/*Task 110. A hunter has to shoot at least K animals. He knows the probability of every animal been shot.
Find the probability of the hunter's success.

The term "at least K animals been shot" is that the hunter can miss no more than (N-K) times.
The task is being solved recursively by considering two situations:
 - the current animal is shot with probability of p[i], and we still have K rooms to fail for other animals;
 - the current animal is missed with probability of (1-p[i]), and we now have (K-1) rooms to fail for other animals.
The task has two return conditions:
 - all animals have already been shot or missed: the probability to shoot 0 animals is 100%;
 - we've missed K times and now we have to become The Gunslinger and kill the rest of the animals: the probability is p[i+1]*p[i+2]*...
*/

#include <iostream>
#include <vector>
#include <numeric>

double task110_impl(std::vector<double> const& probs, int can_be_missed) {
	// An ideal hunt is when you shall not shoot at all:
	if (probs.size() == 0)
		return 1.;

	// You have already got some misses. You have to shoot rest of the animals:
	if (can_be_missed == 0)
		return std::accumulate(probs.begin(), probs.end(), 1., std::multiplies<double>());

	std::vector<double> psi(probs.begin() + 1, probs.end());

	// Else you get two cases:
	// - you shoot the current animal with probability of `probs[0]` and then you have `can_be_missed` shots;
	// - you miss the current shot with probability of `1-probs[0]` and you have `can_be_missed-1` shots.
	return probs[0] * task110_impl(psi, can_be_missed) +
	(1. - probs[0]) * task110_impl(psi, can_be_missed - 1);
}

double task110(std::vector<double> const& probs, int must_be_shot) {
	// The condition "at least K animals been shot" is like a hunter can miss no more than (N-K) times.
	return task110_impl(probs, probs.size() - must_be_shot);
}


int main(void) {
	std::cout << task110({ 0.5, 0.5, 0.5 }, 2) << '\n';
	std::cout << task110({ 0.3, 0.4, 0.7, 0.1 }, 3) << '\n';
	std::cout << task110({ 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 }, 8) << '\n';

	system("pause");
	return 0;
}