Connection Status:
Competition Arena > MarbleTop

MarbleTop

TCCC07 Round 1B · 2007-07-30 · by dgoodman

TCCC07 Round 1B · 2007-07-30 · by dgoodman · Search, Sorting
Class Name: MarbleTop
Return Type: int
Method Name: minCuts
Arg Types: (int, vector<int>, vector<int>)
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.

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
0)
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.

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.

2)
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.

3)
6
{4}
{20,5,11}
Returns: -1
4)
6
{8,16,6,37,11,21}
{4,6,6,6}
Returns: 2

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MarbleTop with a public method int minCuts(int k, vector<int> stock, vector<int> orders) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous