CHEFYODA
Let’s consider Game1 in which only horizontal and vertical movements are allowed, One can easily see that yoda wins only when both N and M are odd.
In the other game, chef wins only when both N and M are even.
This reduces the problem to followin
- If chef is winning in both the games, output 1
- If chef is losing in both the games, and P \neq 0 , output 0. Else if P = 0, then output 1.
- If chef is losing in 1 game and winning in other, then we need to calculate probbability of winning atleast P games out of K.
This is given by binomial distribution as \frac1 2^K \sum_{i=P}^{K} K\choose i
Now the task is to calculate K\choose i for i = P to K. You can calculate this by using BigDecimal in Java or using Decimal in python. This would work for small test case and would give you 40 points. For large testcase, this would result in TLE, even if you set precision to 6 decimal places.
Now, sum of last K - P terms is equal to sum of first K - P terms
\sum_{i=P}^{K} K\choose i = \sum_{i=0}^{K - P} K\choose i
and as per following
\sum_{i=0}^{K - P} \le 2^{K - 1} \exp\frac{(K - 2(K - P) - 2)^2}{4(1+(K - P) -K)}
since Probability is \frac1 2^K \sum_{i=0}^{K - P} K\choose i, we have
Probability \le 2 ^{-1} \exp\frac{(K - 2(K - P) - 2)^2}{4(1+(K - P) -K)}
Now, for small values of P, probability would be close to 1 and we could answer 1 instead of finding out probability. Similarly, for large values of P, probability would be close to 0 and we could answer 0 instead of finding the probability.
The first difference in output would occur when Probability = 10^{-6}
We can find the value of P by following
10 ^ {-6} = 2 ^{-1} \exp\frac{(K - 2(K - P) - 2)^2}{4(1+(K - P) -K)}
Substituting K = 10 ^ 5 gives P = 49162 and 50821
Substituting K = 10 ^ 6 gives P = 497370 and 502614
Observe that these values are pretty close to \frac K 2. We know that sum of all terms is 2^K and that the series is symetric. Therefore, sum of \frac K 2 terms is 2^{K - 1}. Now, we need to add or subtract atmost 3000 Terms from 2^{K - 1} to get probability.
This can be done within the given timelimit and here is the
(https://www.codechef.com/viewsolution/12795962)
You can also do it using Python Libraries