Barbara goes to Alan’s banana farm, where the NN banana trees are organized in one long line represented by an array BB. The tree at position ii has BiBi banana bunches. Each tree has the same cost. Once Barbara buys a tree, she gets all the banana bunches on that tree.

Banana Bunches solution kickstart

Problem

Barbara goes to Alan’s banana farm, where the NN banana trees are organized in one long line represented by an array BB. The tree at position ii has BiBi banana bunches. Each tree has the same cost. Once Barbara buys a tree, she gets all the banana bunches on that tree.
Alan has a special rule: because he does not want too many gaps in his line, he allows Barbara to buy at most 22 contiguous sections of his banana tree line.

Barbara wants to buy some number of trees such that the total number of banana bunches on these purchased trees equals the capacity KK of her basket. She wants to do this while spending as little money as possible. How many trees should she buy?

Banana Bunches solution kickstart

Banana Bunches solution kickstartInput

The first line of the input gives the number of test cases, TTTT test cases follow.
Each test case begins with a line containing two integers integer NN, the number of trees on Alan’s farm, and KK, the capacity of Barbara’s basket.
The next line contains N positive integers B1,B2,,BNB1,B2,…,BN representing array BB, where the ii-th integer represents the number of banana bunches on the ii-th tree on Alan’s farm.

Banana Bunches solution kickstart

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 11) and yy is the minimum number of trees Barbara must purchase to obtain KK banana bunches using at most 22 contiguous sections of the farm, or -1 if it is impossible to do so.

Banana Bunches solution kickstart

Banana Bunches solution kickstart

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
0BiK0≤Bi≤K, for each ii from 11 to NN.

Test Set 1

1K1041≤K≤104.
1N501≤N≤50.

Test Set 2

1K1041≤K≤104.
1N5001≤N≤500.

Test Set 3

1K1061≤K≤106.

For at most 25 cases:
1N50001≤N≤5000.

For the remaining cases:
1N5001≤N≤500.

Banana Bunches solution kickstart

Banana Bunches solution kickstart

Sample

Sample Input
content_copy
4
6 8
1 2 3 1 2 3
4 10
6 7 5 2
6 8
3 1 2 1 3 1
4 6
3 1 2 0
Sample Output
content_copy
Case #1: 3
Case #2: -1
Case #3: 4
Case #4: 3

Banana Bunches solution kickstart

In Sample Case #1, the first section can contain the trees at indices 22 and 33, and the second section can contain the tree at index 66.

In Sample Case #2, it is impossible to achieve a sum of 1010 with 22 contiguous sections.

In Sample Case #3, the first section can contain the trees at indices {1,2}{1,2}, and the second section can contain the trees at indices {5,6}{5,6}. We cannot take the 2+3+32+3+3 combo (trees at indices {1,3,5}{1,3,5}) since that would be 33 contiguous sections.

In Sample Case #4, the only section contains the trees at indices {1,2,3}{1,2,3}.

Leave a Comment

Your email address will not be published. Required fields are marked *