← 返回题目列表

AtCoder · pakencamp_2024_day2_g

G. 贪婪机器人

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

配点 : 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 可以通过多条道路行驶

小課題

  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 。对于此子任务,将根据以下方式确定分数:
    • 关于该子任务对应的测试用例,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 ,判断器返回你要移动到的路口号。
!
2
1 2 1
2 3 2
输出问题的答案。

评分注意事项

对于所有测试用例,实际评分程序不是自适应的。这意味着评分程序从一开始就有固定的路径信息。