Codeforces 1451D. Circle Game(博弈)

Description

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;
}