PeriodicJumping | Topcoder Archive

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. The int[] 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 the int 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.

Definition

Class:: PeriodicJumping
Method:: minimalTime
Parameters:: int, int[]
Returns:: int
Method signature:: int minimalTime(int x, int[] jumpLengths)
(be sure your method is public)

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

```
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).
```
5
```
```
{5}
```
```
Returns: 1
```
One jump is enough, since the distance between (0,0) and (5,0) is exactly 5.
```
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.
```
-10
```
```
{2,3,4,500,6,7,8}
```
```
Returns: 11
```
```
-1000000000
```
```
{1}
```
```
Returns: 1000000000
```
```
0
```
```
{19911120}
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.