Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Marvin plays a simple game. The game is played with an infinite supply of marbles and five bags, labeled "bag 0" through "bag 4".
- At the beginning, Marvin takes N marbles (where N is a nonnegative integer) and places them into bag 0. The remaining four bags are left empty. Marvin then follows this simple algorithm:
- Add a marble into bag 1.
- Repeat forever:
- Add a marble into bag 1.
- Empty bag 4.
- While there are marbles in bag 0:
- While there are marbles both in bag 0 and in bag 1:
- Remove a marble from bag 0.
- Remove a marble from bag 1.
- Add a marble into bag 2.
- Add a marble into bag 3.
- End While
- Add a marble into bag 4.
- If bags 0 and 1 are both empty:
- Move all marbles from bag 3 to bag 4.
- TERMINATE THE GAME
- End If
- Move all marbles from bag 3 to bag 1.
- End While
- Move all marbles from bag 2 to bag 0.
- End Repeat
- You are given a long long N. Count the number of times a marble enters a bag during Marvin's game. That is, compute X+Y, where X is the number of times a marble is added to some bag, and Y is the number of times a marble is moved from one bag to another. To avoid overflows, return just the value ((X+Y) modulo 1,000,000,009). If Marvin's game does not terminate for the given N, return -1 instead.
Add Comment
Please, Sign In to add comment