QuadraticJumping
SRM 802 · 2021-03-18 · by misof
Problem Statement
You are on a straight line that is infinite in both directions. Your starting location is coordinate 0 and your goal is to reach coordinate goal using as few jumps as possible.
Your jumps are numbered starting from 1. The length of jump x must be exactly x^2 (x squared). For each jump you get to choose the direction in which you jump (left or right).
Return the smallest number of jumps needed to reach the given goal, or -1 if the goal cannot be reached.
Constraints
- goal will be between 1 and 10^16, inclusive.
14 Returns: 3
Jump right three times: from 0 to 1, from 1 to 1+4 = 5, and from 5 to 5+9 = 14.
28 Returns: 4
Jump left, right, right, right: 0 to -1 to 3 to 12 to 28.
7 Returns: 6
Jump left, twice right, twice left, right: 0 to -1 to 3 to 12 to -4 to -29 to 7.
333383335000 Returns: 10000
Ten thousand jumps to the right.
1 Returns: 1
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuadraticJumping with a public method long long jump(long long goal) · 128 test cases · 2 s / 256 MB per case