@anu1234 Here you go, It’s gonna be a little long answer, but try being patient you’ll get the answer in the end There are two kinds of positions, winning and losing. To find whether a position {i,j} is winning or loosing, we draw a 2-D grid. All configuration of the form {i,i} or {0,i} or {i,0} are winning positions and we mark them in the grid. Initially, the grid looks like

```
'*' indicates yet to be determined.
'L' indicates a loosing position.
'W' indicates a winning position.
L W W W W W W...
W W * * * * * * * .......
W * W * * * * * * .......
W * * W * * * * *.......
W * * * W * * * *......
W * * * * W * * ......
..................................
Considering 0 based indexing in the grid, position i,j in the grid indicates the configuration {i,j} of the game (i remaining in H1 and j remaining in H2).
```

Consider any losing position say {1,2}(it can be easily seen that 1,2 is a losing position), then all those positions from which we can move to (1,2) are winning positions because we know the player that plays the move on reaching (1,2) will surely lose. Is this clear?(If not, you may ask in the comment).

Thus, for this losing position, all points in the grid of the form:

```
Winning positions:
(1+i,2+i)-> we can reach (1,2) by taking i from each heap
(1+i,2) -> take i from 1st heap will lead to config. (1,2)
(1,2+i) -> taking i from second heap will lead to configuration (1,2)
Similarly, (2,1) is also a losing move and thus (2+i,1+i)(2,1+i)(2+i,1) are winning positions.
```

Now, we can easily see here that if we know one losing move, we can get all other winning positions possible from this move and mark them as W in the grid. How, our grid will look like can be seen here. This, was just the tutorial mentioned in short.

As mentioned, The problem is standard Wythoff’s game and the standard solution with good space and time optimization is here: The strategy of the game revolves around cold positions(losing ones) and hot positions(winning ones). Our main objective is just to determine which positions are hot and which are cold :P. This classification can be done this way, (from wiki):

```
1.) (0,0) is a cold position.
2.) Any position from which a cold position can be reached in a single move is a hot position.
3.) If every move leads to a hot position, then a position is cold.
```

We already know all configurations of the form (0,i) or (i,0) or (i,i) are winning positions. Some of the cold positions are: (0,0) (1,2), (3,5) etc… These configurations represented by say (n,m) form a regular pattern which is determined this way: let (n_{k}, m_{k}) be the k’th cold position. Then, all such cold positions form the Beatty sequences. In short it is the sequence of integers formed by the taking the floor value of positive multiples of the given irrational numbers. We’ll however, be dealing with integers here.

So, far so good I suppose, have patience :).

Specifically, if K is any natural number, then

n_{k}= k*(golden ratio)

and m_{k}= n_{k} +k

or more clearly, if we take n_{k} to be some value i, then m_{k} is (i+k).

and this is generated using the following code:

```
int k=0; // start with the losing state (0,0) and assuming we are finding k'th losing state
for(int i=0; (i+d)<=MAX;i++)
{
if(!used[i] && !used[i+k])
{
cout<<"losing state : "<<i<<" "<<i+d<<endl;
used[i]=1;
used[i+k]=1; // mark the move as used
}
}
```

What the above code does is, we start with some initial losing state (0,0). In the configuration (n_{k}, m_{k}, i in the above code refers to n_{k} and (i+k) refers to m_{k}. Recall the above wiki lines which told how the cold positions look like. Why are we marking the states as used? This is because, lets say we have the losing state (2,1), the next possible state without the use could have been (2,4)( i=2 and d=2) but we can reach the state (2,1) by taking 3 coins from heap2. Thus, this state is the winning state. This is actually the interpretation of the second points of the above wiki lines (“Any position from which a cold position can be reached in a single move is a hot position.”).

Now, we have all states which are losing and which are winning, we can judge who’ll be the winner in just constant time look-up. For fully working code, you may refer this.

(PS: This is not my code, my code was a brute force one, i’ll post here if you want, just let me know, I was looking several codes of this hackerearth problem when I went across this, and then the whole concept, but i just accidently forgot to take note of the person who’s code is this. I’d have opted to give you credits here :), thanks a lot man!!

I tried my best explaining, any faults or comments are most welcomed.

Thanks, for reading such long and being patient