题目描述
https://codeforces.com/contest/1451/problem/D
Solution
首先这是个单一游戏的博弈论题，所以基本要跟 $sg$ 说再见了
我们考虑如果 $(x,y)$ 再走一步就出界，则 $(x,y)$ 是必败态
那么 $(x-k,y)$ 和 $(x,y-k)$ 是必胜态
那么对于 $(x-k,y-k)$ 只能到达 $(x-k,y)$ 和 $(x,y-k)$，所以 $(x-k,y-k)$ 一定是必败态
以此类推，如果 $(0,0)$ 是必败态，则说明 $(mk,mk)$ 是必败态，其中 $(mk,mk)$ 一次就可以走出界
反正 $(0,0)$ 一定是必胜态
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
| #include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
ll n, k, m, M;
inline ll S(ll x) { return x * x; }
void work() {
cin >> n >> k; m = sqrt(n * n / (2 * k * k));
if (S(m + 1) * S(k) + S(m) * S(k) > n * n) cout << "Utkarsh" << "\n";
else cout << "Ashish" << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|