DWITE '10 R4 #5 - Sleepwalking Probabilities

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, 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 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 will contain 5 lines, each containing integers 1 \le M \le 10, 1 \le N, S, E, W \le 97. N+S+E+W 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 M steps; rounded down to the nearest percent.

Sample Input

2 25 25 25 25
6 17 33 29 21

Sample Output

25
7

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.