Codeforces Round 982 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$, изначально содержащий $$$n$$$ целых чисел. За одну операцию вы можете сделать следующее:
Какова максимально возможная длина массива $$$a$$$ после выполнения данной операции некоторое количество раз (возможно, нулевое)?
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможную длину $$$a$$$ после выполнения некоторой последовательности операций.
452 4 6 2 555 4 4 5 146 8 2 311
10 11 10 1
В первом наборе входных данных мы можем сначала выбрать $$$i = 4$$$, так как $$$a_4 = 5 + 1 - 4 = 2$$$. После этого массив станет равен $$$[2, 4, 6, 2, 5, 0, 0, 0]$$$. Затем мы можем выбрать $$$i = 3$$$, так как $$$a_3 = 8 + 1 - 3 = 6$$$. После этого массив станет равен $$$[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$$$, то есть будет иметь длину $$$10$$$. Можно показать, что нельзя получить более длинный массив.
Во втором наборе входных данных мы можем выбрать $$$i=2$$$, затем $$$i=3$$$, затем $$$i=4$$$. Итоговый массив будет равен $$$[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$$$, и его длина будет равняться $$$11$$$.
Название |
---|