JumpFurther
SRM 587 · 2013-06-25 · by ir5
Problem Statement
Little Fox Jiro is standing at the bottom of a long flight of stairs. The bottom of the stairs has number 0, the bottommost step has number 1, the next step has number 2, and so on. The staircase is so long that Jiro is guaranteed not to reach its top.
Jiro will now perform N consecutive actions. The actions are numbered 1 through N, in order. When performing action X, Jiro chooses between two options: either he does nothing, or he jumps exactly X steps up the stairs. In other words, if Jiro starts performing action X standing on step Y, he will end it either on step Y, or on step Y+X.
For example, if N=3, Jiro will make three consecutive choices: whether or not to jump 1 step upwards, 2 steps upwards, and then 3 steps upwards.
One of the steps is broken. The number of this step is badStep. Jiro cannot jump onto this step.
You are given the
Constraints
- N will be between 1 and 2,000, inclusive.
- badStep will be between 1 and 4,000,000, inclusive.
2 2 Returns: 3
The optimal strategy is to jump upwards twice: from step 0 to step 1, and then from step 1 to step 3. This trajectory avoids the broken step.
2 1 Returns: 2
In this case step 1 is broken, so Jiro cannot jump upwards as his first action. The optimal strategy is to first stay on step 0, and then to jump from step 0 to step 2.
3 3 Returns: 5
1313 5858 Returns: 862641
1 757065 Returns: 1
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class JumpFurther with a public method int furthest(int N, int badStep) · 72 test cases · 2 s / 256 MB per case