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

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

Post by emotional blind » Mon Jul 30, 2007 3:52 pm

Its okay :)

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

Post by ibroker » Fri Aug 10, 2007 2:47 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:

Post by mf » Fri Aug 10, 2007 3:02 pm

(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

Post by ibroker » Fri Aug 10, 2007 8:46 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:

Post by mf » Fri Aug 10, 2007 8:52 pm

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:

Post by sclo » Sat Aug 11, 2007 3:28 am

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

Post by ibroker » Sat Aug 11, 2007 4:34 am

Thanks!! :D

Schultz
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am

Post by Schultz » Mon Aug 20, 2007 1:02 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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 20, 2007 10:07 am

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

Post by Schultz » Mon Aug 20, 2007 9:36 pm

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Aug 21, 2007 12:55 am

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

Post by Schultz » Sat Aug 25, 2007 5:09 pm

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

Post by tanaeem » Mon Dec 31, 2007 7:22 am

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:

Post by mf » Mon Dec 31, 2007 9:16 am

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

Post by esharif » Wed Jul 04, 2012 5:22 pm

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.

Post Reply

Return to “Volume 112 (11200-11299)”