DWITE Online Computer Programming Contest
January 2011
Problem 5
Sleepwalking Probabilities

It is bad news if you are sleepwalking in the middle of nowhere, wondering aimlessly. Unfortunately for you, that is exactly what is happening. Being slightly aware of what is going on, and somehow having access to a programmable mobile device, you decide to try to figure out where you might end up (but not call to be picked up, or anything like that...). You notice that you step North, South, East or West with probabilities of N, S, E, and W. You can also make an educated guess that you'd probably be taking M more steps. So now you want to calculate the probability that you'll end up at the same spot as you've started, after taking M steps.

The input file DATA5.txt will contain 5 lines, each containing integers 1 <= M <= 10, 1 <= N, S, E, W <= 97. N+S+E+W always add up to 100. The number of steps to take, and probabilities for going in any particular direction at every step.

The output file OUT5.txt will contain 5 lines, each containing a single integer, the probability of ending up at the same spot after M steps; rounded down to the nearest percent.


Sample Input (first 2 cases shown):
2 25 25 25 25
6 17 33 29 21
Sample Output (first 2 cases shown):