codeforces-scrape

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

2237C.md (3432B)


      1 Source: https://codeforces.com/problemset/problem/2237/C
      2 
      3 C. Duck Surplus
      4 
      5 time limit per test
      6 
      7 2 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 Ja the Ghost is playing with rubber ducks again! There are $n$ piles of rubber ducks arranged in a row from left to right. Initially, the $i$-th pile contains $a_i$ rubber ducks.
     22 
     23 While the sequence $a$ is not sorted in nondecreasing order, Ja must perform the following operation:
     24 
     25 * Choose two adjacent piles such that the left pile contains more ducks than the right pile. Ja swaps these two piles, and then adds the number of ducks in the new left pile to the new right pile.
     26 
     27   Formally, choose an index $i$ such that $1\le i \lt n$ and $a_i \gt a_{i+1}$. Then replace the adjacent pair $(a_i,a_{i+1})$ with $(a_{i+1},a_i+a_{i+1})$.
     28 
     29 For example, if two adjacent piles contain $7$ and $3$ rubber ducks, then after the operation they contain $3$ and $10$ rubber ducks.
     30 
     31 Ja may choose any index satisfying the condition above at each step. It can be shown that, regardless of his choices, the process eventually ends with the sequence sorted in nondecreasing order.
     32 
     33 Ja wants the largest pile at the end of the process to contain as few rubber ducks as possible. Determine the minimum possible value of the largest pile.
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     38 
     39 The first line of each test case contains $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of piles.
     40 
     41 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the number of ducks in each pile.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output a single integer — the minimum possible value of the largest pile.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 10
     55 
     56 4
     57 
     58 1 2 2 5
     59 
     60 2
     61 
     62 7 3
     63 
     64 3
     65 
     66 3 2 1
     67 
     68 5
     69 
     70 2 2 1 3 3
     71 
     72 4
     73 
     74 3 1 4 2
     75 
     76 5
     77 
     78 1 4 3 2 5
     79 
     80 6
     81 
     82 6 2 5 1 4 3
     83 
     84 7
     85 
     86 2 7 1 6 3 5 4
     87 
     88 8
     89 
     90 8 1 7 2 6 3 5 4
     91 
     92 5
     93 
     94 1000000000 999999999 999999998 999999997 999999996
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 5
    101 
    102 10
    103 
    104 6
    105 
    106 3
    107 
    108 6
    109 
    110 14
    111 
    112 21
    113 
    114 26
    115 
    116 36
    117 
    118 4999999990
    119 ```
    120 
    121 Note
    122 
    123 In the transformations below, the two underlined numbers are the adjacent pair just obtained by the operation.
    124 
    125 In the first test case, the sequence is already sorted in nondecreasing order. Therefore Ja does not perform any operation, and the answer is $5$.
    126 
    127 In the second test case, Ja has only one possible operation: $$ [7,3]\to [\underline{3},\underline{10}]. $$ The sequence is then sorted, so the answer is $10$.
    128 
    129 In the third test case, Ja can perform the following operations: $$ [3,2,1]\to [\underline{2},\underline{5},1]\to [2,\underline{1},\underline{6}]\to [\underline{1},\underline{3},6]. $$ The largest pile contains $6$ ducks. If Ja first chooses the last two piles instead, the final largest pile would contain $7$ ducks. Therefore the answer is $6$.
    130 
    131 In the fourth test case, Ja cannot choose the first two piles at the beginning, because $2$ is not greater than $2$. One possible process is $$ [2,2,1,3,3]\to [2,\underline{1},\underline{3},3,3]\to [\underline{1},\underline{3},3,3,3]. $$ Thus the answer is $3$.
    132 
    133 In the fifth test case, one optimal process is $$ [3,1,4,2]\to [\underline{1},\underline{4},4,2]\to [1,4,\underline{2},\underline{6}]\to [1,\underline{2},\underline{6},6]. $$ Therefore the answer is $6$.