boj 590

[Description]

teoy和3230391在915机房里发现了一块尺寸为n*m的巧克力，两个人互不想让，于是他们打算通过游戏来把这块巧克力瓜分掉。规则是两个人轮流吃巧克力，每次吃掉一个方块的巧克力时，它右下方的巧克力方块都可以他被吃掉。但是，谁把左上角的方块吃掉，谁就必须请对方一个大果粒。并且两人都不能中途退出游戏。由于是3230391先发现的巧克力，所以3030391先吃巧克力。假设两人都采取明智的策略，请问谁将掏钱来买大果粒。

对于这块巧克力，可以看作是n*m个方块组成，左上角的方块为(1,1),右下角的方块为(n,m)。

 

[Input]

一共有T组测试数据。每组数据一行两个整数n,m。

 

数据范围：

T<=20;

0<n,m<=200;

 

[Output]

对于每组数据，若最后3230391请客买大果粒，输出“3230391”；否则输出”teoy”。

 

[Sample Input]

1

2 2

 

[Sample Output]

teoy

 

[Hint]

 

[Source]

Caesar11@BUPTACM

 

当n=m=1时，先手输

当n,m不同时为1时，如果对于k∈[1,n-1],存在某个k，使得(k,m)为先手必败态，则3230391可以通过策略一步到达状态(k,m)，teoy买大果粒，同理对于k∈[1,m-1]，存在某个k，使得(n,k)为先手必败态，一样为3230391胜，teoy买大果粒。

如果对于所有的k∈[1,n-1],q∈[1,m-1],(k,m),(n,q)均为先手必胜态，则3230391总可以通过吃不同的方块，使自己达到某个(k,m)或者(n,q)状态，同样为3230391胜，teoy买大果粒。

代码：

#include<iostream>
using namespace std;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		if(n==1&&m==1)printf("3230391\n");
		else printf("teoy\n");
	}
}