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 DPapproach 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 Edited by author 25.11.2016 17:53 Many AC codes input the n=100, output have many zero before the radix point, the relative error is not enough very much! Why did they accept? Give me, please, first 1015 answers. 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 What was the issue? For me straightforward implementation in C++ using double got AC easily. How did you take 100th power of 3/2? I can't think it out. I've never used decimal long arithmetic. Edited by author 03.01.2013 16:06 Edited by author 03.01.2013 16:06 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 :) good test: n=40 ans=3688328.070956036 The problem asks for at least 6 correct decimals. I had to compute up to 100 decimals (in intermediate computations) to get the required precision in the final answer for n = 100. Here is the (censored) answer for the biggest possible test: n = 100 answer = 13552*3*4*4*1*6*18.186159417 
