Problem Statement
On a piece of paper you draw a rectangular grid whose outer edges coincide with the edges of the paper. Every grid cell is exactly 1 unit by 1 unit. You can use scissors to cut out groups of cells along grid lines. The length of a cut is given as the number of units that the scissors need to travel along grid lines.
Given that the grid has dimensions width units by height units return the minimum length of a cut that cuts out exactly n cells from the piece of paper.
Definition
- Class:
- GridCut
- Method:
- cutLength
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int cutLength(int width, int height, int n)
- (be sure your method is public)
Constraints
- width will be between 1 and 1000 inclusive.
- height will be between 1 and 1000 inclusive.
- n will be between 1 and width*height inclusive.
Examples
4
2
3
Returns: 3
We cut along the dotted lines to obtain the blue cells. The lengths of the dotted lines add up to 3.
3
2
4
Returns: 2
100
1
43
Returns: 1
Here we will never need more than one cut to cut away any number of squares.
4
4
4
Returns: 4
The most economical way is to cut out a 2 by 2 square.
10
20
15
Returns: 8
4
5
20
Returns: 0
All cells are used, so no cuts are needed.
9
9
9
Returns: 6
396
603
71996
Returns: 397
261
401
1205
Returns: 70
6
267
971
Returns: 7
4
269
310
Returns: 5
135
804
82546
Returns: 136
1000
1000
500
Returns: 45
514
618
277461
Returns: 401
836
80
6227
Returns: 81
623
680
122618
Returns: 624
904
876
86595
Returns: 589
689
749
12472
Returns: 224
260
653
99069
Returns: 261
260
839
116298
Returns: 261
63
758
19883
Returns: 64
771
781
37861
Returns: 390
938
140
64689
Returns: 141
938
140
140
Returns: 24
938
140
14000
Returns: 140
938
140
938
Returns: 62
938
140
9380
Returns: 140
938
140
40334
Returns: 141
810
375
270590
Returns: 365
983
392
324966
Returns: 393
423
331
83478
Returns: 332
954
926
614814
Returns: 927
445
160
70780
Returns: 41
220
511
103946
Returns: 185
496
686
319121
Returns: 291
1000
1000
1000000
Returns: 0
347
234
81198
Returns: 0
1000
1000
999999
Returns: 2
1000
1000
999998
Returns: 3
1000
1000
249001
Returns: 998
1000
1000
999982
Returns: 9
100
100
9979
Returns: 10
4
2
5
Returns: 3
4
5
9
Returns: 5
1
1
1
Returns: 0
1000
1000
999999
Returns: 2
100
100
5
Returns: 5
6
5
26
Returns: 4
10
15
19
Returns: 9
100
100
9001
Returns: 64
10
10
100
Returns: 0
16
16
28
Returns: 11
5
5
24
Returns: 2
40
40
1580
Returns: 9
1000
1000
37267
Returns: 387
4
4
15
Returns: 2
5
6
26
Returns: 4
1000
1000
497
Returns: 45
100
100
20
Returns: 9
997
993
317239
Returns: 994
987
789
777404
Returns: 74
5
10
5
Returns: 5
100
100
9996
Returns: 4
1000
51
4000
Returns: 52
1000
1000
1000
Returns: 64
20
10
185
Returns: 8
1000
1000
999992
Returns: 6
10
10
91
Returns: 6
7
6
21
Returns: 7
1000
1000
900000
Returns: 633
2
2
3
Returns: 2
4
2
7
Returns: 2
7
12
76
Returns: 6
1000
500
470000
Returns: 347
1000
1000
888323
Returns: 669
2
1000
501
Returns: 3
1000
1000
5
Returns: 5
1000
1000
999998
Returns: 3
10
10
99
Returns: 2
23
37
836
Returns: 8
6
3
6
Returns: 3
20
20
97
Returns: 20
1000
1000
999942
Returns: 16
6
6
27
Returns: 6
4
5
19
Returns: 2
1000
1000
999499
Returns: 45
1000
1000
499
Returns: 45
100
100
9950
Returns: 15
11
11
120
Returns: 2
1000
1000
10
Returns: 7
1000
1000
17
Returns: 9
1000
1000
489001
Returns: 1001
100
100
7
Returns: 6
1
100
1
Returns: 1
1000
1000
999991
Returns: 6
1000
997
247011
Returns: 995
10
9
74
Returns: 8
100
1
43
Returns: 1
5
5
21
Returns: 4
1000
1000
750001
Returns: 1000
1000
1000
97
Returns: 20
20
20
375
Returns: 10
5
6
10
Returns: 5
7
5
16
Returns: 6
10
10
6
Returns: 5
100
100
9890
Returns: 21
1000
1000
490001
Returns: 1001
100
100
72
Returns: 17
6
6
20
Returns: 7
10
100
999
Returns: 2
1000
1000
999982
Returns: 9
100
100
9979
Returns: 10
4
2
5
Returns: 3
4
5
9
Returns: 5
1
1
1
Returns: 0
1000
1000
999999
Returns: 2
100
100
5
Returns: 5
6
5
26
Returns: 4
10
15
19
Returns: 9
100
100
9001
Returns: 64
10
10
100
Returns: 0
16
16
28
Returns: 11
5
5
24
Returns: 2
40
40
1580
Returns: 9
1000
1000
37267
Returns: 387
4
4
15
Returns: 2
5
6
26
Returns: 4
1000
1000
497
Returns: 45
100
100
20
Returns: 9
997
993
317239
Returns: 994
987
789
777404
Returns: 74
5
10
5
Returns: 5
100
100
9996
Returns: 4
1000
51
4000
Returns: 52
1000
1000
1000
Returns: 64
20
10
185
Returns: 8
1000
1000
999992
Returns: 6
10
10
91
Returns: 6
7
6
21
Returns: 7
1000
1000
900000
Returns: 633
2
2
3
Returns: 2
4
2
7
Returns: 2
7
12
76
Returns: 6
1000
500
470000
Returns: 347
1000
1000
888323
Returns: 669
2
1000
501
Returns: 3
1000
1000
5
Returns: 5
1000
1000
999998
Returns: 3
10
10
99
Returns: 2
23
37
836
Returns: 8
6
3
6
Returns: 3
20
20
97
Returns: 20
1000
1000
999942
Returns: 16
6
6
27
Returns: 6
4
5
19
Returns: 2
1000
1000
999499
Returns: 45
1000
1000
499
Returns: 45
100
100
9950
Returns: 15
11
11
120
Returns: 2
1000
1000
10
Returns: 7
1000
1000
17
Returns: 9
1000
1000
489001
Returns: 1001
100
100
7
Returns: 6
1
100
1
Returns: 1
1000
1000
999991
Returns: 6
1000
997
247011
Returns: 995
10
9
74
Returns: 8
100
1
43
Returns: 1
5
5
21
Returns: 4
1000
1000
750001
Returns: 1000
1000
1000
97
Returns: 20
20
20
375
Returns: 10
5
6
10
Returns: 5
7
5
16
Returns: 6
10
10
6
Returns: 5
100
100
9890
Returns: 21
1000
1000
490001
Returns: 1001
100
100
72
Returns: 17
6
6
20
Returns: 7
10
100
999
Returns: 2