DWITE Online Computer Programming Contest

Sleepwalking Probabilities

January 2011
Problem 5

It is bad news if you are sleepwalking in the middle of nowhere, wandering 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 the probabilities 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 (the number of steps to take); 1 ≤ N, S, E, W ≤ 97 (probabilities for going in any particular direction at every step). N+S+E+W always equals 100.

The output file OUT5.txt will contain 5 lines, each containing a single integer representing 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):