PeriodicJumping
SRM 633 · 2014-08-25 · by Vasyl[alphacom]
SRM 633 · 2014-08-25 · by Vasyl[alphacom] · Math
Problem Statement
Problem Statement
Frog Suwako lives on a two-dimensional plane.
Currently, she is located in the point (0, 0).
She would like to reach the point (x, 0).
Suwako jumps in a peculiar way: her jump lengths repeat in a periodic fashion. Theint[] jumpLengths contains one period of her jump lengths, starting with the length of the first jump she will make.
For example, if jumpLengths = { 2, 5 }, Suwako's jump lengths will be 2, 5, 2, 5, 2, 5, ...
Note that Suwako can jump onto arbitrary points in the plane, they are not required to have integer coordinates.
You are given theint x and the int[] jumpLengths.
Return the smallest non-negative integer j such that Suwako can reach the desired destination after j jumps.
If there is no such j, return -1 instead.
Suwako jumps in a peculiar way: her jump lengths repeat in a periodic fashion. The
You are given the
Constraints
- x will be between -1,000,000,000 and 1,000,000,000, inclusive.
- jumpLengths will contain between 1 and 50 elements, inclusive.
- Each element in len will be between 1 and 1,000,000,000, inclusive.
Examples
0)
15
{1,2,3,4,5,6,7,8,9,10}
Returns: 5
In 4 jumps Suwako cannot get far enough. In 5 jumps she can reach the destination as follows: (0,0) -> (1,0) -> (3,0) -> (6,0) -> (10,0) -> (15,0).
1)
5
{5}
Returns: 1
One jump is enough, since the distance between (0,0) and (5,0) is exactly 5.
2)
1
{10}
Returns: 2
Here Suwako needs two jumps. One possible solution is to land at (0.5, sqrt(10*10-0.5*0.5)) after the first jump.
3)
-10
{2,3,4,500,6,7,8}
Returns: 11
4)
-1000000000
{1}
Returns: 1000000000
Submissions are judged against all 215 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PeriodicJumping with a public method int minimalTime(int x, vector<int> jumpLengths) · 215 test cases · 2 s / 256 MB per case