CrouchingAmoebas
SRM 493 · 2010-11-01 · by maksay
SRM 493 · 2010-11-01 · by maksay · Geometry, Search
Problem Statement
Problem Statement
Little Romeo is being attacked by amoebas crouching on the floor of his room. His room can be represented as a Cartesian plane, and the amoebas can be represented as points on that plane. You are given int[] s x and y, where the i-th amoeba is at point (x[i], y[i]). Multiple amoebas can exist at the same coordinates.
To escape, Romeo must destroy as many amoebas as possible. He has two powers at his disposal. First, he can choose one amoeba and move it along either of the axes by one unit. He can do this at most T times, choosing any amoeba each time. Then, he can choose an AxA square on the plane and use his SuperAmoebaDestroyer to destroy all amoebas inside or on the border of that square. The square must have sides parallel to the axes.
Return the maximum number of amoebas Romeo can destroy.
To escape, Romeo must destroy as many amoebas as possible. He has two powers at his disposal. First, he can choose one amoeba and move it along either of the axes by one unit. He can do this at most T times, choosing any amoeba each time. Then, he can choose an AxA square on the plane and use his SuperAmoebaDestroyer to destroy all amoebas inside or on the border of that square. The square must have sides parallel to the axes.
Return the maximum number of amoebas Romeo can destroy.
Constraints
- x and y will each contain between 1 and 30 elements, inclusive.
- x and y will have the same number of elements.
- Each element of x and y will be between -1,000,000,000 and 1,000,000,000, inclusive.
- A will be between 1 and 1,000,000,000, inclusive.
- T will be between 1 and 15, inclusive.
Examples
0)
{0,0}
{0,1}
1
1
Returns: 2
All the amoebas are already in a 1x1 square, so Romeo can immediately use the SuperAmoebaDestroyer without having to move any amoebas.
1)
{0,1,2}
{1,2,0}
1
1
Returns: 2
Romeo can't put all the amoebas in a 1x1 square in one move.
2)
{0,1,2}
{1,2,0}
1
2
Returns: 3
Moving the last amoeba left and then up puts all the amoebas in the 1x1 square with lower left corner at (0,1).
3)
{0,1,2}
{1,2,0}
2
1
Returns: 3
4)
{0,0,3,3}
{0,3,0,3}
2
4
Returns: 4
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CrouchingAmoebas with a public method int count(vector<int> x, vector<int> y, int A, int T) · 73 test cases · 2 s / 256 MB per case