CartInSupermarket
SRM 649 · 2015-01-29 · by tozangezan
Problem Statement
The process of removing the carts will consist of one or more turns. Each turn will take exactly one minute. At the beginning of each turn, you will have some sequences of carts. For each of those sequences you can choose between two options:
- split it (in an arbitrary place) into two shorter sequences
- remove one shopping cart from the sequence
There is one additional constraint: during the entire process you can only choose to split a sequence at most b times.
You are given
Constraints
- The number of elements in a will be between 1 and 50, inclusive.
- Each element in a will be between 1 and 1,000,000,000, inclusive.
- b will be between 0 and 1,000,000,000, inclusive.
{8}
3
Returns: 4
We have a single sequence of 8 carts and we can use at most 3 splits. The optimal solution takes 4 minutes. During the first minute split the sequence of 8 carts into two sequences with 4 carts each. During the second minute perform two splits, dividing each of the two 4-cart sequences into two new sequences with 2 carts each. Thus, after the second minute you will have four sequences of 2 carts. In the third minute choose to remove a cart from each of them. Repeat that choice in the fourth minute and you are done.
{6,6,5}
3
Returns: 4
One optimal solution with only 4 minutes looks as follows: Split each of the first two sequences from 6 to 3+3. Remove a cart from the third sequence, shortening it from 5 to 4. Sequences after the first minute: {3,3,3,3,4}. Shorten each of the sequences of length 3. Split the sequence of length 4 into 2+2. Sequences after the second minute: {2,2,2,2,2,2}. Shorten each sequence. Sequences after the third minute: {1,1,1,1,1,1}. Shorten each sequence again and you are done.
{12,5,6,2,6,8}
4
Returns: 6
{15,20,11,13,18,24,25,21,22,10,15,14,19}
0
Returns: 25
{671122748,846444748,84701624,608579554,672060899,967957440,31438849,734849843,376589643,904285209
,80693344,211737743,85405464,444633541,293184188,935462519,146753109,972886045,496631016,601669536
,257574086,958464570,6294570,546189534,668105964,601197313,784337929,921840143,70408284,722040626
,253400894,56411549,811940644,152086353,122638884,776352066,118932182,177589709,538122558,127914469
,523761221,290027568,734517444,819458123,699130727,784698122,810265337,283326309,593596316,368671876}
6478
Returns: 3805054
Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CartInSupermarket with a public method int calcmin(vector<int> a, int b) · 105 test cases · 2 s / 256 MB per case