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, [10i;2· 10i - 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.
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, [10i;2· 10i - 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.
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.....