#P17807. [Ontak2024]受限Nim
[Ontak2024]受限Nim
题目描述
Alicja 和 Bob 玩一种修改规则后的 Nim 游戏。
初始有 堆物品,第 堆有 个,另给定一个正整数 。双方轮流操作,Alicja 先手。
每次操作,玩家必须选择一堆,从中取走正整数个物品,且不能超过该堆的剩余数量。此外:
- Alicja 第一次操作取走的数量不能超过 。
- 从第二次操作起,每次取走的数量不能超过对方在紧接着的上一次操作中取走的数量。
无法进行合法操作的玩家输掉游戏。
双方都采取最优策略。请判断谁会获胜。
输入格式
第一行包含一个整数 ,表示测试用例数量。
每个测试用例的第一行包含两个整数 。
第二行包含 个整数 ,表示各堆的初始数量。
输出格式
对每个测试用例输出一行:若 Alicja 获胜,输出 Alicja;否则输出 Bob。
数据范围
$$1\le t\le10^6,\quad 1\le n\le10^6,\quad 1\le k,a_i\le10^9.$$所有测试用例的 之和不超过 。
样例
4
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3
2 1
1 1
Alicja
Alicja
Alicja
Bob
子任务
| 额外限制 | 分值 |
|---|---|
| 26 | |
| ,所有测试用例的 之和不超过 , | 8 |
| , | 11 |
| , | 8 |
| 16 | |
| 是 的幂 | 7 |
| 无额外限制 | 8 |