Решение этой задачи состоит из двух этапов. Первый - научиться считать количество чисел со старшей цифрой 1 в отрезке [L;R]. Второй - по полученным данным (т.е. фактически по известным вероятностям того, что одна величина будет хорошей) решить задачу про K процентов.
Чтобы решить первую подзадачу, можно сгенерировать все отрезки хороших чисел и посмотреть, что останется после их пересечения с отрезком [L;R]. Отрезки хороших чисел имеют вид [1;1], [10;19], [100;199] и т.д., т.е. [10i;2· 10i - 1]. Посчитать, сколько же чисел содержится в их пересечении с отрезком [L;R] - тривиальная задача.
Значит, мы научились считать вероятность p[i] (i = 0... n - 1) того, что i-ая величина будет хорошей: эта вероятность p[i] равна отношению количества хороших чисел, которое мы только что считали, к величине R[i] - L[i] + 1.
Теперь перейдём ко второй части задачи. В ней требуется по полученным вероятностям p[i] того, что та или иная величина будет хорошей, посчитать вероятность того, что K процентов всех величин будут хорошими. Это делается методом динамического программирования: пусть D[i][j] - вероятность того, что среди первых i величин ровно j будут хорошими. Начальным состоянием является D[0][0] = 1, а переходы в динамике следующие:
D[i][j] = p[i - 1]· D[i - 1][j - 1] + (1 - p[i - 1])· D[i - 1][j].
Ответом на задачу будет сумма D[n][j] по всем j таким, что j / n ≥ k / 100.
Чтобы решить первую подзадачу, можно сгенерировать все отрезки хороших чисел и посмотреть, что останется после их пересечения с отрезком [L;R]. Отрезки хороших чисел имеют вид [1;1], [10;19], [100;199] и т.д., т.е. [10i;2· 10i - 1]. Посчитать, сколько же чисел содержится в их пересечении с отрезком [L;R] - тривиальная задача.
Значит, мы научились считать вероятность p[i] (i = 0... n - 1) того, что i-ая величина будет хорошей: эта вероятность p[i] равна отношению количества хороших чисел, которое мы только что считали, к величине R[i] - L[i] + 1.
Теперь перейдём ко второй части задачи. В ней требуется по полученным вероятностям p[i] того, что та или иная величина будет хорошей, посчитать вероятность того, что K процентов всех величин будут хорошими. Это делается методом динамического программирования: пусть D[i][j] - вероятность того, что среди первых i величин ровно j будут хорошими. Начальным состоянием является D[0][0] = 1, а переходы в динамике следующие:
D[i][j] = p[i - 1]· D[i - 1][j - 1] + (1 - p[i - 1])· D[i - 1][j].
Ответом на задачу будет сумма D[n][j] по всем j таким, что j / n ≥ k / 100.
в таком случае мы не учитываем p[n] и обращаемся к p[0]
http://codeforces.net/contest/50/problem/D
Кстати, кто знает, нет ли у нее какого-нибудь названия вроде "обобщенной схемы Бернулли"? Ведь то же самое, только вероятности различны.
Вот я очень долго не мог найти формулу для количества чисел с первыми единичками :) А помимо всего прочего, меня Петр по B поломал (я квадраты на 90 градусов не поворачивал), пришлось исправлять. А мог бы еще и обратно поломать, причем навсегда; я даже не предполагал, что можно допустить ошибку в сравнении, и на этот кусок кода, разумеется, не смотрел. Так вообще оказалось, что у меня в комнате как минимум три решения B с таким багом были.
Когда наконец уже придумал все в C, времени не оставалось дописать.
Мне кстати тоже приходила такая мысль, когда писал решение этой задачи - уж больно стандартно выглядит эта формула PD[i - 1] + (1 - P)D[i - 1].
Наверняка у математиков какое-нибудь слово придумано на этот случай :)
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.....
чекер ведет себя очень странно. Решение доходит до какого-нибудь теста, после чего чекер говорит что-нибудь вроде
"Test: #17, time: 2000 мс., память: 13208 Кб, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
то есть ввод пустой.
Одно и то же решение доходит до разных тестов, от 17 до 57, а потом случается вот такой тайм лимит.