Кот Miston поставил на скачивание сериал «Котокоп» («Police Cat»). В сериале $$$n$$$ серий, $$$i$$$-я из которых сейчас скачивается со скоростью $$$v_i$$$, и браузер показывает, что $$$i$$$-я серия скачается ровно через $$$t_i$$$ минут, что не совсем верно.
Браузер рассчитывает время, исходя из предположения, что скорость скачивания $$$i$$$-й серии не изменится. Однако когда какая-то серия оказывается полностью скачанной, скорость скачивания других серий увеличивается (других причин для изменения скорости скачивания той или иной серии и правда нет). При этом соотношения скоростей скачивания еще не скачанных серий неизменны. Иными словами, если $$$v_i^t$$$ — скорость скачивания $$$i$$$-й серии в момент времени $$$t$$$, то для любых $$$i$$$ и $$$j$$$ верно, что при всех $$$t$$$, меньших момента окончания скачивания $$$i$$$-й или $$$j$$$-й серии, величина $$$\frac{v_i^t}{v_j^t}$$$ одинакова.
Никакой другой нагрузки на сеть, кроме скачивания $$$n$$$ серий, нет. То есть суммарная скорость скачивания $$$\sum\limits_{i=1}^n v_i^t$$$ постоянна (одинакова при любом $$$t$$$).
Определите для каждой серии реальный момент времени, в который завершится ее загрузка.
В первой строке ввода содержится целое число $$$n$$$ — количество серий в сериале ($$$1 \le n \le 3 \cdot 10^5$$$).
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$v_i$$$ и $$$t_i$$$ — текущая скорость скачивания и предполагаемое браузером время скачивания $$$i$$$-й серии ($$$1 \le v_i, t_i \le 10^{18}$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{18}$$$).
Для каждой серии выведите настоящее время ее скачивания.
Ваш ответ будет засчитан, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$. Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет засчитан, если $$$\frac {|a - b|}{\max(1, b)} \le 10^{-6}$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 5 | $$$n \le 2$$$ | полная | |
| 2 | 5 | $$$n \le 3$$$ | 0, 1 | первая ошибка |
| 3 | 15 | $$$n, v_i, t_i \le 3000$$$ | 0 | первая ошибка |
| 4 | 20 | $$$n \le 3000$$$ | 0 – 3 | первая ошибка |
| 5 | 20 | $$$v_i = v_j$$$ для всех $$$i$$$, $$$j$$$ | первая ошибка | |
| 6 | 15 | $$$n \le 30\,000$$$ | 0 – 4 | первая ошибка |
| 7 | 5 | $$$t_i \le 10^{9}$$$ для всех $$$i$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{9}$$$ | 0, 3 | первая ошибка |
| 8 | 15 | без дополнительных ограничений | 0 – 7 | первая ошибка |
22 43 5
4 4.6
31 45 22 3
2.5 2 2.375
| Innopolis Open 2024. Заключительный этап |
|---|
| Закончено |
