Optimal Strategy in a Turn-based Game

Two players, A and B, play a game taking turns operating on a pair of integers \((x,y)\). Initially, \((x,y)=(1,0)\). There are three operations available:

1. Change \((x,y)\) to \((1, x+y)\).
2. Change \((x,y)\) to \((2x, y)\).
3. Change \((x,y)\) to \((3x, y)\).

However, when \(x+y \ge n\) (where \(n\) is a given positive integer), the second and third operations are disallowed. Moreover, if after a move, the value of \(y\) becomes \(\ge n\), then the mover loses immediately.

You are given that \(n\) is chosen such that the first player has a winning strategy. Your task is to implement an interactive function

[ extern \ "C"\ int _opt(int n, int x, int y) ]

which, when it is your turn and the current pair is ((x,y)) (with parameter (n)), returns one of the integers (1), (2) or (3) corresponding to the move you choose.

A simple example is when \(n=3\). The first player can choose operation 3 from the initial state \((1,0)\) to obtain \((3,0)\). Now \(x+y=3\), so the second player is forced to use operation 1 (the only allowed move), resulting in \((1,3)\); since \(3 \ge 3\) the second player loses.

inputFormat

This is an interactive problem. The testing system will call your function _opt with parameters n, x, and y representing the target threshold and the current state \((x,y)\) respectively. It is guaranteed that the current state satisfies \(x+y < n\) (so that a move is available).

outputFormat

Your function should return an integer value of 1, 2, or 3 representing the chosen operation.

The operations are defined as follows:

• 1: transforms \((x,y)\) to \((1, x+y)\).
• 2: transforms \((x,y)\) to \((2x, y)\).
• 3: transforms \((x,y)\) to \((3x, y)\).

Remember: if the operation you choose causes \(y \ge n\) (which can happen with operation 1), you lose immediately. Use operations 2 or 3 to manipulate \(x\) and force your opponent into a losing move when possible.

sample

3
1 0

3