Каждое утро Винни-Пух собирает из ульев мёд. Весь собранный мёд Винни переливает в один большой горшок и с нетерпением ждёт, когда же он наконец переполнится.
И тогда Винни сможет съесть весь собранный мёд.
Однако этот долгожданный день откладывается из-за того, что каждый вечер Винни-Пух съедает часть мёда из горшка.
Известно, что каждый день Винни-Пух собирает ровно $$$A$$$ литров мёда, каждый вечер съедает в точности $$$B$$$ литров $$$(B \lt A)$$$. Объем горшка составляет $$$C$$$ литров, а все дни сбора мёда пронумерованы, начиная с $$$1$$$. Изначально горшок пуст.
Требуется выяснить, когда же всё-таки наступит этот долгожданный день, а именно — номер дня, когда в момент добавления нового мёда он не поместится в горшок целиком.
Вводятся три целых числа $$$A$$$, $$$B$$$, $$$C$$$, где $$$A$$$ — количество мёда (в литрах), собираемого Винни-Пухом каждое утро, $$$В$$$ — количество мёда (в литрах), съедаемого Винни-Пухом каждый вечер, $$$C$$$ — количество мёда (в литрах), помещающегося в горшок. Все числа $$$A$$$, $$$B$$$, $$$C$$$ принадлежат промежутку $$$[1; 10^{18}]$$$, причем $$$B \lt A$$$.
Каждое число подается на вход в отдельной строке.
Выведите одно целое число — номер дня (при нумерации дней с $$$1$$$), когда горшка не хватит, чтобы весь собранный в этот день мёд поместился в него.
Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.
| Подгруппа | Дополнительные ограничения | Баллы | Необходимые подгруппы |
| $$$0$$$ | Тест из условия | $$$0$$$ | — |
| $$$1$$$ | $$$A, B, C \le 100$$$ | $$$20$$$ | $$$0$$$ |
| $$$2$$$ | $$$A, B, C \le 10^9$$$ | $$$30$$$ | $$$0,\ 1$$$ |
| $$$3$$$ | — | $$$50$$$ | $$$0,\ 1,\ 2 $$$ |
5210
3
При решении следует использовать 64-битный тип данных (int64 в Pascal, long long в C++ или long в Java).
В доме Васи появились мухи. Они были чересчур активными, нахально ползали по окну и громко жужжали. Они мешали Васе жить.
И Вася принял решение. Он вычислил координаты всех мух. Он определил для каждой мухи её активность — некоторое положительное число. Он купил отличную мухобойку радиуса $$$r$$$. Мухобойка действует только на мух с положительной активностью. Если под удар такой мухобойки попадёт сразу $$$k$$$ мух с положительной активностью, то активность каждой из них уменьшится на $$$\dfrac{1}{k}$$$ единиц. Как только активность мухи перестанет быть положительным числом, муха впадает в зимнюю спячку.
Какое минимальное количество раз Васе придётся ударить мухобойкой, чтобы избавиться от всех мух?
В первой строке через пробел записаны целые числа $$$n$$$ и $$$r$$$ $$$(1 \le n, r \le 10\, 000)$$$ — количество мух и радиус мухобойки. В каждой из следующих $$$n$$$ строк через пробел записаны координаты очередной мухи и её активность. Все координаты и активности — целые положительные числа, не превосходящие $$$10\,000$$$.
Никакие две мухи не находятся в одной точке.
Выведите единственное число — минимальное количество раз, которое нужно ударить мухобойкой, чтобы сделать активности всех мух неположительными числами.
Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.
| Подгруппа | Дополнительные ограничения | Баллы | Необходимые подгруппы |
| $$$0$$$ | Тест из условия | $$$0$$$ | — |
| $$$1$$$ | $$$n \le 10$$$ | $$$20$$$ | $$$0$$$ |
| $$$2$$$ | $$$n \le 1\,000$$$ | $$$30$$$ | $$$0,\ 1$$$ |
| $$$3$$$ | — | $$$50$$$ | $$$0,\ 1,\ 2 $$$ |
2 51 1 42 2 5
9
Андрей — отличный стрелок. Он никогда не промахивается. Ему очень нравится стрелять по внезапно появляющимся мишеням.
Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными числами.
Каждая мишень может «убита» в течение лишь одной секунды с момента её появления. Будем считать, что выстрел происходит мгновенно, поэтому поразить мишень можно в любой момент этой одной секунды: в самом её начале, в конце или в любой другой промежуточный момент между.
На перезарядку ружья у Андрея уходит ровно $$$1$$$ секунда, а одной перезарядки хватает только на один выстрел. В начальный момент времени (момент времени, равный $$$0$$$) ружьё у Андрея заряжено. Кроме того, Андрей успевает зарядить ружьё и выстрелить по мишени, если мишень появилась в тот же момент, в который он начал перезаряжать ружьё.
По известным моментам времени появления мишеней посчитайте максимальное количество мишеней, которые может поразить Андрей.
В первой строке вводится натуральное число $$$N$$$ — количество мишеней $$$(1 \le N \le 2 \cdot 10^5)$$$.
Во второй строке записано $$$N$$$ целых чисел — моменты появления мишеней $$$t_i$$$, выраженные в секундах от начала тренировки. Каждый момент появления мишени $$$t_i$$$ — это целое число из промежутка $$$[1; 10^9]$$$.
Выведите одно целое число — максимальное количество мишеней, которые может поразить Андрей.
Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.
| Подгруппа | Дополнительные ограничения | Баллы | Необходимые подгруппы |
| $$$0$$$ | Тест из условия | $$$0$$$ | — |
| $$$1$$$ | $$$N \le 10,\ t_i \le 10$$$ | $$$10$$$ | $$$0$$$ |
| $$$2$$$ | $$$N \le 25,\ t_i \le 50$$$ | $$$15$$$ | $$$0,\ 1$$$ |
| $$$3$$$ | $$$N \le 10^4,\ t_i \le 10^5$$$ | $$$20$$$ | $$$0,\ 1,\ 2$$$ |
| $$$4$$$ | $$$N \le 10^5,\ t_i \le 10^8$$$ | $$$25$$$ | $$$0,\ 1,\ 2,\ 3$$$ |
| $$$5$$$ | — | $$$30$$$ | $$$0,\ 1,\ 2,\ 3,\ 4$$$ |
41 2 1 2
3
Так как поражение мишени происходит мгновенно, то можно поразить две мишени, появившиеся в один и тот же момент времени, если первую мишень поразить сразу, как только она появилась, а вторую после перезарядки ружья, в момент окончания одной секунды.
В примере Андрей может поразить максимум 3 мишени (например, первую, вторую и четвёртую), сделав выстрелы в моменты времени 1 (момент начала секунды), 2 (момент окончания первой секунды, сразу после перезарядки ружья) и 3 (момент окончания второй секунды, сразу после второй перезарядки ружья).