CartInSupermarketEasy

SRM 649 · 2015-01-29 · by tozangezan

SRM 649 · 2015-01-29 · by tozangezan · Simple Math

Show categories

Class Name: CartInSupermarketEasy

Return Type: int

Method Name: calc

Arg Types: (int, int)

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:

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 ints N and K. Compute and return the smallest number of minutes in which it is possible to remove all the carts.

Constraints

N will be between 1 and 100, inclusive.
K will be between 0 and 100, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

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.

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.

15
4
Returns: 6

7
100
Returns: 4

You don't have to split exactly K times.

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