← 返回题目列表

Codeforces · 1137/D

D. 合作游戏

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

这是一个交互问题。

Misha喜欢玩信息不完全的合作游戏。今天他建议十个朋友玩一个合作游戏“湖”。

Misha 已经为即将到来的游戏想出了一个场地。该游戏的场是由两部分组成的有向图。第一部分是沿着湖岸的一条道路,它是 $$$c$$$ 个顶点的循环。第二部分是一条从家到湖边的路径,它是一条由 $$$t$$$ 个顶点组成的链,从这条链的最后一个顶点到沿海岸的道路上有最美丽的湖景的顶点有一条边,也称为终点顶点。 Misha 决定对这个领域保密,所以没有人知道 $$$t$$$ 和 $$$c$$$。

请注意,场的每个顶点都只有一条出边,并且除起始顶点和终点顶点之外的所有顶点都恰好有一条入边。起始顶点没有传入边,结束顶点有两个传入边。

在游戏开始时,所有十名玩家的棋子(用从 $$$0$$$ 到 $$$9$$$ 的连续整数索引)都位于起始顶点。之后,在每个回合中,一些玩家可以要求 Misha 同时沿着相应的边缘移动他们的棋子。 Misha 不会回答超过 $$$q$$$ 的此类问题。每次移动后,米莎都会告诉玩家谁的棋子在相同的顶点,谁的棋子在不同的顶点。

游戏的目标是将所有棋子移动到终点。 Misha 的朋友们在不知道 $$$c$$$、$$$t$$$ 和 $$$q$$$ 的情况下不知道如何在这样的游戏中获胜,但幸运的是他们是你的朋友。帮助他们:协调他们的行动来赢得比赛。

Misha 绘制了这样一个域 $$$1 \le t, c$$$, $$$(t+c) \leq 1000$$$ 和 $$$q = 3 \cdot (t+c)$$$。

输入

没有输入——直接进入交互部分。

互动

要发出移动好友的命令,请打印“next”,然后输入要移动的好友的空格分隔索引。例如,要发出命令移动索引为 $$$0$$$、$$$2$$$、$$$5$$$ 和 $$$9$$$ 的朋友,请打印“next 0 2 5 9”。在每一回合,你必须移动至少一个朋友。

作为答案,首先读取整数 $$$k$$$,然后将 $$$10$$$ 数字分为 $$$k$$$ 空格分隔的组。同一组中的索引对应的好友位于同一顶点。不同组中索引对应的好友位于不同的顶点。每组中的索引按升序排列。

例如,答案“2 05 12346789”表示索引为 $$$0$$$ 和 $$$5$$$ 的好友位于一个顶点,而所有其他好友位于相同但不同的顶点。答案“4 01 567 234 89”意味着 Misha 的朋友位于四个不同的顶点:索引为 $$$0$$$ 和 $$$1$$$ 的朋友在第一个,索引为 $$$5$$$、$$$6$$$ 和 $$$7$$$ 的朋友在第二个,索引为 $$$2$$$、$$$3$$$ 和 $$$3$$$ 的朋友在第二个。 $$$4$$$ 在第三个,指数为 $$$8$$$ 和 $$$9$$$ 的朋友在第四个。

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

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

回答“stop”而不是有效的,意味着您进行了无效的查询。收到“停止”后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

为了破解,在一行中打印两个整数 $$$t$$$ 和 $$$c$$$ ($$$1 \le t, c$$$, $$$(t+c) \leq 1000$$$)。

输出

当所有朋友聚集在终点顶点后,打印“done”并终止你的程序。

示例

输入 #1

2 05 12346789

3 246789 135 0

3 246789 0 135

3 246789 0 135

2 135 0246789

1 0123456789

输出 #1

next 0 5

next 0 1 3

next 2 3 0 1 4 5 6 7 8 9

next 9 8 7 6 5 4 3 2 1 0

next 0 1 3 5

next 1 3 5

done

注意

在示例中,输入和输出值对齐只是为了简化按时间顺序解释它们。在实际交互中,不应出现“额外”换行符。

示例中,好友移动如下: