Problem Translation :

A game is being played. You have N carrots and at each move the player can take 2^0, 2^1, 2^2... carrots. The one that takes the last carrot wins. You should output whether the first or second player wins, and if the first wins — what is his first move. N<=10^150.

General approach :

If you see such kind of problem, with N<=10^150, then most likely there is some observation to be made, that solves the problem. I won't go into details about game theory but in general, the best approach to start out with is write a simple program that will print which amounts of carrots are in a losing position.

Since the game is finite and there is no draw, then each position is either winning or losing. You have that 0 is a losing position, so you can either using DP-like state calculation or just simple backtracking find the losing/winning states for 1-100. Having done that, let's observe the results.

The following are the amounts of carrots that are a losing position:

3, 6, 9, 12, 15, 18, 21 ...

Now, those are obviously the multiples of three. And usually after such revelation, you come to think — but why is that so?

Now if you are in a competition you can just go ahead and code the solution, the proof isn't necessary, even though proving it is always a good thing to do.

But soon or later you gotta go back and try to prove why does that work? And well, in problems like this one where you have to print the first move, you have to find out the logic behind those positions to know what your moves should be.

Proof :

Now that you know multiples of 3 is something you should think about, it is easy to see and prove that 2^n = 1 or 2 (mod 3) — obviously, 2^n can't be divisible by 3, and 2^0,2^1 are examples of remainders 1 and 2.

So how does that help us? Well, we can notice that if the number is divisible by 3, then no matter what power we subtract by it — it won't be divisible by 3. And not only that, but if it is not divisible by 3, we can make it divisible by 3 in one move.

So knowing that, our strategy could be such that after each our move the remaining carrots will be a multiple of 3.

Solution :

Knowing everything we need, it is easily seen that the solution is in few easy parts. First we have to check whether the number is divisible by 3. Implement long integers? — No. We can just use the property for divisibility by 3 — if the sum of the digits is divisible by 3, then the number also is.

Then if it is not divisible by 3 we have to print an optimal move. Well that is easy, as we have noticed that only remainders of the power matter, so the move could always be 1 or 2, depending on the remainder of the number itself (sum of digits has the same remainder as the number itself).

Additional thoughts on game theory :

Problems like this are extremely common. I like to call them the " property X " problems. The idea is such:

If you have some property, call it X, that your state has. And the following rules are obeyed :

1. From a state having property X you can't go to another state having the property in one move.

2. From a state not having property X you can always go to another state having the property in one move.

3. All the terminal states (the positions in which the player whose move it is loses) have the property X.

Then you have a winning strategy. The strategy is simple : after your every move, leave the state with property X.

In our case, property X is divisibility by 3 and the only terminal state is 0, which is indeed divisible by 3 — so we have our optimal strategy.

This approach is very common and it's also used the famous NIM game, in which the property X is the XOR sum of all piles being 0. So you see, the properties could be quite different but if they follow the rules — the strategy is fine.

Hope I helped :)

P.S. Hope you speak English, since I don't speak Russian and I translated the statement from what I know in my Russian classes (which is not that much)