Show all threads Hide all threads Show all messages Hide all messages 
Hint.  jk_qq  1936. Roshambo  15 Oct 2017 02:54  1 
Hint. 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 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++). 
not sure about statement  Motasem ALKayed  1936. Roshambo  25 Nov 2016 01:32  1 
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 
the problem of relative error  Yuiffy  1936. Roshambo  4 Aug 2014 18:30  1 
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? 
some tests  Vladimir  1936. Roshambo  24 May 2014 01:44  10 
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 Re: some tests Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 18 Dec 2012 04:19 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 Re: some tests Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 4 Jan 2013 16:09 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 :) Re: some tests Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 6 Jan 2013 01:25 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 
The "beats" are backwards  Bogatyr  1936. Roshambo  12 Nov 2012 18:35  1 
