Digital Deletions
Begin by writing down a string of digits (numbers) that's as long or as short as you like. The digits can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and appear in any combinations that you like. You don't have to use them all. Here is an example:
On a turn a player may either:
Change any one of the digits to a value less than the number that it is. (No negative numbers are allowed.) For example, you could change a 5 into a 4, 3, 2, 1, or 0.
Erase a zero and all the digits to the right of it.
The player who removes the last digit wins.
The game that begins with the string of numbers above could proceed like this:
Now, given a initial string, try to determine can the first player win if the two players play optimally both.
The length of string will be in the range of [1,6]. The string contains only digit characters.
Proceed to the end of file.
0 00 1 20
Yes Yes No No
#include<cstdio>
#include<cstring>
int vis[110];
int SG[11][11][11][11][11][11];
void fun()
{
int i,j;
int cnt[10];
SG[0][0][0][0][0][0]=0;
for(cnt[1]=1;cnt[1]<=10;cnt[1]++)
{
for(cnt[2]=0;cnt[2]<=10;cnt[2]++)
{
for(cnt[3]=0;cnt[3]<=10;cnt[3]++)
{
if(cnt[2]==0 && cnt[3]!=0)
break;
for(cnt[4]=0;cnt[4]<=10;cnt[4]++)
{
if(cnt[3]==0 && cnt[4]!=0)
break;
for(cnt[5]=0;cnt[5]<=10;cnt[5]++)
{
if(cnt[4]==0 && cnt[5]!=0)
break;
for(cnt[6]=0;cnt[6]<=10;cnt[6]++)
{
if(cnt[5]==0 && cnt[6]!=0)
break;
memset(vis,0,sizeof(vis));
if(cnt[1]>1)
{
for(j=1;j<cnt[1];j++)
vis[SG[j][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]]=1;
}
if(cnt[2]>1)
{
for(j=1;j<cnt[2];j++)
vis[SG[cnt[1]][j][cnt[3]][cnt[4]][cnt[5]][cnt[6]]]=1;
}
if(cnt[3]>1)
{
for(j=1;j<cnt[3];j++)
vis[SG[cnt[1]][cnt[2]][j][cnt[4]][cnt[5]][cnt[6]]]=1;
}
if(cnt[4]>1)
{
for(j=1;j<cnt[4];j++)
vis[SG[cnt[1]][cnt[2]][cnt[3]][j][cnt[5]][cnt[6]]]=1;
}
if(cnt[5]>1)
{
for(j=1;j<cnt[5];j++)
vis[SG[cnt[1]][cnt[2]][cnt[3]][cnt[4]][j][cnt[6]]]=1;
}
if(cnt[6]>1)
{
for(j=1;j<cnt[6];j++)
vis[SG[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][j]]=1;
}
if(cnt[1]==1)
vis[SG[0][0][0][0][0][0]]=1;
if(cnt[2]==1)
vis[SG[cnt[1]][0][0][0][0][0]]=1;
if(cnt[3]==1)
vis[SG[cnt[1]][cnt[2]][0][0][0][0]]=1;
if(cnt[4]==1)
vis[SG[cnt[1]][cnt[2]][cnt[3]][0][0][0]]=1;
if(cnt[5]==1)
vis[SG[cnt[1]][cnt[2]][cnt[3]][cnt[4]][0][0]]=1;
if(cnt[6]==1)
vis[SG[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][0]]=1;
for(i=0;i<100;i++)
{
if(vis[i]==0)
{
SG[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]=i;
break;
}
}
}
}
}
}
}
}
}
int main()
{
char ch[10];
int tmp[10];
int i;
fun();
while(scanf("%s",ch)==1)
{
int L=strlen(ch);
for(i=0;i<L;i++)
{
tmp[i]=ch[i]-'0'+1;
}
while(i<6)
{
tmp[i++]=0;
}
if(SG[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]]==0)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}