P2252-[SHOI2002]取石子游戏|【模板】威佐夫博弈
题目:
题目描述:
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
输入格式:
输入共一行。
第一行共两个数a, b，表示石子的初始情况。
输出格式:
输出共一行。
第一行为一个数字1、0或-1，如果最后你是胜利者则为1；若失败则为0；若结果无法确定则为-1。
样例:
样例输入1:
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // Problem: P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2252
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
const double gold = (sqrt(5.0) + 1.0) / 2.0;
int main()
{
long long n, m;
yin >> n >> m;
if (n < m)
swap(n, m);
if (m == (long long)(gold * (n - m)))
puts("0");
else
puts("1");
return 0;
}
|