## 11249 - Game

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Its okay

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
(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
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm
Thanks!!

Schultz
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
For this input

Code: Select all

``````1
1 1
64 26``````
your program replies "WINNING", but it's a losing position.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Schultz
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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'.
``````
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Schultz
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am
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
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### Getting WA

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 :
Last edited by tanaeem on Mon Dec 31, 2007 8:12 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Print a blank line after each test case.

esharif
New poster
Posts: 18
Joined: Sun Jun 03, 2012 11:56 pm

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

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.