AT_pakencamp_2024_day2_g Greedy Robot

**本题为交互题。** 在「パ研王国」中有 $N$ 个路口，编号为 $1$ 到 $N$。有 $M$ 条道路，每条道路双向连接两个不同的路口。不存在两条不同的道路连接同一对路口。 这些道路被涂上了 $1$ 至 $K$ 的某个整数颜色。可能有多条道路颜色相同。但是，每个路口连接的所有道路中，不会有两条或以上使用相同颜色。 茜同学开发了一个可以在路口间移动的机器人。你可以给这个机器人一个通过排列 $(1,2,\ldots,K)$ 得到的序列 $P=(P_1, P_2, \ldots, P_K)$。机器人会从当前路口连接的道路中，选择第一个出现在 $P$ 中的颜色的道路，并沿着该道路移动到相邻的路口。（补充：每次操作只能移动一次。） 茜同学仅已知路口个数 $N$ 与颜色种类 $K$。她希望通过最多 $10000$ 次“调查”，确定道路数 $M$、每条道路连接的路口编号、以及每条道路的颜色。 **调查**：选择一个路口 $v$，将机器人放置于此。随后给机器人一个排列 $P=(P_1, P_2, \ldots, P_K)$ 并令其移动，观察机器人移动的下一个路口编号。 茜同学希望尽量减少调查次数。 请你实现茜同学的策略的程序。

首先输入交点个数 $N$、颜色种类数 $K$、子任务编号 $\mathrm{subtask\_id}$，格式如下： > $N$ $K$ $\mathrm{subtask\_id}$ 之后，你可以进行不超过 $10000$ 次调查。每次必须按如下格式输出 $v$ 与排列 $P$： > ? $v$ $P_1$ $P_2$ $\ldots$ $P_K$ 其中 $v$ 满足 $1 \leq v \leq N$，且 $(P_1, P_2, \ldots, P_K)$ 是 $1$ 到 $K$ 的一个全排列。 每次询问后，标准输入会返回如下格式的查询结果： > $\mathrm{ans}$ 其中 $\mathrm{ans}$ 是 $1$ 到 $N$ 的整数，表示机器人移动到的下一个路口编号。 最后，你需要按如下格式输出答案： > ! $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$ 其中 $M$ 表示道路数，$A_i$ 与 $B_i$ 表示第 $i$ 条道路连接的两个路口编号，$C_i$ 表示该道路的颜色。 输出道路、以及 $A_i$ 和 $B_i$ 的顺序任意。

无

## 子任务 1. ($3$ 分) $N=3, M=2, K=2, \mathrm{subtask\_id}=1$ 2. ($3$ 分) $N=3, M=2, \mathrm{subtask\_id}=2$ 3. ($4$ 分) $K=2, \mathrm{subtask\_id}=3$ 4. ($90$ 分) $\mathrm{subtask\_id}=4$。本子任务得分如下： - 若本子任务的任意一个测试点没有 AC，得分为 $0$； - 否则，记所有测试点中调查次数最大值为 $Q$，得分为： - 若 $8750 < Q \leq 10000$，得 $5$ 分； - 若 $5003 < Q \leq 8750$，得 $\left\lfloor\frac{20000}{Q - 4750}\right\rfloor$ 分； - 若 $5000 < Q \leq 5003$，得 $90 - (Q-5000)\times3$ 分； - 若 $Q \leq 5000$，得 $90$ 分。 ## 评测 - **每次输出后，必须刷新标准输出，否则评测结果不可预知。** - 输出答案后，程序应立即终止，否则行为不确定。 - 若询问格式、输出结果非法，评测结果不可预知。 ## 输入输出样例 以下示例仅用于说明交互流程。 输入 | 输出 | 说明 --- | --- | --- `3 2 1` | | 首先输入路口数量 $N$、颜色 $K$、子任务编号 | `? 2 1 2` | 查询 $v=2, P=(1,2)$ `1` | | 机器人移动到路口 $1$，评测返回下一个路口编号 | `!

2

1 2 1

2 3 2` | 输出答案，包括每条道路两端路口及颜色 ## 评分注意事项 所有测试点的评分程序均为非自适应，即所有评测数据在执行前即全部确定。 ## 数据范围 - $3 \leq N \leq 500$ - $N-1 \leq M \leq 500$ - $2 \leq K \leq 500$ - 任意两点连通 由 ChatGPT 5 翻译