Page 2 of 3

Posted: Mon Jul 30, 2007 3:52 pm
by emotional blind
Its okay :)

Posted: Fri Aug 10, 2007 2:47 pm
by 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?

Posted: Fri Aug 10, 2007 3:02 pm
by 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.

Posted: Fri Aug 10, 2007 8:46 pm
by 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?

Posted: Fri Aug 10, 2007 8:52 pm
by 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.

Posted: Sat Aug 11, 2007 3:28 am
by 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.

Posted: Sat Aug 11, 2007 4:34 am
by ibroker
Thanks!! :D

Posted: Mon Aug 20, 2007 1:02 am
by 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?

Posted: Mon Aug 20, 2007 10:07 am
by little joey
For this input

Code: Select all

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

Posted: Mon Aug 20, 2007 9:36 pm
by 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?

Posted: Tue Aug 21, 2007 12:55 am
by 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'.

Posted: Sat Aug 25, 2007 5:09 pm
by 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.

Getting WA

Posted: Mon Dec 31, 2007 7:22 am
by 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 :

Posted: Mon Dec 31, 2007 9:16 am
by mf
Print a blank line after each test case.

Why WA for 11249, please give me some critical i/p & o/p

Posted: Wed Jul 04, 2012 5:22 pm
by 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.