JOIN
Get Time

   Problem Statement  

 Problem Statement for RectangleCovering

Problem Statement

    

There is a rectangular hole in the ground. You are given the dimensions of this rectangle: ints holeH and holeW.

You have a collection of rectangular boards. You are given their dimensions as two int[]s: boardH and boardW. For each valid i, you have a rectangular board with dimensions boardH[i] and boardW[i]. You would like to cover the hole completely, using as few of these boards as possible.

There are some rules you must follow when covering the hole:

  • The boards may overlap arbitrarily.
  • Together, the boards must cover the entire hole.
  • You may rotate each board, but you must place it so that the sides of the board are parallel to the sides of the hole.
  • All corners of each board must be strictly outside the hole. (That is, they are not allowed to lie on the boundary of the hole, either.)

If you can cover the hole using the boards you have, return the smallest number of boards that is sufficient to cover the hole. Otherwise, return -1.

 

Definition

    
Class:RectangleCovering
Method:minimumNumber
Parameters:int, int, int[], int[]
Returns:int
Method signature:int minimumNumber(int holeH, int holeW, int[] boardH, int[] boardW)
(be sure your method is public)
    
 

Constraints

-holeH and holeW will be between 1 and 1,000,000,000, inclusive.
-boardH and boardW will contain between 1 and 50 elements, inclusive.
-boardH and boardW will contain the same number of elements.
-Each element of boardH and boardW will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
5
5
{8,8,8}
{2,3,4}
Returns: 2
You cannot cover this hole completely by using a single board. You can cover it by taking any two boards and placing them side by side.
1)
    
10
10
{6,6,6,6}
{6,6,6,6}
Returns: -1
These four boards cannot be used to cover the hole. This is because of the rule that all board corners must be outside the hole.
2)
    
5
5
{5}
{5}
Returns: -1
The corners of a board are not allowed to be on the boundary of the hole.
3)
    
3
5
{6}
{4}
Returns: 1
4)
    
10000
5000
{12345,12343,12323,12424,1515,6666,6789,1424,11111,25}
{1442,2448,42,1818,3535,3333,3456,7890,1,52}
Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 629 Round 1 - Division I, Level One