Problem Statement
A construction company recently ordered some boards of length desiredLength from a lumber company. By mistake, the lumber company instead delivered boards of length actualLength. The construction company doesn't have time to reissue the order, so instead they will cut and glue together the boards they have in order to form boards of the proper length.
The construction company needs desiredCount boards of length desiredLength. The have an effectively unlimited supply of boards of length actualLength. The construction company wants to use as few boards as possible. If there are multiple ways to use the same number of boards, they want to perform as few cuts as possible. Return the number of cuts they will perform.
Definition
- Class:
- BoardSplitting
- Method:
- minimumCuts
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int minimumCuts(int desiredLength, int desiredCount, int actualLength)
- (be sure your method is public)
Notes
- A board is a one-dimensional piece of wood. A single board of length L may be cut into two boards of length X and Y, provided X > 0, Y > 0, and X + Y = L. Two boards of length X and Y may be glued together to form a board of length X + Y.
Constraints
- desiredLength will be between 1 and 1000, inclusive.
- desiredCount will be between 1 and 1000, inclusive.
- actualLength will be between 1 and 1000, inclusive.
Examples
5
4
4
Returns: 3
We need 4 boards of length 5 each. We have an unlimited supply of boards of length 4. One solution is to cut one board into 4 pieces of length 1 each (using 3 cuts), then glue each piece to a board of length 4.
6
100
3
Returns: 0
No cuts are necessary.
500
5
1000
Returns: 3
We cut 3 boards in half.
314
159
26
Returns: 147
1
1
1
Returns: 0
1
1
1000
Returns: 1
1
1000
1
Returns: 0
1
1000
1000
Returns: 999
1000
1
1
Returns: 0
1000
1
1000
Returns: 0
1000
1000
1
Returns: 0
1000
1000
1000
Returns: 0
778
887
384
Returns: 883
336
794
916
Returns: 791
650
493
387
Returns: 492
28
363
422
Returns: 362
764
60
691
Returns: 60
427
541
927
Returns: 541
212
737
173
Returns: 733
430
568
369
Returns: 567
863
531
783
Returns: 531
136
68
124
Returns: 66
23
803
930
Returns: 803
168
70
59
Returns: 69
12
457
394
Returns: 455
374
230
43
Returns: 225
785
920
422
Returns: 918
325
199
538
Returns: 199
414
371
316
Returns: 369
981
92
527
Returns: 92
863
874
957
Returns: 874
282
997
171
Returns: 980
926
926
85
Returns: 916
337
337
506
Returns: 337
730
730
314
Returns: 726
125
125
896
Returns: 125
546
546
815
Returns: 546
435
435
365
Returns: 430
751
751
88
Returns: 743
277
277
179
Returns: 276
789
404
404
Returns: 403
652
400
400
Returns: 396
933
677
677
Returns: 676
369
13
13
Returns: 12
227
95
95
Returns: 94
540
571
571
Returns: 570
435
468
468
Returns: 465
602
903
903
Returns: 602
318
493
318
Returns: 0
757
302
757
Returns: 0
287
442
287
Returns: 0
690
445
690
Returns: 0
441
730
441
Returns: 0
118
98
118
Returns: 0
482
676
482
Returns: 0
928
568
928
Returns: 0
498
498
498
Returns: 0
354
354
354
Returns: 0
587
587
587
Returns: 0
966
966
966
Returns: 0
307
307
307
Returns: 0
3
4
2
Returns: 2
2
3
3
Returns: 2
978
999
121
Returns: 991
2
10
5
Returns: 8
7
9
9
Returns: 8
5
7
7
Returns: 6
2
7
5
Returns: 6
3
8
8
Returns: 7
3
5
8
Returns: 5
12
6
5
Returns: 5
3
10
10
Returns: 9
314
154
27
Returns: 149
6
3
4
Returns: 2
3
1000
1000
Returns: 999
3
60
40
Returns: 59
4
13
26
Returns: 12
31
511
17
Returns: 481
315
159
26
Returns: 153
7
3
15
Returns: 3
24
159
29
Returns: 154
20
3
12
Returns: 2
48
1000
500
Returns: 992
3
100
4
Returns: 75
999
782
567
Returns: 745
4
5
5
Returns: 4
10
1
3
Returns: 1
400
5
1000
Returns: 4
10
6
6
Returns: 4
4
3
6
Returns: 2
153
586
77
Returns: 579
4
6
6
Returns: 4
998
999
1000
Returns: 998
4
10
5
Returns: 8
987
453
566
Returns: 453