配点 : 100 点
問題文
这个问题是一个交互问题。
在帕肯王国 有 N 交叉路口, 它们的编号最大为1 到 N 。另外,M 有一条书路径,每条路径都是 它连接 2 两个方向的不同交叉路口。2 书中的不同道路从未连接同一组交叉路口。
这些道路 1 以上 K 绘制由以下整数表示的颜色。多条道路可以涂成相同的颜色。然而,在连接到某个交叉口的道路中,存在相同颜色的道路。 2 书的数量永远不会超过一本书。
Akane 开发了一种可以穿过十字路口的机器人。这个机器人有 通过重新排列获得的序列(1, 2, \ldots, K) 通过给出 P = (P_1, P_2, \ldots, P_K) 进行操作。机器人选择连接到当前顶点的路径的颜色。 选择 P 中出现的第一个东西并沿着该路径移动。 (补充:12:40)这个动作 1 每次操作 1 只完成一次。
Akane-san 是交叉路口的数量 N 和颜色类型数量 我只知道 K 。所以茜桑做了以下事情: 調査 至最大 通过执行 10000 次,路径数 M 我想确定每条道路连接的交叉路口数量以及每条道路的颜色。 选择
調査: 頂点 v 并将机器人放置在那里。然后变成机器人 给出 P = (P_1, P_2, \ldots, P_K) 并对其进行操作,找出机器人将要移动的路口号。
然而,由于茜非常忙碌,我想尽量减少调查次数。
请创建一个程序来实施茜的策略。
制約
- 3 \leq N \leq 500
- N - 1 \leq M \leq 500
- 2 \leq K \leq 500
- 从任何路口到任何路口,0 可以通过多条道路行驶
小課題
- (3 点) N=3, M=2, K=2, \mathrm{subtask\_id} = 1
- (3 点) N=3, M=2, \mathrm{subtask\_id} = 2
- (4 点) K=2, \mathrm{subtask\_id} = 3
- (90 点) \mathrm{subtask\_id} = 4 。对于此子任务,将根据以下方式确定分数:
- 关于该子任务对应的测试用例,1 如果任何项目获得非 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) \times 3 点
- Q \leq 5000 什么时候 90 点
入出力
一、路口数量 N ,颜色类型数量 K,子任务编号 \mathrm{subtask\_id} 按以下格式作为输入给出。
N K \mathrm{subtask\_id}
然后你 10000 进行以下调查。 v 和 P = (P_1, P_2, \ldots, P_K) 必须按以下格式输出到标准输出。
? v P_1 P_2 \ldots P_K
这里 必须是满足 v 是 1 \leq v \leq N 的整数。另外, 它必须是通过重新排列(P_1, P_2, \ldots, P_K) 是 (1, 2, \ldots, 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 是道路两端的交叉口编号,C_i 代表道路的颜色。
但是,道路的输出顺序,以及 A_i 和 B_i 的顺序是任意的。
法官
-
打印后,必须刷新标准输出。否则,判断结果不确定。
-
程序必须在打印答案后立即退出。否则行为是未定义的。
- 如果提出错误问题或输出错误,判断结果将不确定。
入出力例
以下示例不一定是有意义的交互。
| 入力 | 出力 | 説明 |
|---|---|---|
3 2 1 | 一、路口数量 N ,最大色数 我们将按照 K,子任务编号 \mathrm{subtask\_id} 。 | |
? 2 1 2 | v = 2, P = (P_1, P_2) = (1, 2) 进行调查。 | |
1 | 机器人是一个路口 1 ,判断器返回你要移动到的路口号。 | |
! | 输出问题的答案。 |
评分注意事项
对于所有测试用例,实际评分程序不是自适应的。这意味着评分程序从一开始就有固定的路径信息。