Connection Status:
Competition Arena > MagicalGirlLevelOneDivOne

MagicalGirlLevelOneDivOne

SRM 514 · 2011-05-25 · by wrong

SRM 514 · 2011-05-25 · by wrong · Simple Math, Simple Search, Iteration
Class Name: MagicalGirlLevelOneDivOne
Return Type: String
Method Name: isReachable
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

Magical Girls are girls who have magical powers. They fight against evil witches to protect the Earth.


You, one of the Magical Girls, are at point (0, 0) of the plane. You find another Magical Girl at (x, y) and she seems to be injured. So you decide to go to point (x, y) to help her.


You can move only by n-knight jump. For a positive integer n, the n-knight jump is 8 types of moves. You can go from (0, 0) to (n, 1), (n, -1), (-n, 1), (-n, -1), (1, n), (-1, n), (1, -n) or (-1, -n) by using n-knight jump once.


You are given a int[] jumpTypes containing the valid n-knight jumps you can perform. You can only use an n-knight jump if jumpTypes contains n. Return "YES" if you can reach (x, y) with the n-knight jumps of given numbers. Otherwise return "NO" (all quotes for clarity). You can use each n-knight jump as many times as you want.

Constraints

  • jumpTypes will contain between 1 and 50 elements, inclusive.
  • Each element of jumpTypes will be between 1 and 1,000,000,000, inclusive.
  • All elements of jumpTypes will be distinct.
  • x and y will each be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
{2}
5
4
Returns: "YES"

(0, 0) -> (2, 1) -> (4, 2) -> (5, 4)

1)
{3}
5
4
Returns: "NO"
2)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
1000000000
-999999999
Returns: "YES"
3)
{999999999}
999999999
0
Returns: "NO"
4)
{763829405,204573737,912557271,586200617,116009837,383693699,85201693,150307641,176862787,681790087,112704509,42370477,700440969,457606137,82420091,350831113,205641533,93275369,256974597,647430443,32346817}
207303341
-975372680
Returns: "NO"

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

Coding Area

Language: C++17 · define a public class MagicalGirlLevelOneDivOne with a public method string isReachable(vector<int> jumpTypes, int x, int y) · 161 test cases · 2 s / 256 MB per case

Submitting as anonymous