Connection Status:
Competition Arena > KnightOfIntegerland

KnightOfIntegerland

TCO12 Wildcard Round · 2012-03-27 · by cgy4ever

TCO12 Wildcard Round · 2012-03-27 · by cgy4ever · Math
Class Name: KnightOfIntegerland
Return Type: String
Method Name: able
Arg Types: (int, int, int)
Problem Statement

Problem Statement

You are a knight of the Integerland. You are located at (0, 0) and you want to go to (x, y). You move in a way that is similar to a chess knight. You can be described by a int d. In each step, you may move to any point such that both its coordinates are integers, and its Euclidean distance from your current point is precisely sqrt(d).
You are given the ints d, x, and y. Return "YES" if you can arrive at (x, y) in a finite number of moves, and "NO" otherwise.

Notes

  • In the problem statement, sqrt(d) denotes the square root of d.
  • The Euclidean distance between two points (x1, y1) and (x2, y2) is equal to sqrt((x1-x2)^2 + (y1-y2)^2).
  • There is no limit on the coordinates of points visited during your journey. In particular, they are allowed to be outside of the rectangle with corners (0, 0) and (x, y).

Constraints

  • d will be between 1 and 1,000,000,000, inclusive.
  • x will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
25
1
0
Returns: "YES"

The distance covered by each of your steps must be sqrt(25)=5. You can reach (1, 0) in this way: (0, 0) -> (3, 4) -> (6, 0) -> (1, 0).

1)
25
2276
-9059
Returns: "YES"

From any point (x, y) we can reach (x+1, y) as shown in Example 0. Also, from any point (x, y) we can reach (x, y-1) using a similar sequence of moves. Hence, it is possible to get from (0, 0) to (2276,-9059) by repeating the first sequence of moves 2276 times and then the second sequence of moves 9059 times.

2)
5
58585858
85858585
Returns: "YES"

For d=5 you move like a chess knight. It is well known that the chess knight can reach any cell on an infinite chessboard.

3)
4
47474747
74747474
Returns: "NO"

It's easy to see that for any point (x, y) you can reach, x and y must be both even.

4)
169
2
0
Returns: "YES"

One of the solutions is: (0, 0) -> (13, 0) -> (1, 5) -> (14, 5) -> (2, 0).

5)
3
1
1
Returns: "NO"

In this case you can't achieve any integer point other than (0, 0).

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

Coding Area

Language: C++17 · define a public class KnightOfIntegerland with a public method string able(int d, int x, int y) · 200 test cases · 2 s / 256 MB per case

Submitting as anonymous