WC 5.3 Marble Game

There are N marbles lying on a table. There are two players. On each move, a player can take:

1 or 2 marbles if N is divisible by 3.

1 or 3 marbles if N - 1 is divisible by 3.

1, 2 or 3 marbles if N - 2 is divisible by 3.

Player 1 makes the first move. Each move can be made only if there are enough marbles to take. The player who cannot make a move loses the game. Find the winner if both players play optimally.

Input

N=22
N=45
N=26
N=75

Output

For each test case the answer is 1 or 2 - corresponding to first and second player respectively, who will win the game.

Print the final answer as the sum of outputs for each N.

Examples

For N=2, output is 1

Explanation

When N=2, first player takes both the marbles. Hence no marbles are left for second player. So first player wins

This challenge is worth 80 points.

You must be logged in to submit a solution

View ranklist for this challenge
About scoring and submission

Contact Us


Krish Shah : 9323115454

Kaustubh Khavnekar : 9769408039



Privacy Policy