11249  Game
Moderator: Board moderators

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
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?
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?
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:
I could find no extense input/output for this problem, and I am nearly giving up solving it.
Can anyone help?
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 (xy < k+1) return true;
else if (xy == 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 = (yq)*(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;
}
Can anyone help?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
For this inputyour program replies "WINNING", but it's a losing position.
Code: Select all
1
1 1
64 26
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

 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.
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.
edit:I have indeed done silly mistake, forgot to put a blank line after each case. oops:
But it should be PE :
I have even checked my code by doing DP.
Probably have done some very silly mistake.
Code: Select all
removed after AC
But it should be PE :
Last edited by tanaeem on Mon Dec 31, 2007 8:12 pm, edited 1 time in total.
Why WA for 11249, please give me some critical i/p & o/p
Lets see my code:
Suggest me and provide some critical i/p pleeeeeeeeease.
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=(ba);
else
dif=ab;
if(dif%2==1 && k>=dif/2)
printf("WINNING\n\n");
else
printf("LOSING\n\n");
}
}
}
return 0;
}