测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A16714. Game with a Fraction

编程题 普及/提高-
知识点

题目描述

Alice 和 Bob 有两个整数 $p$ 和 $q$,他们用这两个数玩一个游戏。两人轮流行动,Alice 先手。在自己的回合中,玩家可以执行以下两种操作之一:

- 让 $p$ 减 $1$(当前 $p>0$ 时可以执行该操作);
- 让 $q$ 减 $1$(当前 $q>1$ 时可以执行该操作)。

当 $p=0$ 且 $q=1$ 时,游戏结束。

如果在游戏过程中,分数 $\frac{p}{q}$ 的值等于 $\frac{2}{3}$,则 Bob 获胜;否则,Alice 获胜。

给定 $p$ 和 $q$ 的初始值,假设双方都以最优策略进行游戏,判断谁会获胜。

输入格式

输入包含多组测试数据。第一行为测试用例组数 $t$,其中 $1 \le t \le 10^4$。

每组测试数据占一行,包含两个整数 $p$ 和 $q$,满足 $1 \le p, q \le 10^{18}$。

输出格式

对于每组输入,输出以下内容之一:

- 如果 Alice 获胜,输出 "Alice";
- 如果 Bob 获胜,输出 "Bob"。

输入输出样例

输入 #1
6
4 6
10 14
15 15
7 12
7000000000000000 10487275715782582
1000000000000000000 1000000000000000000
输出 #1
Bob
Bob
Alice
Alice
Bob
Alice

说明/提示

在第一个输入用例中,分数已经等于 $\frac{2}{3}$,因此 Bob 获胜。

在第二个输入用例中,游戏可能经过如下步骤:

- 初始时 $p = 10, q = 14$;
- Alice 行动后 $p = 9, q = 14$;
- Bob 行动后 $p = 9, q = 13$;
- Alice 行动后 $p = 9, q = 12$;
- Bob 行动后 $p = 8, q = 12$。

这时 Bob 获胜,因为 $\frac{8}{12} = \frac{2}{3}$。事实上,在这个例子中,双方都以最优策略下,Bob 总会获胜。

在第三个输入用例中,Alice 的最优策略是尽量让 $q$ 减小。在本例中,不论 Bob 如何行动,最后都将是 Alice 获胜。
上一题 去做题 下一题