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,
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).
Unfortunately, the road contains holes, and Iris can never land on a point which contains a hole.
You are given a vector 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.
DEFINITION
Class:RabbitJumping
Method:getMinimum
Parameters:vector , int
Returns:int
Method signature:int getMinimum(vector holes, int largeJump)
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
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)2010, TopCoder, Inc. All rights reserved.