Codeforces Round #685 (Div. 2) D. Circle Game（博弈）

本文主要是介绍Codeforces Round #685 (Div. 2) D. Circle Game（博弈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://codeforc.es/contest/1451/problem/D

Utkarsh is forced to play yet another one of Ashish’s games. The game progresses turn by turn and as usual, Ashish moves first.

Consider the 2D plane. There is a token which is initially at (0,0). In one move a player must increase either the x coordinate or the y coordinate of the token by exactly k. In doing so, the player must ensure that the token stays within a (Euclidean) distance d from (0,0).

In other words, if after a move the coordinates of the token are (p,q), then p2+q2≤d2 must hold.

The game ends when a player is unable to make a move. It can be shown that the game will end in a finite number of moves. If both players play optimally, determine who will win.

Input
The first line contains a single integer t (1≤t≤100) — the number of test cases.

The only line of each test case contains two space separated integers d (1≤d≤105) and k (1≤k≤d).

Output
For each test case, if Ashish wins the game, print “Ashish”, otherwise print “Utkarsh” (without the quotes).

Example

input

output

Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish

题意

A先从（0， 0）开始走，可以向上或向右走 k 个单位，谁先走出以（0， 0）为圆心，半径为 d 的圈谁就输。

分析

根据圆的方程我们可以得出每种情况下最多走几步不走出圆圈，如果是奇数，那么走完之后必定要 E 走，则 E 必输，否则 A 必输。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int t;
ll d,k;
ll maxx;int main()
{scanf("%d",&t);while(t--){maxx = 0;scanf("%lld%lld",&d,&k);for(ll i=0;i<=d;i+=k){ll x = i;ll y = sqrt(d * d - x * x);maxx = max(maxx, x / k + y / k);}if(maxx % 2 == 0) printf("Utkarsh\n");else printf("Ashish\n");}return 0;
}