ManySquares
SRM 627 · 2014-06-16 · by fsouza
SRM 627 · 2014-06-16 · by fsouza · Geometry, Simple Math
Problem Statement
Problem Statement
You found a box from an old game.
The box contains a lot of sticks and a manual.
Frustrated by the fact the manual was unreadable, you decided to invent your own game with the sticks.
In your game, the goal is to use the sticks to build as many squares as possible.
There are only two rules:
int[] sticks.
The elements of sticks are the lengths of the sticks you have.
Return the maximum number of squares you can make.
- Each stick can only be used in one square.
- Each square must consist of exactly 4 sticks. That is, you cannot combine two or more sticks to create one side of the square.
Notes
- If you can't make any square, return 0.
Constraints
- sticks will contain between 1 and 50 elements.
- Each element of sticks will be between 1 and 1000, inclusive.
Examples
0)
{1,1,2,2,1,1,2}
Returns: 1
You can build a square with side 1.
1)
{3, 1, 4, 4, 4, 10, 10, 10, 10}
Returns: 1
You can build a square with side 10. You cannot build a square with side 4. (Note that you are not allowed to use 3+1 instead of a 4.)
2)
{1,2,3,4,1,2,3,4,1,2,3,1,2,3,4,1,2,3,3,3}
Returns: 3
3)
{1,1,1,2,2,2,3,3,3,4,4,4}
Returns: 0
Sometimes you can't make any square.
4)
{43}
Returns: 0
119)
{2,2,4,4,8,8}
Returns: 0
You are also not allowed to break the sticks.
Submissions are judged against all 161 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ManySquares with a public method int howManySquares(vector<int> sticks) · 161 test cases · 2 s / 256 MB per case