RectangleCovering
SRM 629 · 2014-07-26 · by dreamoon
Problem Statement
There is a rectangular hole in the ground.
You are given the dimensions of this rectangle:
You have a collection of rectangular boards.
You are given their dimensions as two
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.
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.
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.
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.
5
5
{5}
{5}
Returns: -1
The corners of a board are not allowed to be on the boundary of the hole.
3
5
{6}
{4}
Returns: 1
10000
5000
{12345,12343,12323,12424,1515,6666,6789,1424,11111,25}
{1442,2448,42,1818,3535,3333,3456,7890,1,52}
Returns: 3
Submissions are judged against all 198 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RectangleCovering with a public method int minimumNumber(int holeH, int holeW, vector<int> boardH, vector<int> boardW) · 198 test cases · 2 s / 256 MB per case