← 返回题目列表

AtCoder · pakencamp_2022_day2_g

G. 最糟糕的城镇

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

配点 : 700 点

問題文

这个问题是一个交互问题。

在Pakencho N 有一座房子, 它的编号为 1, 2, \ldots, N 。它还连接两个方向的房屋。 0 道路不止一条; 300 我们知道道路少于一条,但我们不知道有多少条路,也不知道每条路连接哪些房屋。然而,没有道路连接两端的同一栋房屋,也没有道路连接同一组房屋。

你已成为帕肯镇镇长,从现在开始,你将 1 我们将一一召开会议。 N 对于每个房屋,您可以决定是否邀请该房屋的居民。

然而,Pakencho是一个非常危险的城镇。尤其是邻居,即。 1 由两条道路连接 2 住在一所房子里的居民很容易在聚会上相遇,然后发生争吵,聚会中的每个人都会卷入其中。

现在,您想了解 Pakencho 有多少条道路以及每条道路连接了哪些房屋。因此,我决定调查帕肯乔的结构,决定每天邀请谁参加聚会,看看是否会爆发斗殴。

这显然是滥用权力, 我们只能在 3200 天之前举行会议。创建一个计划来定义您决定邀请谁参加聚会的策略。

请注意,您不是任何人的邻居。您也可以自己召开会议而不邀请任何人。

制約

  • N 是整数
  • 1 \leq N \leq 200
  • 这条路是 300 不到1本书。
  • 两端相同 1 没有一条路是一所房子。
  • 没有两条道路连接同一组房屋。

小課題

  1. (50 点) N \leq 80
  2. (100 点)对于任何道路,道路连接 2 两栋房子的奇数和偶数不同。
  3. (150 点)哪个房子 关于 a, b, c , 有一条路连接 a 和 b , 如果没有道路连接 a 和 c , 有一条路连接 b 和 c 有一条路相连
  4. (400 点)无附加约束

入出力

首先, N 按以下格式作为输入给出。

N

然后你可以重复这个问题。这个问题被问了多少次了? 不得超过 3200 次。

? S

但是, S 是 0 和 1 组成 它是一个 N , 不得包含除 S_i = 0 如果房子 请不要邀请 i 的居民参加会议。 表示召集 S_i = 1 如果房子 请不要邀请 i 的居民参加会议。

然后评委们将回答问题。此响应是以下字符串之一:

  • Yes :集会中所有参与者都爆发了扭打。
  • No :没有发生扭打。
  • -1 :提出了无效问题或无效输出。这是提出的问题的数量。 包括超过 3200 次的情况。

另外,如果您知道 Parkencho 的结构,请按以下格式输出所有道路。

! M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

这里 M 代表道路数量, i 真正的路是家 这表明 a_i, b_i 已连接。

但是,道路的输出顺序并不重要。另外, a_i, b_i 是否颠倒也没关系。

注意

  • 每次输出后刷新标准输出。否则,判断结果不确定。
  • 如果所有道路都输出后不终止程序,则判断结果不确定。
  • 如果提出错误问题或输出错误,判断结果将不确定。

入出力例

在此输入/输出示例中, 道路是 N=4 还有路 4 有书,每条路都是一个家 显示了打结时与裁判互动的示例 1, 2 、家 2, 3 、家 3, 4 、家 4, 1 。

但是,请注意,这只是输入/输出的示例,并不一定代表有意义的交换。

程序的输入(判断端输出)我的程序的输出
4
? 1011
是
? 0101
No
? 1001
是
! 4
1 2
2 3
3 4
4 1

该输入示例满足子任务的所有约束。