CartInSupermarketEasy
SRM 649 · 2015-01-29 · by tozangezan
SRM 649 · 2015-01-29 · by tozangezan · Simple Math
Problem Statement
Problem Statement
You have a sequence that consists of N shopping carts.
You want to remove all of them as quickly as possible.
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:
There is one additional constraint: during the entire process you can only choose to split a sequence at most K times.
You are given theint s N and K.
Compute and return the smallest number of minutes in which it is possible to remove all the carts.
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 K times.
You are given the
Constraints
- N will be between 1 and 100, inclusive.
- K will be between 0 and 100, inclusive.
Examples
0)
5 0 Returns: 5
As K=0, you can never split any sequence. In each turn you have to remove one cart from your sequence. Hence, it will take 5 minutes to remove all 5 carts.
1)
5 2 Returns: 4
One optimal solution: {5} -> {2,3} -> {1,2} -> {1,1} -> {}. We used two splits: once when splitting the sequence of 5 carts into 2+3 and the second time when splitting the sequence of 2 carts into 1+1.
2)
15 4 Returns: 6
3)
7 100 Returns: 4
You don't have to split exactly K times.
4)
45 5 Returns: 11
Submissions are judged against all 144 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CartInSupermarketEasy with a public method int calc(int N, int K) · 144 test cases · 2 s / 256 MB per case