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 K times.
You are given the
Definition
- Class:
- CartInSupermarketEasy
- Method:
- calc
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int calc(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 100, inclusive.
- K will be between 0 and 100, inclusive.
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
100
100
Returns: 8
1
0
Returns: 1
2
0
Returns: 2
2
1
Returns: 2
3
0
Returns: 3
3
1
Returns: 3
4
0
Returns: 4
4
1
Returns: 3
4
2
Returns: 3
4
3
Returns: 3
100
0
Returns: 100
100
1
Returns: 51
100
2
Returns: 35
100
3
Returns: 27
100
4
Returns: 23
99
0
Returns: 99
99
1
Returns: 51
99
2
Returns: 35
99
3
Returns: 27
99
4
Returns: 23
83
81
Returns: 8
36
38
Returns: 7
22
63
Returns: 6
85
7
Returns: 14
11
41
Returns: 5
28
67
Returns: 6
56
3
Returns: 16
83
20
Returns: 9
19
66
Returns: 6
57
34
Returns: 7
14
72
Returns: 5
20
25
Returns: 6
73
89
Returns: 8
42
2
Returns: 16
34
26
Returns: 7
50
58
Returns: 7
29
6
Returns: 7
59
87
Returns: 7
23
31
Returns: 6
27
28
Returns: 6
55
41
Returns: 7
64
40
Returns: 7
21
26
Returns: 6
64
19
Returns: 8
94
93
Returns: 8
60
54
Returns: 7
99
67
Returns: 8
80
21
Returns: 9
45
100
Returns: 7
12
5
Returns: 5
99
91
Returns: 8
96
31
Returns: 8
22
69
Returns: 6
50
22
Returns: 7
11
66
Returns: 5
86
13
Returns: 10
55
0
Returns: 55
35
81
Returns: 7
33
70
Returns: 7
53
83
Returns: 7
14
18
Returns: 5
52
60
Returns: 7
2
19
Returns: 2
79
47
Returns: 8
21
97
Returns: 6
11
39
Returns: 5
84
77
Returns: 8
76
82
Returns: 8
80
91
Returns: 8
34
34
Returns: 7
100
7
Returns: 16
12
0
Returns: 12
31
4
Returns: 9
76
1
Returns: 39
62
9
Returns: 10
66
6
Returns: 13
86
0
Returns: 86
28
1
Returns: 15
44
9
Returns: 8
67
4
Returns: 16
45
9
Returns: 8
9
6
Returns: 5
71
3
Returns: 20
22
2
Returns: 9
72
3
Returns: 20
44
6
Returns: 10
19
3
Returns: 7
32
0
Returns: 32
94
0
Returns: 94
57
4
Returns: 14
43
0
Returns: 43
10
6
Returns: 5
90
2
Returns: 32
27
9
Returns: 7
56
5
Returns: 12
58
6
Returns: 12
84
1
Returns: 43
38
5
Returns: 9
5
8
Returns: 4
35
3
Returns: 11
77
4
Returns: 18
61
6
Returns: 12
83
0
Returns: 83
82
0
Returns: 82
2
4
Returns: 2
49
6
Returns: 10
32
8
Returns: 7
23
6
Returns: 7
7
9
Returns: 4
14
9
Returns: 5
72
8
Returns: 12
45
4
Returns: 12
71
8
Returns: 12
32
7
Returns: 7
36
4
Returns: 10
31
3
Returns: 10
38
2
Returns: 15
83
7
Returns: 14
77
8
Returns: 12
97
8
Returns: 14
3
5
Returns: 3
97
13
Returns: 11
46
6
Returns: 10
100
10
Returns: 13
3
3
Returns: 3
45
3
Returns: 14
1
100
Returns: 1
78
12
Returns: 10
100
24
Returns: 9
100
15
Returns: 11
2
2
Returns: 2
100
5
Returns: 20
87
53
Returns: 8
6
1
Returns: 4
64
8
Returns: 11
9
2
Returns: 5
15
2
Returns: 7
16
3
Returns: 6
10
2
Returns: 5