If you think it in a way of dynamic programming it could help. Imagine we have N pirats. Calculate probability of draw for single round (either all N pirats has the same gesture or there's a pirat for every possible gesture).
Then calculate average number of rounds to be played before someone lost (standard geometric sum).
Now someone is lost and we have the same game but with less pirats. So we can use DP-approach with probabilities.
Use doubles, it's enough to get AC. You would be happy to implement this problem (my impl is 30 lines with i/o on c++).
the statement says "You should help him determine the expected value of prize in case of his victory" but I believe it should be the case of anyone's victory. can someone who solved the problem please clarify this? thanks
Edit: I got accepted assuming the original statement is wrong
It's not hard to get the correct formula for this problem, but harder to implement it because of high precision required. At last I had to use precalculated array for getting AC. Here's your answers: 2 -> 1.5 3 -> 2.25 4 -> 3.21428571 5 -> 4.48571429 6 -> 6.21981567 7 -> 8.64673579 8 -> 12.1044438 9 -> 17.0919353 10 -> 24.3495978
It is useful to remember that standard double type can store numbers up to 10^300 (and even a bit more). (3/2)^100 < 2^100 < 10^35 => no problem to compute it in double. And since you need relative accuracy of only 7 digits => 16+ digits that double variable stores is more than enough to compute what you need. Actually, here with usual double you can calculate answers for n up to 500+.
Is it really true? I always thought that double type takes only 8 bytes of memory and hence cannot store such big numbers. But anyway thank you. Maybe I just have bad compiler or bad implementation as always :)