10578 - The Game of 31

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

Moderator: Board moderators

Post Reply
Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

10578 - The Game of 31

Post by Maarten » Sat Nov 08, 2003 8:25 pm

Hi everyone!

I tried to do 10578 and was surprised to get WA... First of all I'm a little unsure how to handle the input.. for example if there is an empty line at the end of the input I should treat it as being a test case, right ? And what if there is a \n at the end of the last line but nothing else ?
Hope someone can help me, currently I'm doing something like:
[cpp]while( true ) {
gets(line);
if( feof(stdin) ) break;
...
}[/cpp]

Furthermore, is my output for the following tests correct ?

Input:

Code: Select all


1
2
3
4
5
6
Output:

Code: Select all

 A
1 B
2 B
3 A
4 B
5 B
6 A
Thanks for any help!

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sun Nov 09, 2003 7:30 am

Maarten, your input function seems ok to me but didn't produce the last output in my pc. Instead you can use:
[c]while(gets(line))[/c]

And the output for your input is

Code: Select all

 A
1 A
2 A
3 B
4 B
5 A
6 B

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sun Nov 09, 2003 12:52 pm

hmm.. so it seems i'm completely wrong in my output... then i probably made a stupid mistake somewhere. Thanks for your help so far

-Edit-
Thanks, got accepted now. I made a really stupid mistake... they're usually the hardest to find :-(

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Fri Dec 05, 2003 4:27 pm

What does "perfect strategy" means... I really got confused in problems which says that. Can you explain me a little about this?

In this game, e.g., what is the perfect strategy?

JP.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Dec 06, 2003 1:26 pm

That is exactly what you have to figure out in this problem! ;-)

Perfect strategy means: If there IS a move that leads to a winning situation, you do that move, and no other. Imagine you are calculating all possible moves in the game, and determine if a move is winning, or loosing (or maybe undetermined). Then the move you actually do, is not a loosing move.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sat Dec 06, 2003 2:02 pm

But someone on some time will need to do a loosing move, so the other will win :). If this is true, that loosing move was not perfect, maybe it was the only move one could do.

I'm still confused with that...

JP.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

10578 The Game of 31

Post by SilVer DirectXer » Thu Jan 01, 2004 6:41 am

i do minimax search on it.
but WA.
can anyone give me some cases that my code doesnt work?
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int i,j,k;
char in[30];
int cards[35];
int sum;
int minimax(int n,int state,int card1,int card2,int card3,int card4,int card5,int card6);
void main(void)
{
while (1)
{

sum=31;
for (i=1;i<=6;i++)
cards=4;


gets(in);
if (feof(stdin))
break;
int l=strlen(in);
for (i=0;i<=l;i++)
{
if (in=='1')
{
cards[in-0x30]--;
sum-=(in-0x30);
}

if (in=='2')
{
cards[in-0x30]--;
sum-=(in-0x30);
}

if (in=='3')
{
cards[in-0x30]--;
sum-=(in-0x30);
}

if (in[i]=='4')
{
cards[in[i]-0x30]--;
sum-=(in[i]-0x30);
}

if (in[i]=='5')
{
cards[in[i]-0x30]--;
sum-=(in[i]-0x30);
}

if (in[i]=='6')
{
cards[in[i]-0x30]--;
sum-=(in[i]-0x30);
}
}


int ans=minimax(sum,1,cards[1],cards[2],cards[3],cards[4],cards[5],cards[6]);
if (ans==1)
{
if (l % 2 ==0)
printf("%s A\n",in);
else
printf("%s B\n",in);
}
else
{
if (l % 2==0)
printf("%s B\n",in);
else
printf("%s A\n",in);
}



}
}
int minimax(int n,int state,int card1,int card2,int card3,int card4,int card5,int card6)
{
int c[7];
c[1]=card1;
c[2]=card2;
c[3]=card3;
c[4]=card4;
c[5]=card5;
c[6]=card6;
int end=0;
int temp;
if (n==0)
end=1;

int ok=1;
for (int k=1;k<=6;k++)
{
if(c[k]>0 && n-k>0)
ok=0;
}
if (ok==1)
end=1;

if (end==1)
{
if (state==1)
return 0;
else
return 1;
}

if (state==1)
{
for (int j=1;j<=6;j++)
{
if (c[j]>0 && n-j>0)
{
c[j]--;
temp=minimax(n-j,!state,c[1],c[2],c[3],c[4],c[5],c[6]);
if (temp==1)
return 1;
}
}
return 0;
}
else
{

for (int j=1;j<=6;j++)
{
if (c[j]>0 && n-j>0)
{
c[j]--;
temp=minimax(n-j,!state,c[1],c[2],c[3],c[4],c[5],c[6]);
if (temp==0)
return 0;
}
}
return 1;
}
}
[/cpp]

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Jan 18, 2004 12:37 pm

Hi SilVer DirectXer,

You can try these inputs:
1
2
3
4
5
6
11
112

And the answers:
1 A
2 A
3 B
4 B
5 A
6 B
11 A
112 B

Hope it helps :wink:

angga888

silviagd
New poster
Posts: 1
Joined: Sun May 22, 2005 8:46 pm

10578 time limit

Post by silviagd » Fri May 27, 2005 2:23 pm

It seems that my problem takes too long to calculate the answers, but it works for the standard input. I explore all the branches of the tree. Help

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri May 27, 2005 4:04 pm

Always consider the worst case. I'm guessing the worst case for you would be if input is simply "1".

To avoid computing the same thing over and over again, try to consider the fact that it doesn't matter in what order the previous cards have been played in.

AndresRicardoTorres
New poster
Posts: 1
Joined: Tue Aug 02, 2011 6:53 pm

Re: 10578 - The Game of 31

Post by AndresRicardoTorres » Tue Aug 02, 2011 6:57 pm

Hi guys!

i dont know how optime my search in this problem, some hint ?

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10578 - The Game of 31

Post by Imti » Sat Jan 28, 2012 5:54 pm

AndresRicardoTorres wrote:Hi guys!

i dont know how optime my search in this problem, some hint ?
I used Dynamic programming to solve this problem.Think a dp table of size [31][4][4][4][4][4][4] is within memory
constraint of this problem.Just make best strategy at each recursion for each player and meomrize this for future use.

Post Reply

Return to “Volume 105 (10500-10599)”