CarrotJumping
Member SRM 478 · 2009-12-03 · by rng_58
Member SRM 478 · 2009-12-03 · by rng_58 · Math
Problem Statement
Problem Statement
Rabbits often feel hungry, so when they go out to eat carrots, they jump as quickly as possible.
Initially, rabbit Hanako stands at position init. From position x, she can jump to either position 4*x+3 or 8*x+7 in a single jump. She can jump at most 100,000 times because she gets tired by jumping.
Carrots are planted at position x if and only if x is divisible by 1,000,000,007 (i.e. carrots are planted at position 0, position 1,000,000,007, position 2,000,000,014, and so on). Return the minimal number of jumps required to reach a carrot. If it's impossible to reach a carrot using at most 100,000 jumps, return -1.
Initially, rabbit Hanako stands at position init. From position x, she can jump to either position 4*x+3 or 8*x+7 in a single jump. She can jump at most 100,000 times because she gets tired by jumping.
Carrots are planted at position x if and only if x is divisible by 1,000,000,007 (i.e. carrots are planted at position 0, position 1,000,000,007, position 2,000,000,014, and so on). Return the minimal number of jumps required to reach a carrot. If it's impossible to reach a carrot using at most 100,000 jumps, return -1.
Constraints
- init will be between 1 and 1,000,000,006, inclusive.
Examples
0)
125000000 Returns: 1
She can jump from 125000000 to 1000000007.
1)
281250001 Returns: 2
281250001 -> 1125000007 -> 9000000063
2)
974579565 Returns: -1
3)
18426114 Returns: 58
4)
4530664 Returns: 478
14)
852808441 Returns: -1
She can't reach any carrot by making at most 100,000 jumps.
Submissions are judged against all 65 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CarrotJumping with a public method int theJump(int init) · 65 test cases · 2 s / 256 MB per case