Jumping

SRM 633 · 2014-08-25 · by cgy4ever

SRM 633 · 2014-08-25 · by cgy4ever · Geometry

Show categories

Class Name: Jumping

Return Type: String

Method Name: ableToGet

Arg Types: (int, int, vector<int>)

Problem Statement

Frog Suwako lives on a two-dimensional plane. She likes to jump. Currently, she is located in the point (0, 0). She would like to reach the point (x, y). You are given the ints x and y.

Suwako wants to reach the desired destination in a specific way: using a series of jumps with pre-determined lengths. You are given these lengths in a int[] jumpLenghts. For example, if jumpLengths = { 2, 5 }, Suwako must make a jump of length exactly 2, followed by a jump of length exactly 5.

Note that Suwako can jump onto arbitrary points in the plane, they are not required to have integer coordinates. Return "Able" (quotes for clarity) if Suwako is able to reach her desired destination from (0, 0) using the desired sequence of jump lengths. Otherwise, return "Not able".

Constraints

x will be between -1,000 and 1,000, inclusive.
y will be between -1,000 and 1,000, inclusive.
len will contain between 1 and 50 elements, inclusive.
Each element in len will be between 1 and 1,000, inclusive.

Examples

5
4
{2, 5}
Returns: "Able"

One possibility is to jump from (0, 0) to (2, 0), and then from (2, 0) to (5, 4).

3
4
{4}
Returns: "Not able"

The distance from (0, 0) to (3, 4) is 5. You cannot get there using a single jump of length 4 - it is too short.

3
4
{6}
Returns: "Not able"

The distance from (0, 0) to (3, 4) is 5. You cannot get there using a single jump of length 6 - it is too long.

0
1
{100, 100}
Returns: "Able"

Here, one possible solution looks as follows: Let t = sqrt(100*100 - 0.5*0.5). Suwoko will make her first jump from (0, 0) to (t, 0.5), and her second jump from (t, 0.5) to (0, 1).

300
400
{500}
Returns: "Able"

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

Coding Area

Language: C++17 · define a public class Jumping with a public method string ableToGet(int x, int y, vector<int> jumpLengths) · 139 test cases · 2 s / 256 MB per case