Are my answers correct?

1 -> 3.901234568

3 -> 11.127676543

4 -> 14.729570346

7 -> 25.468979219

29 -> 101.642021572

666 -> 2035.625369012

2011 -> 6070.641622553

5000 -> 15037.641622575

P.S. I have WA #4

Re: Are my answers correct?

As you can verify with brute-force, your answers are wrong. Right answers to your tests are:

1 -> 3.901234567901235

3 -> 11.127669135802471

4 -> 14.729542419753088

7 -> 25.468757517434465

29 -> 101.624893271458560

666 -> 2034.088837677804600

2011 -> 6069.098765418760200

5000 -> 15036.098765432045000

Re: Are my answers correct?

Thank you very much! It seems to be the precision problem in my first solution. But I don't understand why my program gives correct answers now. I just replaced the calculation of expected time of a group of combinations ( the total amount of them is 100 ) to calculation this for every combination separately on each iteration (of course, I did the same with array of probabilities). But I think the more very small numbers you store, the bigger precision troubles you have, isn't it?

Re: Are my answers correct?

Oh my God, you described something very difficult =) My solution fills only two linear arrays in O(N)...

Re: Are my answers correct?

I have an array P[10][10], where P[i][j] is the probability, that Feofan remembers the combination i,j (if i or j less, than 2, then P[i][j] = 1). Then I calculate the expected time for each such combination. So, you can assume I also have 2 arrays of length 100, and my algo O(k) :)

Re: Are my answers correct?

I don't quite understand where do you need this array P[10][10]? - for any combination of digits you can easily calculate probability that he was already summing this before k-th position - it is 1-0.98^(k-1) for non-equal digits and 1-0.99^(k-1) for equal digits...

Re: Are my answers correct?

Yes, it's true (except the combinations like 1-4). But I store this in array because of my own convenience :)

*Edited by author 20.05.2011 16:13*