LightOJ 1393 Solution

Crazy Calendar Solution

Moving some coins to the cell right or beneath it is equivalent to moving some stones from a pile on this pillar of height h to a pillar of h-1.

F = First Player Move

S = Second Player Move

R = Row 

C = Column

x = Row of a cell   

y = Column of a cell

Case 1:

Case 2 :

Case 3 :

Case 4:

This is a example of Staircase Nim Game.

For a cell (x,y) we can think of this as a Stair. Also think that each cell coin as stone of a Stair. 

Above 4 kind of case we say that if (R+C) is Even than we shall compute the xor-sum only cell whose (x+y) is Odd otherwise (R+C) is Odd than we shall compute the xor-sum only cell whose (x+y) is Even.

Coding Part : 

#include<bits/stdc++.h>

#define ll long long int

using namespace std;

int main()

{

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        ll r, c;

        cin >> r >> c;

        ll a, xor_sum = 0, mod = (r+c)%2;

        for(int i=1; i<=r; i++)

        {

            for(int j=1; j<=c; j++)

            {

                cin >> a;

                if((i+j)%2 != mod)

                    xor_sum ^= a;

            }

        }

        if(xor_sum > 0)

            cout << "Case " << k++ << ": win" << "\n";

        else

            cout << "Case " << k++ << ": lose" << "\n";

    }

    return 0;

}