Переполнится ли буфер
В буфере маршрутизатора помещается N пакетов, сейчас в нём k. Каждую микросекунду происходит ровно одно событие: с вероятностью p приходит пакет, и их становится на один больше, иначе один пакет уходит дальше, и их становится на один меньше. События разных микросекунд независимы. Если буфер опустел, маршрутизатор засыпает; если в нём оказалось N пакетов, он переполнен, и начинаются потери.
С какой вероятностью буфер переполнится раньше, чем опустеет?
Вход
В первой строке число запросов q (1 ≤ q ≤ 105). Дальше q строк N k a: вместимость буфера, число пакетов сейчас и вероятность прихода пакета p = a / 109 (1 ≤ N ≤ 109, 0 ≤ k ≤ N, 1 ≤ a ≤ 109 − 1).
Выход
Для каждого запроса — вероятность переполнения с абсолютной погрешностью не больше 10−6.
Примеры
Пример 1
4 2 1 500000000 10 3 600000000 5 5 300000000 7 0 900000000
0.5000000000 0.7161223611 1.0000000000 0.0000000000
Пример 2
4 1000000000 500000000 499999999 1000000000 10 500000001 1000000000 999999990 499999990 1000000000 123456789 500000000
0.1192029220 0.0000000407 0.9999996000 0.1234567890
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обозначьте ответ Pk и разберите первую микросекунду: Pk = p·Pk+1 + q·Pk−1, где q = 1 − p, а P0 = 0 и PN = 1. Как в статье, решите это уравнение для разностей соседних P.
2Подсказка 2
Формула получится короткой, но попробуйте посчитать по ней второй пример — буфер на миллиард пакетов. Что будет с (q/p)N?
3Идея
Перепишем уравнение как p(Pk+1 − Pk) = q(Pk − Pk−1): каждая следующая разность в r = q/p раз больше предыдущей. Разности — геометрическая прогрессия, их сумма от 0 до N равна 1, и при p ≠ ½
Pk = (rk − 1) / (rN − 1),
а при p = ½ все разности равны, и Pk = k/N, как в теореме статьи. Это и есть вся математика задачи. Трудность — в арифметике: при N = 109 и p чуть меньше ½ число rN не помещается ни в какой тип с плавающей точкой, а при p чуть больше ½ числитель и знаменатель — разности близких к единице чисел, и вычитание съедает все значащие цифры.
4Разбор
Перейдём к показателям: r = ex, где x = ln(q/p) = ln(1 + (q − p)/p). Разность q − p = (109 − 2a)/109 считаем в целых числах, а логарифм — функцией log1p, которая точна для маленьких аргументов. Если x < 0, то Pk = expm1(kx) / expm1(Nx), где expm1(t) = et − 1 считается без вычитания. Если x > 0, разделим числитель и знаменатель на rN: Pk = e(k − N)x · (1 − e−kx) / (1 − e−Nx) — теперь все степени не больше единицы. Отдельно — a = 5·108 (ответ k/N) и k = 0 или N.
Во втором примере буфер на миллиард пакетов заполнен наполовину, а пакеты приходят с вероятностью 0,499999999 — на две миллиардных реже, чем уходят. Кажется, это почти честная монетка, и ответ должен быть около ½. Но Nx ≈ 4: за миллиард шагов крошечный перевес успевает сработать, и буфер переполнится лишь с вероятностью 0,119.
4+Решение
5Сложность
O(1) на запрос.
6Типичные ошибки
- Формула «как в учебнике». (1 − rk) / (1 − rN) переполняется при больших N, а при p = ½ делит ноль на ноль — на первом же примере.
- q = 1 − p в дробях. При p = ½ + 10−9 разность q − p, посчитанная из дробей, теряет около половины из шестнадцати значащих цифр; надёжнее считать её в целых.
- Моделирование. Средняя длительность здесь доходит до 1017 микросекунд, и даже одной прогулки не дождаться.