Hint.

Posted by

jk_qq 15 Oct 2017 02:54

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++).