Connection Status:
Competition Arena > GetThemAll

GetThemAll

SRM 207 · 2004-08-10 · by Olexiy

SRM 207 · 2004-08-10 · by Olexiy · Brute Force, Math
Class Name: GetThemAll
Return Type: int
Method Name: quickKnight
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You have an infinite chessboard with several black pieces placed on it. You have a white knight on the same chessboard, which starts from the (0, 0) point, and you want to know how fast it can capture all the black pieces.

You will be given a String[] pieces, containing information about black pieces. Each element of pieces will be formatted as "X Y", where X and Y are integer numbers between -1000000 and 1000000, inclusive. Your method should return the minimum number of moves needed to capture all the black pieces, assuming none of them move.

Notes

  • A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if a knight is at (0,0), it may move to (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2).
  • The knight starts at (0, 0).

Constraints

  • pieces will contain between 0 and 9 elements, inclusive.
  • Each element of pieces will be formatted as "X Y", where X and Y are integer numbers without extra leading zeroes.
  • X and Y will be between -1000000 and 1000000, inclusive, in each element of pieces.
  • All elements of pieces will be different.
  • There are no pieces at (0, 0).
Examples
0)
{}
Returns: 0

An empty chessboard.

1)
{"1 2"}
Returns: 1

Just one move.

2)
{"2 -1", "2 1", "-2 1", "-2 -1"}
Returns: 7

The knight should return to the starting position several times.

3)
{"0 1"}
Returns: 3

The knight needs 3 jumps to move to any adjacent cell.

4)
{"0 7", "7 7", "7 0"}
Returns: 15
7)
{"-1000000 -1000000", "1000000 1000000", "1000000 -1000000", "-1000000 1000000"}
Returns: 3666668

One really big square, containing the maximal possible distance between two pieces.

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

Coding Area

Language: C++17 · define a public class GetThemAll with a public method int quickKnight(vector<string> pieces) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous