codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.