CF1931E Anna and the Valentine's Day Gift

Sasha 在情人节送给 Anna 一个包含 $n$ 个整数的列表 $a$。Anna 并不需要这个列表，于是她提议通过玩一个游戏来销毁它。 两位玩家轮流操作。Sasha 是个绅士，所以他让 Anna 先手。 - 在她的回合，Anna 必须从列表中选择一个元素 $a_i$，并将其各位数字反转。例如，如果 Anna 选择值为 $42$ 的元素，它会变成 $24$；如果 Anna 选择值为 $1580$ 的元素，它会变成 $851$。注意，反转后前导零会被去除。此操作后，列表中的元素个数不变。 - 在他的回合，Sasha 必须从列表中取出两个不同的元素 $a_i$ 和 $a_j$（$i \ne j$），将它们按任意顺序拼接起来，并将结果插入回列表。例如，如果 Sasha 选择值为 $2007$ 和 $19$ 的元素，他可以将这两个元素从列表中移除，并加入整数 $200719$ 或 $192007$。此操作后，列表中的元素个数减少 $1$。 玩家不能跳过回合。游戏在 Sasha 无法操作时结束，即 Anna 操作后列表中只剩下一个数。如果这个整数不小于 $10^m$（即 $\ge 10^m$），则 Sasha 获胜。否则，Anna 获胜。 可以证明，游戏一定会结束。请判断如果双方都采取最优策略，谁会获胜。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^6$），分别表示列表中的整数个数和决定 Sasha 获胜的参数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示 Sasha 送给 Anna 的列表。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行： - 如果 Sasha 在最优策略下获胜，输出 "Sasha"； - 如果 Anna 在最优策略下获胜，输出 "Anna"。

考虑第一个测试用例。 Anna 可以反转整数 $2$，然后 Sasha 可以将 $2$ 和 $14$ 拼接，得到整数 $214$，它大于 $10^2 = 100$。如果 Anna 反转的是 $14$，Sasha 可以将 $41$ 和 $2$ 拼接，得到整数 $412$，它也大于 $10^2 = 100$。Anna 没有其他选择，因此她会输。 由 ChatGPT 4.1 翻译