Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### e-maxx's blog

By e-maxx, 9 years ago, translation, ,
Solution for this problem consists of two stages. First stage - counting the numbers with 1 as their first digit in the [L;R] segment. Second stage - using this information (in fact, by given probabilities that i -th quantity will be good) solve the problem about K percents.

To solve the first sub-problem one can generate all segments of good numbers and look how many numbers from them lie in the [L;R] segment. Segments of good numbers are of form [1;1] , [10;19] , [100;199] and so on, that is, [10 i;2· 10 i - 1] . After noticing that, calculating their intersection with [L;R] segment is quite easy.

So, we've learnt how to calculate the probability p[i] that i -th quantity is correct: this probability p[i] equals to a fraction of the number of good numbers and R[i] - L[i] + 1 .

Now we can go to the second stage of the solution: solving the problem with N quantities and K percents. Now we know the probabilities p[i] that this or that quantity is good, and want to find the probability that K percents of them will be good. This can be done using dynamic programming: let's D[i][j] - probability that among first i quantities exactly j will be good. The starting state is D[0][0] = 1 , and calculation of other states can be done as following:

D[i][j] = p[i - 1]· D[i - 1][j - 1] + (1 - p[i - 1])· D[i - 1][j].

After that answer to the problem will be a sum of D[n][j] over all j such, that j / n ≥ k / 100 .

• +18

 9 years ago, # | ← Rev. 2 →   +7 hi why you dont put any tutorial about problem A and problem B ? although these are simple(maybee!) but i hope you put them , by the way , thanks.....
 9 years ago, # |   0 I was just wondering, if the second part (DP) could be solved in < O(n^2). Is there any way?