「CF1451D」 Circle Game

题意

在一个二维平面直角坐标系上，有一个棋子在 $(0,0)$ 位置，两玩家轮流操作。在一次操作中，当前玩家必须将棋子向右移 $k$ 个单位，或向上移 $k$ 个单位，（即从 $(x,y)$ 到 $(x+k,y)$ 或 $(x,y+k)$ ）且要保证移动后得点在以原点为圆心半径为 $d$ 的圆内，即 $x^2+y^2\le d^2$ ，最后不能移动玩家输。问先手后手谁必胜。

题解

考虑后手这样得操作：先手向右，后手向上；先手向上，后手向右。即后手使棋子一直在 $y=x$ 上。

令正整数 $z$ 满足 $(zk,zk)$ 在圈内且最大。

倘若 $(zk+k,zk)$ 出圈了，那么后手必胜。显然后手执行上面得操作一定能到 $(zk,zk)$ ，而此时先手无论走哪都出圈。

若 $(zk+k,zk)$ 在圈内，那先手必胜，考虑先手先把第一步走出，之后后手无论走哪里，先手可以把棋放到 $y=x+k$ 或 $y=x-k$ 上，先手一定能把棋搞到 $(zk+k,zk)$ 上，那么后手无论怎么走一定出圈。

根据定义 $z$ 是最大得满足 $2z^2k^2 \le d^2$ 的正整数，那么

$2(z+1)^2k^2\gt d^2$

向右出圈，且

$z^2k^2+(z+2)^2k^2 \ge 2(z+1)^2k^2\gt d^2$

向上也出圈，得证。

CODE

代码十分简洁

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;ll d,k;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld",&d,&k);
        ll z=1.0*d/(1.0*sqrt(2)*k);
        ll x=z*k,y=(z+1)*k;
        if(x*x+y*y>d*d) puts("Utkarsh");
        else puts("Ashish");
    }
}