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 ?
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.
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 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]
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.
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.
. If this is true, that loosing move was not perfect, maybe it was the only move one could do.