欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 1451D. Circle Game(博弈)

程序员文章站 2022-03-15 23:36:50
...

Description
Codeforces 1451D. Circle Game(博弈)
Example
input
5
2 1
5 2
10 3
25 4
15441 33

output
Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish

Solution
典型对称博弈
先计算出若右/上交替着走能走的最远步数k
若k为奇数:先手先随便走一步,之后的每一步都与上一步后手对称,即可使得先手必胜
若k为偶数:无论先手怎么走,后手都与其对称的走,即可使得后手必胜

Code

int res;
ll d,k;
void dfs(ll x,ll y) {
	if(x > y) swap(x,y);
	ll tmp = x + k;if(tmp * tmp + y * y > d * d) return ;
	res++;dfs(tmp,y);
}
int main(int argc, char const *argv[])
{
	int T;scanf("%d",&T);
	while(T--) {
		scanf("%lld %lld",&d,&k);
		res = 0;
		dfs(0,0);
		if(res%2) printf("Ashish\n"); else printf("Utkarsh\n");
	}
	return 0;
}
相关标签: 博弈论