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

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

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?

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

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) :)

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

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