Pagodas

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1052    Accepted Submission(s): 740

Problem Description
n pagodas were standing erect in Hong Jue Si between the Niushou Mountain and the Yuntai Mountain, labelled from 1 to n. However, only two of them (labelled a and b, where 1≤a≠b≤n) withstood the test of time.

Two monks, Yuwgna and Iaka, decide to make glories great again. They take turns to build pagodas and Yuwgna takes first. For each turn, one can rebuild a new pagodas labelled i (i∉{a,b} and 1≤i≤n) if there exist two pagodas standing erect, labelled j and k respectively, such that i=j+k or i=j−k. Each pagoda can not be rebuilt twice.

This is a game for them. The monk who can not rebuild a new pagoda will lose the game.
 

Input
The first line contains an integer t (1≤t≤500) which is the number of test cases.
For each test case, the first line provides the positive integer n (2≤n≤20000) and two different integers a and b.
 

Output
For each test case, output the winner (``Yuwgna" or ``Iaka"). Both of them will make the best possible decision each time.
 

Sample Input
16 2 1 2 3 1 3 67 1 2 100 1 2 8 6 8 9 6 8 10 6 8 11 6 8 12 6 8 13 6 8 14 6 8 15 6 8 16 6 8 1314 6 8 1994 1 13 1994 7 12
 

Sample Output
Case #1: Iaka Case #2: Yuwgna Case #3: Yuwgna Case #4: Iaka Case #5: Iaka Case #6: Iaka Case #7: Yuwgna Case #8: Yuwgna Case #9: Iaka Case #10: Iaka Case #11: Yuwgna Case #12: Yuwgna Case #13: Iaka Case #14: Yuwgna Case #15: Iaka Case #16: Iaka
 

Source

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学） 



思路：

这道题的题意就是，给你n个点，然后在n个点中只有两个点是完好可用的，然后两个人轮流来走，每次只能走到j-k或者j+k，当没办法继续走的时候就输了。问这两个人谁会赢。一开始的做法是DFS深度优先搜索，对于数据较小的范围可以实现，但是不太对的地方就是，我的每个dfs函数体内，要向下递归4次，这就使次数按4次幂增长，所以到第17个样例的时候，我直接就开始爆掉了，所以DFS做法没调好。之后采用数学的做法，因为在手动模拟中可以看出来，每次走的距离都是这两个数的因数，而且是最大公因数。这就说明，它能走的距离是他们的最大公因数的倍数。所以只需要判断n之内有几个可走到的点就可以得出走了几次从而知道谁会赢。


代码：

DFS没调通的做法：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int sum=0;
int n;
int a[20000+5];

void dfs(int jj,int kk)
{
	int j=min(jj,kk);
	int k=max(jj,kk);
	int dir1[2]={-k,k};
	int dir2[2]={-j,j};
	for(int i=0;i<2;i++)
	{
		int dx=j+dir1[i];

		if(dx<1||dx>n)continue;
		
		if(a[dx]==0)
		{
			sum++;
			a[dx]=1;
			dfs(j,dx);
			dfs(k,dx);
		}
		else if(a[dx]<2*n)
		{
			a[dx]++;
			dfs(k,dx);
			dfs(j,dx);	
		}
	}
	for(int i=0;i<2;i++)
	{
		int dx=k+dir2[i];

		if(dx<1||dx>n)continue;
		
		if(a[dx]==0)
		{
			sum++;
			a[dx]=1;
			dfs(k,dx);
			dfs(j,dx);
		}
		else if(a[dx]<2*n)
		{
			a[dx]++;
			dfs(k,dx);
			dfs(j,dx);	
		}
	}
}

int main()
{
	int t;
	while(scanf("%d",&t)!=EOF)
	{
		for(int num=1;num<=t;num++)
		{
			memset(a,0,sizeof(a));
			sum=0;
			scanf("%d",&n);
			int a1,a2;
			scanf("%d%d",&a1,&a2);
			a[a1]=1;
			a[a2]=1;
			dfs(a1,a2);
		//	printf("%d\n",sum);
			printf("Case #%d: ",num);
			if(sum%2==0)printf("Iaka%d\n");
			else printf("Yuwgna%d\n");
		}
	}
	return 0;
}


数学规律ac代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int gcd(int a, int b)
{  
    return b == 0 ? a : gcd(b, a%b);  
}  
int main()  
{  
	//freopen("in.txt","r",stdin);
	int t;
	while(scanf("%d",&t)!=EOF)
	{
		for(int num=1;num<=t;num++)
		{
			int n;
			scanf("%d",&n);
			int a1,a2;
			scanf("%d%d",&a1,&a2);
			int temp = gcd(a1, a2);  
            int sum = n / temp - 2;  
			printf("Case #%d: ",num);
			if(sum%2==0)printf("Iaka\n");
			else printf("Yuwgna\n");
		}
	}
	return 0;
}