Codeforces Round 886 (Div. 4) |
---|
Закончено |
Михай и Славик смотрели на группу из $$$n$$$ лягушек, пронумерованных от $$$1$$$ до $$$n$$$, которые изначально находились в точке $$$0$$$. Лягушка $$$i$$$ может прыгнуть на расстояние $$$a_i$$$.
Каждую секунду лягушка $$$i$$$ прыгает на $$$a_i$$$ единиц вперед. Прежде чем лягушки начнут прыгать, Славик и Михай могут поставить ровно одну ловушку в координате, чтобы поймать всех лягушек, которые когда-либо пройдут через эту координату.
Однако, дети не могут уйти далеко от своего дома, поэтому они могут поставить ловушку только в одной из первых $$$n$$$ точках (то есть в точке с координатой от $$$1$$$ до $$$n$$$), и дети не могут поставить ловушку в точке $$$0$$$, так как они боятся лягушек.
Можете ли вы помочь Славику и Михаю определить, сколько лягушек они могут поймать, используя ловушку?
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Затем следуют описания наборов.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество лягушек, которое равно расстоянию, которое Славик и Михай могут пройти, чтобы установить ловушку.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — длины прыжков соответствующих лягушек.
Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество лягушек, которых Славик и Михай могут поймать с помощью ловушки.
751 2 3 4 532 2 263 1 3 4 9 1091 3 2 4 2 3 7 8 511087 11 6 8 12 4 4 8109 11 9 12 1 7 2 5 8 10
3 3 3 5 0 4 4
В первом примере лягушки будут прыгать следующим образом:
Во втором примере Славик и Михай могут поставить ловушку в координате $$$2$$$ и мгновенно поймать всех трех лягушек.
Название |
---|