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
```