11249 - Game

[emotional blind]

Its okay

[ibroker]

Sample input is confuse.

start at (a b) : (2 6)
take 1 stone both pile.(because at most k means 0~k)
(2 6) -> (1 5)

I think (1 5) must be winning point

Did I got misunderstand problem?

[mf]

(1, 5) is a winning position (for k=1), that's right.
As are all other positions to which you could move from (2, 6), and that in turn means that (2, 6) is a losing position, because whatever move you take, it'll be a win for your opponent.

[ibroker]

Oops I have to modify my post

I think (1 5) is loosing position.

if I make one of the pile zero, another player must be winner.

(because he can take up to all the stones from a pile)

So he must make piles nonzero.

Then he can take a stone.(k=1)

So another player's starts (1 4).

another player can take a stone.

So I starts (1 3).

It is a loosing point.

So (1 5) is loosing point.

Is it wrong?

[mf]

If you take stones from only one pile, you can take any number of stones - from 1 to the size of the pile. In position (1, 5) it's profitable to take 2 stones from the second pile - you'll reach (1, 3) which is a losing position. And thus (1, 5) is a winning position.

[sclo]

It is best to just write a dp program to simulate small inputs, then figure out a pattern to solve the large inputs. That way, we won't make much mistakes.

[ibroker]

Thanks!!

[Schultz]

I have written a program which produces correct outputs to the inputs I have tried so far. While solving the problem a friend and I formulated a complicated theory and proved its correctness. Of course, we must have made a mistake in the proof, otherwise we would have received accepted. According to it, the following code should solve the problem:

Code: Select all

#include<iostream>
#include<algorithm>
using namespace	std;

bool	wins(int x, int y, int k) {
	if (y > x)	swap(x, y);
	if (x-y < k+1)		return	true;
	else if (x-y == k+1)	return	y > 1;
	else {
		int	q;
		if (y > (k+1)*(k+2)) {
			q = k+1;
		}
		else {
			if (y%(k+2) == 0)	return	true;
			q = y/(k+2);
		}
		int	p = (y-q)*(k+2) + q;
		return	x != p;
	}
}

int	main() {
	int	t;
	cin >> t;
	while (t != 0) { --t;
		int	k, q;
		cin >> k >> q;
		while (q != 0) { --q;
			int	x, y;
			cin >> x >> y;
			cout << (wins(x, y, k) ? "WINNING" : "LOSING") << '\n';
		}
	}
	return	0;
}

I could find no extense input/output for this problem, and I am nearly giving up solving it.

Can anyone help?

[little joey]

For this input

Code: Select all

1
1 1
64 26

your program replies "WINNING", but it's a losing position.

[Schultz]

Thank you. I will check our proof once more after examining the input more carefully.

Could you tell me how why is it I can not win if I am given 64 26 with k = 1?

[little joey]

It is a lot of work to completely write it out. You could write a brute force program, as Adrian suggested, and verify it for yourself. In pseudo code:

Code: Select all

function evaluate(a,b,k):
/* returns 'winning'or 'losing'; a and b are the pile sizes */

   if a==0 and b==0 return 'losing'.

   for all positions (a',b') reachable from (a,b):
      if evaluate(a',b',k)=='losing' return 'winning'.

   return 'losing'.

[Schultz]

Sorry to delay so much to answer, I was lacking internet connection.

I see, it happens that we assumed many things to get to our result. We will give up this, we wasted four ours in this problem in the day we used it in our contest. I only wish I could know what is wrong with our theroy.

[tanaeem]

I am not sure what is my problem.
I have even checked my code by doing DP.
Probably have done some very silly mistake.

Code: Select all

removed after AC

edit:I have indeed done silly mistake, forgot to put a blank line after each case. oops:
But it should be PE :

[mf]

Print a blank line after each test case.

[esharif]

Lets see my code:

Code: Select all

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

int main()
{
    long int i, j, a, b, t, k, q, sum, dif, res;
    while(scanf("%ld",&t)==1)
    {
        for(i=1; i<=t; i++)
        {
            scanf("%ld%ld", &k, &q);
            for(j=1; j<=q; j++)
            {
                scanf("%ld%ld", &a, &b);
                if(b>a)
                    dif=(b-a);
                else
                    dif=a-b;
                if(dif%2==1 && k>=dif/2)
                    printf("WINNING\n\n");
                else
                    printf("LOSING\n\n");
            }
        }
    }
    return 0;
}

Suggest me and provide some critical i/p pleeeeeeeeease.