A15396. Minimize the Thickness
编程题
普及/提高-
知识点
题目描述
You are given a sequence $a=[a_1,a_2,\dots,a_n]$ consisting of $n$ positive integers.
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]$ .
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.
We split the given sequence $a$ into segments so that:
- each element is in exactly one segment;
- the sums of elements for all segments are equal.
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$ .
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$ .
Find the minimum thickness among all possible splits of the given sequence of $a$ into segments in the required way.
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]$ .
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.
We split the given sequence $a$ into segments so that:
- each element is in exactly one segment;
- the sums of elements for all segments are equal.
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$ .
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$ .
Find the minimum thickness among all possible splits of the given sequence of $a$ into segments in the required way.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 100$ ) — the number of test cases.
Each test case is described by two lines.
The first line of each test case contains a single integer $n$ ( $1 \le n \le 2000$ ) — the length of the sequence $a$ .
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$ .
It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$ .
Each test case is described by two lines.
The first line of each test case contains a single integer $n$ ( $1 \le n \le 2000$ ) — the length of the sequence $a$ .
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$ .
It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$ .
输出格式
For each test case, output one integer — the minimum possible thickness of a split of the sequence $a$ into segments.
Note that there always exist a split, you can always consider whole sequence as one segment.
Note that there always exist a split, you can always consider whole sequence as one segment.
输入输出样例
输入 #1
4 6 55 45 30 30 40 100 4 10 23 7 13 5 10 55 35 30 65 6 4 1 1 1 1 4
输出 #1
3 4 2 3
说明/提示
The split in the first test case is explained in the statement, it can be shown that it is optimal.
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$ .
In the third test case, the optimal split will be $[10, 55], [35, 30], [65]$ . The thickness of the split equals to $2$ .
In the fourth test case possible splits are:
- $[4] + [1, 1, 1, 1] + [4]$ ;
- $[4, 1, 1] + [1, 1, 4]$ .
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$ .
In the third test case, the optimal split will be $[10, 55], [35, 30], [65]$ . The thickness of the split equals to $2$ .
In the fourth test case possible splits are:
- $[4] + [1, 1, 1, 1] + [4]$ ;
- $[4, 1, 1] + [1, 1, 4]$ .