TopCoder Statistics - Problem Statement

Problem Statement

We install marble countertops. The marble comes in a standard width but varying lengths. It is very difficult to cut the marble -- we have a special machine that cuts a length of marble into two pieces, one of which must be exactly k feet long. A piece that is no bigger than k cannot be cut.


int[] stock contains the lengths of marble that we have on hand, and int[] 
orders contains the lengths that our customers have ordered. Given k, stock,
and orders, return the minimum number of cuts
needed to satisfy all our customers. If it is not possible, return -1.

Definition

Class:: MarbleTop
Method:: minCuts
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int minCuts(int k, int[] stock, int[] orders)
(be sure your method is public)

Constraints

k will be between 1 and 40, inclusive.
stock and orders will each contain between 1 and 50 elements, inclusive.
Each element of stock and of orders will be between 1 and 40, inclusive.

Examples

5

{5,3,11}

{10,3,5}

Returns: -1

There is no way to deliver a piece of length 10. The only sizes we could deliver are 11,6,5,3,1.
5

{5,3,11}

{6,6,5}

Returns: -1

We can deliver one length of 6 and a length of 5 but not the second 6.
1

{7,6,2,1}

{3,1,1,1,1,1,1}

Returns: 4

Cut the 6 into a 5 and 1, cut the 5 into a 4 and 1, cut the 4 into a 3 and 1. Now we have 7, 3, 2, and four 1's. Cut the 2 and we have (in addition to the 7) a 3 and 6 1's as needed.
6

{4}

{20,5,11}

Returns: -1
6

{8,16,6,37,11,21}

{4,6,6,6}

Returns: 2
1

{4}

{2}

Returns: 2
3

{6,8,10,10,4,3,9,4}

{3,10,5}

Returns: 1
3

{2,3,10,7,10,8,10,9}

{3,3,3,3,3,3,3,9,10}

Returns: 6
1

{6,3,5,1,1}

{1,5,1,6,3}

Returns: 0
2

{1,5,1,6,3}

{6,3,5,1,1}

Returns: 0
2

{1,5,1,6,3,3,6}

{6,3,5,1,1,2,2,2}

Returns: 2
2

{1,5,1,6,3,3,6}

{2,6,3,5,1,1,2,2,2}

Returns: 3
4

{15,7,12,16,11,6,37,2,37}

{7,6,5,4,3,2,1}

Returns: 19
4

{15,7,12,16,11,6,37,2,37}

{7,6,5,4,3,2,1,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}

Returns: 21
40

{37,12,18}

{12,18,40}

Returns: -1
1

{40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40}

{17,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,2},

Returns: 1153
2

{8, 8, 8 }

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

Returns: 8
5

{10, 15, 20 }

{5, 5, 5, 5, 5, 5 }

Returns: 4
5

{9, 8, 7 }

{3, 5 }

Returns: 1
3

{2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }

{3, 3, 3 }

Returns: 2
5

{39, 13, 10, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 5 }

{5, 5, 5, 5, 5 }

Returns: 3
2

{5, 8 }

{2, 2, 2, 2 }

Returns: 3
1

{40, 39, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 33, 33, 32, 32, 31, 31, 30, 30, 29, 29, 28, 28, 27, 27, 26, 26, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 }

{11, 11, 12, 12, 13, 14, 14, 9, 8, 7, 6, 4, 3, 2, 1, 1, 1, 2, 2 }

Returns: 70
1

{1 }

{2 }

Returns: -1
3

{13, 2, 25, 30, 30, 9 }

{1, 2, 1, 3, 3, 3 }

Returns: 12
2

{3 }

{2 }

Returns: 1
1

{7, 3, 8, 3, 3, 3, 3, 3, 3, 3 }

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Returns: 12
3

{5, 6, 7, 8, 9, 10 }

{3, 3, 3, 3, 3, 3, 3, 3, 4, 5 }

Returns: 6
2

{2, 3, 4 }

{1, 2, 2 }

Returns: 1
3

{5, 6, 5 }

{3, 3, 3 }

Returns: 2
7

{40, 40, 39, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 33, 33, 32, 32, 31, 31, 30, 30, 29, 29, 28, 28, 27, 27, 26, 26, 25, 25, 24, 24, 23, 23, 22, 22, 21, 21, 20, 20 }

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

Returns: 47
5

{31, 36, 37, 32, 39, 34, 9, 11, 15, 19, 20 }

{21, 26, 22, 27, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

Returns: 10
4

{8, 12, 4, 8, 39 }

{4, 4, 4, 4, 4, 4, 7 }

Returns: 8
3

{6, 8, 9 }

{3, 3, 3, 3, 3 }

Returns: 3
10

{25, 20 }

{10, 15 }

Returns: 1
5

{14, 16, 17, 19, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 13, 20 }

{5, 5, 5, 5, 5, 11, 2 }

Returns: 5
3

{7, 9, 9 }

{3, 3, 3 }

Returns: 2
5

{11 }

{5, 5 }

Returns: 2
1

{7, 6, 2, 1 }

{3, 1, 1, 1, 1, 1, 1, 1, 1 }

Returns: 6
5

{10, 6 }

{5, 1 }

Returns: 1
3

{10 }

{3 }

Returns: 1
2

{40, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 40 }

{4, 4 }

Returns: 36
3

{3, 7, 4 }

{3, 3, 3, 3 }

Returns: 3
10

{21, 21, 32, 33, 20, 20, 30, 30, 33 }

{11, 13, 13, 21, 22, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

Returns: 8
5

{15, 1 }

{10, 5 }

Returns: 1
30

{40, 40, 40, 40, 40, 40, 40, 40 }

{10, 30, 30, 30, 30, 30, 30, 30, 30 }

Returns: 8
2

{7 }

{2, 2, 2 }

Returns: 3
5

{15, 8 }

{5, 5, 5 }

Returns: 2
10

{20 }

{10, 10, 10 }

Returns: -1
5

{6, 6, 10 }

{5, 5 }

Returns: 1
2

{3, 3, 4 }

{1, 2, 2, 1 }

Returns: 2
5

{23 }

{3, 20 }

Returns: -1
3

{4, 5 }

{2, 3 }

Returns: 1

Statistics

Problem Statement for "MarbleTop"

Problem Statement

Definition

Constraints

Examples