Codeforces 1451D. Circle Game(博弈)
程序员文章站
2022-03-15 23:36:50
...
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;
}
推荐阅读
-
Codeforces 1451D. Circle Game(博弈)
-
Ticket Game CodeForces - 1215D(博弈题,巴什博弈思维)
-
Codeforces 1215 D. Ticket Game(博弈论)
-
Codeforces Round #666 (Div. 2)D. Stoned Game(博弈问题)
-
Codeforces Round #685 (Div. 2)——D. Circle Game
-
D. Stoned Game(博弈问题) Codeforces Round #666 (Div. 2)
-
Codeforces 1451D. Circle Game(博弈)
-
Circle Game CodeForces - 1451D( 博弈 +思维 )
-
Codeforces 1451D. Circle Game(博弈)