Problem Statement
The time limit for this problem is 5 seconds.
Bob is trying to build a brick tower of height H. Currently, he has a tower of height B.
Being the power-macho he is, Bob can break the tower he has at any time. Whenever he breaks the tower, he divides it into multiple equal parts of integer height. He then keeps one of those parts as his new tower and he discards the rest. (The parts of the tower discarded this way are lost and cannot be reused in the future.)
He can also make his tower taller by buying new bricks and stacking them on top of the tower. The brick shop at the local marketplace has a sale on bricks, offering a package of K bricks for just a single dollar. The store has a sufficient supply of these to arrange as many packages as Bob wants to buy.
Find and return the minimum cost Bob has to pay in order to transform his tower from its beginning height B to the desired height H. Return -1 if itâs impossible to make a tower of height H.
Definition
- Class:
- BobtheBuilder
- Method:
- minimumPrice
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int minimumPrice(int B, int K, int H)
- (be sure your method is public)
Constraints
- B, H, K will be between 1 and 1000, inclusive.
Examples
65
5
6
Returns: 1
Bob's initial brick tower is of height 65, and he wants one with a height of 6. As he cannot break the tower into equal pieces such that all of them have height 6, he cannot achieve his goal for free. He can achieve his goal for $1. In order to do that, he can first break the tower into 65 smaller towers each of height 1, discard all but one of them, and then buy one stack of 5 bricks for $1 and add them to the top of his current tower.
3
2
2
Returns: -1
Bob's brick tower has an initial height of 3. Note that the height is odd. Whenever he breaks such a tower into pieces, the new height will also be odd. Additionally, the number of bricks in a package he can buy is even. Whenever he adds two more bricks to a tower with an odd height, the height will remain odd. Thus, there is no way Bob can make a tower of height 2, which is an even number.
5
6
79
Returns: 13
Bob's current brick tower has a height of 5 while he wants it to be of height 79. Since the current height is smaller than the required height, Bob will need to buy bricks to increase the height. Buying 12 sets of size 6 will lead to a height of 5 + 6*12 = 77 falling short of the required height while purchasing 13 sets will overshoot, making it 5 + 6*13 = 83. Notice that Bob will require at least 13 sets to have the required height no matter what other operation he performs. As 13*6 = 78 falls just 1 short of 79, Bob's optimal way is to first divide tower of height 5 into 5 smaller towers of height 1, then pick one of them and place 13 sets of 6 bricks on it to achieve the desired height.
94
1
25
Returns: 2
Starting from 94, there are many ways in which Bob can achieve a height of 25: 94 + 1*6 = 100 -> 25 (buys 6 bricks placing all of them on top, and then breaking it into 4 equal pieces of height 25) 94 -> 47 -> 47 + 3 = 50 -> 25 (first breaks into 2 halves, buys 3 bricks and places them on top of one of the half, and then breaks that half again into 2 equal halves of height 25) 94 -> 47 -> 47 + 1 = 48 -> 24 -> 24 + 1 = 25 (first breaks into 2 halves, then buys 1 brick to make one of the half of height 48, breaks that half into 2 further halves, finally buying 1 more brick to place on top of one of them for achieving the required height) The last solution shown is optimal.
289
5
17
Returns: 0
Bob can simply break the tower into 17 smaller towers each of height 17 (since 17*17 = 289) and then keep one of them.
90
1
82
Returns: 37
401
780
779
Returns: 30
86
1
95
Returns: 9
18
2
87
Returns: 39
43
5
53
Returns: 2
28
3
93
Returns: -1
47
7
45
Returns: 6
97
4
20
Returns: -1
86
3
94
Returns: 17
14
5
88
Returns: 18
39
3
46
Returns: 11
69
2
76
Returns: -1
83
8
6
Returns: -1
28
10
35
Returns: -1
78
9
61
Returns: 6
81
2
68
Returns: -1
6
3
6
Returns: 0
32
9
92
Returns: 10
93
1
17
Returns: 2
99
6
54
Returns: -1
59
2
70
Returns: -1
50
6
1
Returns: 0
831
47
209
Returns: 2
20
274
176
Returns: 5
693
526
310
Returns: -1
733
49
941
Returns: 20
629
748
415
Returns: 10
6
847
757
Returns: 6
341
200
823
Returns: 6
718
761
177
Returns: 4
329
841
723
Returns: 5
786
815
49
Returns: 3
307
761
717
Returns: 7
29
580
69
Returns: 3
289
404
321
Returns: 6
719
191
578
Returns: 4
600
927
411
Returns: 4
778
172
820
Returns: -1
688
796
943
Returns: 2
56
233
152
Returns: 5
127
220
774
Returns: -1
516
992
136
Returns: -1
1
13
856
Returns: 68
1
31
870
Returns: 29
1
43
990
Returns: 23
1
91
990
Returns: 15
1
990
193
Returns: 13
1
996
199
Returns: 13
1
990
257
Returns: 15
1
910
303
Returns: 18
1
990
331
Returns: 21
1
990
497
Returns: 22
1
990
559
Returns: 23
1
966
769
Returns: 24
1
780
779
Returns: 30
883
840
839
Returns: 40
1
840
809
Returns: 29
1
840
839
Returns: 40
13
840
839
Returns: 40
17
840
839
Returns: 40
19
840
839
Returns: 40
23
840
839
Returns: 40
31
840
839
Returns: 40
999
980
979
Returns: 20
998
840
839
Returns: 38
991
840
839
Returns: 40
499
840
839
Returns: 40
857
840
839
Returns: 40
1
1
1000
Returns: 999
5
9
100
Returns: 11
129
13
791
Returns: 62
987
5
78
Returns: 2
786
5
76
Returns: 7
5
9
35
Returns: 5
20
5
3
Returns: 1
20
9
7
Returns: 1