← 返回题目列表

Codeforces · 1147/F

F. 之字形游戏

中文机器翻译题面 查看原题

给您一个完整的二分图,其中包含 $$$2n$$$ 个节点,二分的每一侧都有 $$$n$$$ 个节点。节点 $$$1$$$ 到 $$$n$$$ 位于二分的一侧,节点 $$$n+1$$$ 到 $$$2n$$$ 位于另一侧。您还会获得一个描述边权重的 $$$n \times n$$$ 矩阵 $$$a$$$。 $$$a_{ij}$$$ 表示节点$$$i$$$ 和$$$j+n$$$ 之间的边的权重。每条边都有不同的权重。

Alice 和 Bob 正在该图上玩游戏。首先,爱丽丝选择为自己扮演“增加”或“减少”的角色,而鲍勃则选择另一个选择。然后她在图的任何节点上放置一个令牌。然后,Bob 沿着与该节点相关的任何边移动令牌。他们现在轮流玩下面的游戏,爱丽丝先玩。

当前玩家必须将令牌从当前顶点移动到某个相邻的未访问顶点。令 $$$w$$$ 为所遍历的最后一条边的最后权重。如果玩家玩“递增”游戏,则遍历的边必须严格大于 $$$w$$$,否则,必须严格小于 $$$w$$$。第一个无法采取行动的玩家失败。

您将获得 $$$n$$$ 和图的边权重。你可以选择扮演爱丽丝或鲍勃,并且你将与法官对战。您必须赢得所有比赛,您的答案才会被判定为正确。

互动

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试都以整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) 开始——二分区每一侧的节点数。

接下来的 $$$n$$$ 行包含 $$$n$$$ 整数 $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq n^2$$$)。 $$$a_{ij}$$$表示节点$$$i$$$和节点$$$j+n$$$之间的边的权重。所有 $$$a_{ij}$$$ 都是不同的。

首先打印字符串“A”或“B”,表示您要玩的玩家(“A”代表 Alice,“B”代表 Bob)。

如果扮演 Alice,首先打印“I”或“D”(表示您选择“增加”还是“减少”)。然后,打印您希望开始的节点。

如果扮演鲍勃,读入字符“I”或“D”(表示法官选择“增加”还是“减少”),然后读入法官选择开始的节点。

要进行移动,请打印您想要前往的节点的索引。要读取法官采取的行动,请从标准输入中读取一个整数。

如果法官回答 $$$-1$$$,则意味着法官已确定其没有合法行动(或者可能刚刚放弃)并且您赢得了此案。立即停止处理此案例并开始处理下一个案例。

如果法官回答$$$-2$$$,则意味着法官判定你的棋步无效,因此你应该立即退出,以免得到其他判决。

如果您无法采取行动或放弃,请打印$$$-1$$$,然后立即退出。这会给你一个错误答案的判决。

打印移动后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

要破解,请使用以下格式。请注意,您只能使用一个测试用例进行破解。

第一行应包含单个整数 $$$t$$$ ($$$t=1$$$)。

第二行应包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$)。

接下来的 $$$n$$$ 行每行应包含 $$$n$$$ 个整数,即 $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq n^2$$$)。 $$$a_{ij}$$$表示节点$$$i$$$和节点$$$j+n$$$之间的边的权重。所有 $$$a_{ij}$$$ 必须不同。

法官将在本案与被黑客攻击的程序中采取一致随机的合法棋步。如果没有剩余合法步数,它将放弃并宣布玩家为获胜者。

示例

输入 #1

2
3
3 1 9
2 5 7
6 4 8
6
-1
1
1
I 1
-1

输出 #1

A
D 3
2
B
2

注意

第一个示例有两个测试用例。在第一个测试用例中,图表如下所示。

在示例输出中,玩家决定扮演 Alice 并选择“递减”并从节点 $$$3$$$ 开始。法官通过移动到节点 $$$6$$$ 来做出响应。之后,玩家移动到节点$$$2$$$。此时,法官没有更多动作(因为重量必须“增加”),因此它放弃并打印 $$$-1$$$。

在下一种情况下,我们有两个节点通过权重 $$$1$$$ 的边连接。玩家决定扮演鲍勃。无论法官选择什么,玩家都可以将令牌移动到另一个节点,而法官没有移动,因此将失败。