RabbitJumping
SRM 475 · 2009-11-12 · by lyrically
SRM 475 · 2009-11-12 · by lyrically · Graph Theory
Problem Statement
Problem Statement
Rabbits often feel lonely, so when they go out to meet their friends, they jump as quickly as possible.
Rabbit Iris is on an infinitely long straight road. Points on this road are numbered ..., -3, -2, -1, 0, 1, 2, 3, ... from west to east. Iris is at point 0 now, and she is going to meet her friend at point 1,000,000,001. She can only move by jumping, and she can perform two types of jumps: small and large. When she is at point x,int[] holes containing N * 2 elements. For each i, where 0 <= i < N, all points between holes[i * 2] and holes[i * 2 + 1], inclusive, contain holes.
Iris prefers to perform small jumps because she can do them faster. Return the minimum number of large jumps required to reach point 1,000,000,001. If it is impossible to reach that point, return -1 instead.
Rabbit Iris is on an infinitely long straight road. Points on this road are numbered ..., -3, -2, -1, 0, 1, 2, 3, ... from west to east. Iris is at point 0 now, and she is going to meet her friend at point 1,000,000,001. She can only move by jumping, and she can perform two types of jumps: small and large. When she is at point x,
- By making a small jump, she can move to either point (x + 2) or point (x - 2).
- By making a large jump, she can move to either point (x + largeJump) or point (x - largeJump).
Iris prefers to perform small jumps because she can do them faster. Return the minimum number of large jumps required to reach point 1,000,000,001. If it is impossible to reach that point, return -1 instead.
Notes
- Iris can travel to points with negative numbers and numbers greater than 1,000,000,001.
Constraints
- holes will contain between 2 and 50 elements, inclusive.
- holes will contain an even number of elements.
- Each element of holes will be between 1 and 1,000,000,000, inclusive.
- Elements of holes will be in strictly increasing order.
- largeJump will be between 3 and 1,000,000,000, inclusive.
Examples
0)
{ 1, 2 }
3
Returns: 1
0 => 3 -> 5 -> 7 -> ... -> 999999999 -> 1000000001 Iris needs to make at least one large jump to jump over the holes at points 1 and 2.
1)
{ 1, 2 }
4
Returns: -1
Iris can never step on point 1,000,000,001, or any other odd-numbered point.
2)
{ 2, 3 }
3
Returns: 3
One solution to reach the goal with 3 large jumps is: 0 -> -2 => 1 => 4 => 7 -> 9 -> 11 -> ... -> 999999999 -> 1000000001
3)
{ 2, 17, 21, 36, 40, 55, 59, 74 }
19
Returns: 5
4)
{ 187640193, 187640493, 187640738, 187640845, 564588641, 564588679,
564588696, 564588907, 605671187, 605671278, 605671288, 605671386,
755723729, 755723774, 755723880, 755723920, 795077469, 795077625,
795077851, 795078039, 945654724, 945654815, 945655107, 945655323 }
475
Returns: 9
Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RabbitJumping with a public method int getMinimum(vector<int> holes, int largeJump) · 163 test cases · 2 s / 256 MB per case