codeforces-scrape

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

1741C.md (2736B)


      1 Source: https://codeforces.com/problemset/problem/1741/C
      2 
      3 C. Minimize the Thickness
      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 You are given a sequence $a=[a_1,a_2,\dots,a_n]$ consisting of $n$ positive integers.
     22 
     23 Let's call a group of consecutive elements a segment. Each segment is characterized by two indices: the index of its left end and the index of its right end. Denote by $a[l,r]$ a segment of the sequence $a$ with the left end in $l$ and the right end in $r$, i.e. $a[l,r]=[a_l, a_{l+1}, \dots, a_r]$.
     24 
     25 For example, if $a=[31,4,15,92,6,5]$, then $a[2,5]=[4,15,92,6]$, $a[5,5]=[6]$, $a[1,6]=[31,4,15,92,6,5]$ are segments.
     26 
     27 We split the given sequence $a$ into segments so that:
     28 
     29 * each element is in exactly one segment;
     30 * the sums of elements for all segments are equal.
     31 
     32 For example, if $a$ = [$55,45,30,30,40,100$], then such a sequence can be split into three segments: $a[1,2]=[55,45]$, $a[3,5]=[30, 30, 40]$, $a[6,6]=[100]$. Each element belongs to exactly segment, the sum of the elements of each segment is $100$.
     33 
     34 Let's define thickness of split as the length of the longest segment. For example, the thickness of the split from the example above is $3$.
     35 
     36 Find the minimum thickness among all possible splits of the given sequence of $a$ into segments in the required way.
     37 
     38 Input
     39 
     40 The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.
     41 
     42 Each test case is described by two lines.
     43 
     44 The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the length of the sequence $a$.
     45 
     46 The second line of each test case contains exactly $n$ integers: $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — elements of the sequence $a$.
     47 
     48 It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$.
     49 
     50 Output
     51 
     52 For each test case, output one integer — the minimum possible thickness of a split of the sequence $a$ into segments.
     53 
     54 Note that there always exist a split, you can always consider whole sequence as one segment.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 4
     62 
     63 6
     64 
     65 55 45 30 30 40 100
     66 
     67 4
     68 
     69 10 23 7 13
     70 
     71 5
     72 
     73 10 55 35 30 65
     74 
     75 6
     76 
     77 4 1 1 1 1 4
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 3
     84 4
     85 2
     86 3
     87 ```
     88 
     89 Note
     90 
     91 The split in the first test case is explained in the statement, it can be shown that it is optimal.
     92 
     93 In the second test case, it is possible to split into segments only by leaving a single segment. Then the thickness of this split is equal to the length of the entire sequence, that is, $4$.
     94 
     95 In the third test case, the optimal split will be $[10, 55], [35, 30], [65]$. The thickness of the split equals to $2$.
     96 
     97 In the fourth test case possible splits are:
     98 
     99 * $[4] + [1, 1, 1, 1] + [4]$;
    100 * $[4, 1, 1] + [1, 1, 4]$.