Connection Status:
Competition Arena > TheTower

TheTower

SRM 423 · 2008-10-28 · by Vasyl[alphacom]

SRM 423 · 2008-10-28 · by Vasyl[alphacom] · Search
Class Name: TheTower
Return Type: int[]
Method Name: count
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

N checkers are placed on an infinitely large board. The i-th checker is in the cell at row x[i], column y[i]. There can be more than one checker in the same cell. A move consists of taking one checker and moving it one cell up, down, left or right.

Return a int[] containing exactly N elements, where the i-th element (0-based) is the minimum number of moves necessary to end up with at least i+1 checkers in the same cell.

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x will be between 1 and 1,000,000, inclusive.
  • Each element of y will be between 1 and 1,000,000, inclusive.
Examples
0)
{1, 2, 4, 9}
{1, 1, 1, 1}
Returns: {0, 1, 3, 10 }

Here is one possible way to get the minimal number of moves: for 1 checker: do nothing for 2 checkers: put the first two checkers at cell (1, 1) for 3 checkers: put the first three checkers at cell (2, 1) for 4 checkers: put all the checkers at cell (3, 1)

1)
{15, 15, 14, 16}
{14, 16, 15, 15}
Returns: {0, 2, 3, 4 }

Whenever we need to have more than one checker in a single cell, we can put them in cell (15, 15).

2)
{4, 4}
{7, 7}
Returns: {0, 0 }

They are already at the same cell.

3)
{8, 1, 9, 9, 7}
{7, 7, 7, 7, 10}
Returns: {0, 0, 1, 6, 13 }
4)
{3, 3, 6, 1, 5, 7}
{1, 9, 9, 2, 1, 6}
Returns: {0, 2, 5, 13, 21, 31 }

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

Coding Area

Language: C++17 · define a public class TheTower with a public method vector<int> count(vector<int> x, vector<int> y) · 167 test cases · 2 s / 256 MB per case

Submitting as anonymous