+1学姐玩跳棋

Description

 

拥有复读机buff的+1学姐一路顺利,现在已经来到了最后一个关卡——跳棋大作战,该关卡有三个BOSS,分别是Gevjon,Tyr和Hoder。

战斗规则是,在1*n的棋盘上,从左到右依次标号为1,2,3……n-1,n。跳棋起初放在最左端,即位置1上。+1学姐和BOSS轮流进行一次操作,以一定的规则向右挪动棋子,将棋子恰好挪到最右端,即位置n上的人获胜。不能向左移动,只能在棋盘上移动,不能超出位置n。如果轮到某人移动棋子,但是棋子无法移动,则此人失败,对方获胜。

下面介绍移动规则,三场战斗移动规则不同:

Gevjon:两人轮流将棋子往右移动a格,即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+a;
Tyr:两人轮流将棋子往右移动1格或b格,即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+1或i+b;
Hoder:两人轮流将棋子往右移动c格或d格,即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+c或i+d;

假设+1学姐和三个BOSS都选择了最优策略。

由于BOSS不能主动攻击,所以每一个关卡都是+1学姐先手。

三场战斗独立进行,即这三场战斗跳棋起初都放在位置1上。

三场战斗使用的棋盘大小可能不同,即n可能不同。

现在给出n1,n2,n3,a,b,c,d(n1,n2,n3即三场棋盘的大小,a,b,c,d如上所述),请判断+1学姐能否通关。三个BOSS都被打败才算通关。

Input

 

第1行:一个数T,表示有T组样例。(1 <= T <= 10)

第2 - T + 1行:每行7个数n1,n2,n3,a,b,c,d。(1 <= n1,n2 <= 10^9,1<=n3<=1000,1<a,b<=10^9,1<=c,d<=1000)

Output

 

共T行,如果+1学姐能通关输出“YES”,否则输出“NO”。

Sample Input 1 

3
7 11 15 2 6 3 5
7 10 15 2 6 3 5
6 11 18 2 6 3 5

Sample Output 1

YES
NO
NO

Hint

Sample1 解释

第一组样例,+1学姐可以打败所有BOSS,所以输出“YES”。

第二组样例,+1学姐可以打败第一个BOSS Gevjon和第三个BOSS Hoder,但是不能打败第二个BOSS Tyr,所以输出“NO”。

第三组样例,+1学姐可以打败第二个BOSS,不能打败第一个和第三个BOSS,所以输出“NO”。

 

思路:

第一场:可以看做有n1-1颗石子,每次拿a颗,如果拿奇数次能拿完(或者不能再拿了),那么先手必胜,否则必败

第二场:打表找规律

              如果 b 是奇数的话,只需要判断 n2 的奇偶性,n2 为偶数则必胜;
              如果 b 是偶数,则 n2 每 b + 1 会出现 0101010 .......... 101011 的循环,所以只需要先将 n2%(b + 1),再判断奇偶性,若为偶数则必胜。

第三场:打表找规律

             n3-1每c+d会出现c个0,d个1的循环,所以(n3-1)%(c+d)<c的话就是必败态。

组合游戏不会推就直接sg函数打表找规律吧(打表代码见最下面)

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	int T,n1,n2,n3,a,b,c,d,k;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d%d%d%d",&n1,&n2,&n3,&a,&b,&c,&d);
		bool flag1=false,flag2=false,flag3=false;
		//1
		k=(n1-1)/a;
		if(k&1) flag1=true; 
		//2
		if((b&1)&&n2%2==0) flag2=true; 
		if(b%2==0&&(n2%(1+b))%2==0) flag2=true;
		//3
		if(c>d) swap(c,d);
		k=(n3-1)%(c+d);
		if(k>=c) flag3=true;
		//总
		//printf("%d%d%d\n",flag1,flag2,flag3);
		if(flag1&&flag2&&flag3) printf("YES\n");
		else printf("NO\n"); 
	}
	return 0;
}

 打表里的i是n-1

#include<cstdio>
#include<cstring>
using namespace std;
int sg[100];
int a,b,c,d,n;
void init(){
	memset(sg,-1,sizeof(sg));
}
int Getsg(int x){
	if(sg[x]!=-1) return sg[x];
	if(x==0) return sg[x]=0;
	if(x==c||x==d) return sg[x]=1;
	if(x<c) return sg[x]=0;
	bool book[100];
	memset(book,0,sizeof(book));
	if(x>=d){
		sg[x-c]=Getsg(x-c);
		book[sg[x-c]]=true;
		sg[x-d]=Getsg(x-d);
		book[sg[x-d]]=true;
	}
	if(x>=c&&x<d){
		sg[x-c]=Getsg(x-c);
		book[sg[x-c]]=true;
	}
	for(int i=0;;i++){
		if(!book[i]) return sg[x]=i;
	}
}
int main(){
	scanf("%d%d",&c,&d);
	printf("c = %d , d = %d\n",c,d);
	for(int i=0;i<100;i++){//i是n-1
		init();
		int ans=Getsg(i);
		if(ans!=0) ans=1;//为了好观察,所有的必胜态的sg值都输出1
		printf("%3d  %3d : %3d\n",i,(i+1)%(c+d),ans);
	}
	return  0;
}