CF1451D-Circle Game

题目:

题目描述:

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 $ p^2 + q^2 \leq d^2 $ 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.

输入格式:

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

The only line of each test case contains two space separated integers $ d $ ( $ 1 \leq d \leq 10^5 $ ) and $ k $ ( $ 1 \leq k \leq d $ ).

输出格式:

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

样例:

样例输入1:

1
2
3
4
5
6

5
2 1
5 2
10 3
25 4
15441 33

样例输出1:

1
2
3
4
5

Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include "ybwhead/ios.h"
int main()
{
	int TTT;
	yin>>TTT;
	while(TTT--)
	{
		long long d,k;
		yin>>d>>k;
		long long x=0,y=0;
		while(1)
		{
			if(x<=y&&(x+k)*(x+k)+y*y<=d*d)
				x+=k;
			else if(x>y&&x*x+(y+k)*(y+k)<=d*d)
				y+=k;
				else break;
		}
		if(x==y)
		{
			puts("Utkarsh");
		}
		else
		{
			puts("Ashish");
		}
	}
	return 0;
}