b%a, a is inevitable
Let us say our numbers are 0 < a <= b . We represent such a state as (a,b). (If b < a, then just swap them). The first thing to notice is that it is inevitable that we will eventually reach the state equal to (b%a, a). One of the available steps actually does it. But it is also nice to notice that the other kind of allowed steps, to subtract from b a power of a not equal to 1, will never change the result b'%a. This is because all ak when (k != 0) are multiples of a. So, if we have (b >= ak) then (b % a) will always be equal to ( (b - ak) % a ).
This is useful, because given a state (a,b), the number of different states reached by doing only (b % a, a) operations is quite small. (This is actually like an Euclidean algorithm, which we know has few states even for pairs of large numbers).
Some recursion won't hurt.
We got a state (a,b), and we know it will eventually become (b%a, b). Let us assume that we are using our knowledge in the theory of impartial games: We want to know if the player to receive the state (a,b) will win or not and we already know, whether the smaller case (b%a, b) is a victorious game or not (We are using recursion).
If (b % a, b) is a losing state, then the player that got state (a,b) can already win: Simply do the b%=a, operation.
In the other case, we got quite a sub-problem. The player is not able to use the b%=a operation without losing. Now, imagine the current player did some subtraction operation that did not lead to state (b%a, b), the next player will not be able to use the (b%a%a, b%a) move without losing either. In this battle to avoid letting the other player get state (b%a, a), we will have both players using only subtraction operations.
Let us consider the total number of times we can subtract a from b before it becomes equal to (b%a). We can assume b is not a multiple of a, (because else (b%a = 0, a) would be a losing state). Thus we have c = (b / a) - The number of times we can subtract a.
A subproblem
We can translate the previous subproblem to this version: We have a stack of c "stones" and two players. Each player can take 1, a, a^2, a^3, ... stones from the stack. The last player to remove stones from the stack before it becomes empty, will lose - The player that receives an empty stack wins.
(Removing one stone from the stack is the equivalent to subtracting a from b. Removing a stones is the equivalent of subtracting a^2. Etc. And when the stack is empty, it is equivalent to reaching state (b%a, a) which is a victory state).
At first I thought that we could somehow reduce this to Nim. But it turns out that's not the best approach (although I think it is possible and the end result is exactly the same we will find).
Imagine for a second that c is not very large. In fact, it is not larger than a. This means that the only move we are allowed to do is to take a single stone. (We cannot take a*a stones or greater, and if we take a stones, we lose). In this case, it is easy to see that the player will win if and only if c is even.
That is simply because 1 is an odd number. In fact, we can extend the idea: Imagine a was an odd number. Then every power of a will also be an odd number. This means that each player can only take an odd amount of stones in each turns. Once again, the current player wins if and only if c is even.
What to do when a is even and c is greater than a?. That is a nice question. Please note that we already know the answers for smaller values of c. Let us model our f(c) that says if it is a winning state or not:
f(0) = 1 (The player who receives the state with 0 stones wins).
f(1) = 0
f(2) = 1
f(3) = 0 // Since the only legal move is to subtract 1, the results alternate unti:
...
f(a-1) = 0
f(a) = 1 (We are assuming a is even)
f(a+1) = 1
f(a+2) = 0
f(a+3) = 1
...
f(a+a-1) = 1
f(a+a) = 0
f(a+a+1) = 1
f(a+a+2) = 1
Yes, (a+1) is a winning state. We can simply remove a stones and we force the other player to receive state 1, which is a losing state.
(a+2) is not a winning state. If we remove a single stone, the other player receives (a+1) which is a winning state. If we take (a) stones, the other player receives state (2). Another winning state. (a+3), ... keep alternating until we reach f(a+a-1) which is a winning state (subtract a to reach (a-1), a losing state). f(a+a) is a losing state, subtract 1 to reach (a+a-1) or a to reach state (a). It becomes interesting in (a+a+2)'s case, in which once again it is necessary to subtract (a) and reach (a+2). Now note that for each (a + 2 <= c <= a+a+2), f(c) is equal to f(c-(a+1) ). With this it is enough to conclude that if the allowed moves were 1 and a, the results are cyclic every (a+1) steps. In fact, the result is equal to taking (c % (a+1)) - if (c % (a+1)) is even, you win, else you lose.
Finally, consider a value of c such that it is a losing state in our supposed variation in which only taking 1 or a stones is allowed. This means that both f(c-1) and f(c-a) are winning states. Is it possible for f(c-a^k) (k > 1) to be a losing state? By induction, assume that the formula is valid for smaller states. So Since f(c - a) is a winning state and for contradiction purposes we assume that f(c - a^k) is a losing state then we have that the parities of the following two expressions must be different:
1. (c - a) % (a + 1)
2. (c - a^k) % (a + 1)
BUT, a and a^k always have the same parity (for k >= 2). So this is a contradiction and we have demonstrated that the formula is correct.
The similar problem from an old SRM: PotatoGame. I thank the blog at http://d.hatena.ne.jp/komiyam/20120328/1332881255 for pointing it out.
The code
//=========================================================
// program:
//
bool solve(long a, long b)
{
// {a <= b}
if (a > b) {
return solve(b, a);
}
if (a==0) {
//first player always loses
return false;
}
bool next = solve(b % a, a);
if (! next) {
// next state is defeat, always move to it
return true;
}
//return ( ( (b / a)%(a + 1) ) % 2 == 0);
// The next state is win, our current player must think of a way to reach
// next state in an even number of moves.
// we know that a is not 1 and b is not a multiple of a.
long c = (b / a);
// If current player wants to win, c elements must be taken from a 'stack'
// In an even number of moves when the only allowed moves are to take
// 1, a, a^2, a^3, ...
// if a is odd or if (a^2 is too large),
// then all allowed moves can only change the parity of the
// number of stacks. The parity of 0 is 0. Must reach "even" parity after
// an even number of moves.
if ( (a % 2 == 1) || (c <= a) ) {
return (c % 2 == 0);
} else {
// moves no longer forcibly change parity. Meh.
return ( ( c%(a + 1) ) % 2 == 0);
}
// Note that last give lines can be replaced with a single:
// return ( ( c%(a + 1) ) % 2 == 0); Because it also works
// when (a % 2 == 1) || (c <= a)
}
inline void init(){}
//=========================================================
// I/O:
//
int main()
{
init();
bool prev = false;
int T;
while( cin >> T) {
if (prev) {
cout << endl;
}
prev = true;
long a,b;
for (int i=0; i<T; i++) {
cin >> a >> b;
cout << (solve(a,b) ?"First": "Second") << endl;
}
}
return 0;
}
Once again, my explanation is humongous.
No comments :
Post a Comment