2027C.md (1823B)
1 Source: https://codeforces.com/problemset/problem/2027/C 2 3 C. Add Zeros 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You're given an array $a$ initially containing $n$ integers. In one operation, you must do the following: 22 23 * Choose a position $i$ such that $1 \lt i \le |a|$ and $a_i = |a| + 1 - i$, where $|a|$ is the current size of the array. 24 * Append $i - 1$ zeros onto the end of $a$. 25 26 After performing this operation as many times as you want, what is the maximum possible length of the array $a$? 27 28 Input 29 30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 31 32 The first line of each test case contains $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array $a$. 33 34 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$). 35 36 It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$. 37 38 Output 39 40 For each test case, output a single integer — the maximum possible length of $a$ after performing some sequence of operations. 41 42 Example 43 44 Input 45 46 ``` 47 4 48 49 5 50 51 2 4 6 2 5 52 53 5 54 55 5 4 4 5 1 56 57 4 58 59 6 8 2 3 60 61 1 62 63 1 64 ``` 65 66 Output 67 68 ``` 69 10 70 11 71 10 72 1 73 ``` 74 75 Note 76 77 In the first test case, we can first choose $i = 4$, since $a_4 = 5 + 1 - 4 = 2$. After this, the array becomes $[2, 4, 6, 2, 5, 0, 0, 0]$. We can then choose $i = 3$ since $a_3 = 8 + 1 - 3 = 6$. After this, the array becomes $[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$, which has a length of $10$. It can be shown that no sequence of operations will make the final array longer. 78 79 In the second test case, we can choose $i=2$, then $i=3$, then $i=4$. The final array will be $[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$, with a length of $11$.