链接:https://ac.nowcoder.com/acm/contest/59840/H 来源:牛客网 Alice和Bob在玩一个棋盘游戏,在他们面前有两个棋盘,第一个棋盘有n个棋子,第二个棋盘 有m个棋子,双方轮流拿棋子,每次拿棋子的时候只能通过下面两种方式拿: 1.从第一个棋盘上面拿走一个棋子,从第二个棋盘拿走两个棋子。 2.从第一个棋盘上面拿走两个棋子,从第二个棋盘拿走一个棋子。 每次取之前必须保证当前两个棋盘上有一个棋盘的棋子数量大于等于取的数量。 有一方无法取棋子则算输,Alice先取,如果两个人都会以最有策略进行游戏,最终谁能获胜? 输入描述: 第1行输入一个正整数T(1<=T<=100000),代表数据组数。 第2-T+1行每行输入两个整数n,m(1<=n,m<=10^9),代表两个棋盘上棋子的数量。 输出描述: 对于输入的每一组数据,输出获胜者的名字。 示例1 输入 复制 6 2 1 2 3 1 1 3 3 8 10 6 7 输出 复制 Alice Alice Bob Bob Alice Bob用代码表示出来
时间: 2024-03-30 09:36:28 浏览: 185
以下是使用C++实现的代码:
```cpp
#include <iostream>
using namespace std;
string solve(int n, int m) {
int sum = n + m;
if (sum % 3 == 0 && 2 * n >= m && 2 * m >= n) {
return "Alice";
} else {
return "Bob";
}
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
cout << solve(n, m) << endl;
}
return 0;
}
```
代码思路:
1. 如果两个棋盘上的棋子数量之和不能被3整除,则无法找到符合条件的拿棋子方法,此时先手必输。
2. 如果两个棋盘上的棋子数量之和能被3整除,则先手有必胜策略当且仅当满足以下条件:
- 取走一个棋盘上的一个棋子和另一个棋盘上的两个棋子,或者取走一个棋盘上的两个棋子和另一个棋盘上的一个棋子,这两种方法的棋子数量之和必须等于总棋子数量之和除以3。
- 取走棋盘上的棋子不能导致另一个棋盘上的棋子数量小于当前取走的棋子数量。即取走1个棋盘上的1个棋子和另一个棋盘上的2个棋子时,必须满足2 * n >= m;取走1个棋盘上的2个棋子和另一个棋盘上的1个棋子时,必须满足2 * m >= n。
3. 根据上述条件判断先手是否有必胜策略,若有则先手获胜,否则后手获胜。
代码中使用了一个`solve`函数,用于判断给定的棋盘情况下先手是否获胜,并返回获胜者的名字。在`main`函数中循环读入每组数据,调用`solve`函数并输出结果。
阅读全文