DWITE Online Computer Programming Contest, January 2011, Problem 5
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 , , , and . You can also make an educated guess that you'd probably be taking 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 steps.
The input file will contain 5 lines, each containing integers , . always adds up to 100. These are the number of steps to take, and probabilities for going in any particular direction at every step respectively.
The output will contain 5 lines, each containing a single integer, the probability of ending up at the same spot after steps; rounded down to the nearest percent.
2 25 25 25 25 6 17 33 29 21