← 返回题目列表

AtCoder · arc070_d

F. 诚实还是不友善

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

分数: 1300 点

问题陈述

这是一项交互式任务。

AtCoDeer 鹿遇到了 N 人。为了方便起见,对人进行了编号 0 通过 N-1。 其中, A 是 诚实 以及剩余的 B(=N-A) 是 不友善。 所有这些 N 人们知道谁是诚实的,谁是不仁慈的,但AtCoDeer只知道有 A 诚实和 B 不友善的人。 他试图通过向这些人提出问题来识别所有诚实的人 N 人。 对于一个问题,AtCoDeer 选择 a 和 b (0≤a,b≤N-1),并询问人 a 以下问题:“人是 b 诚实吗?”

诚实的人总是会正确回答“是”或“否”。 然而,不友善的人会选择“是”或“否”来回答 任意。 也就是说,不友善的人使用的算法可能不是简单的算法,例如总是撒谎或随机给出五五十个答案。

AtCoDeer最多可以询问 2N 问题。他会一一提出问题,并且在决定下一个要问的问题时可以使用对前一个问题的回答。

识别所有诚实的人。 如果这是不可能的(更正式地说,如果对于任何询问策略 2N 问题,存在一种让不友善的人回答问题的策略,以便有两组或更多可能的诚实人),报告该事实。

约束

  • 1≤A,B≤2000

输入和输出

首先, A 和 B 由标准输入以以下格式给出:

A B

如果无法识别诚实的人,程序必须立即打印以下输出并终止自身:

Impossible

否则,程序将提出问题。 每个问题必须按以下格式写入标准输出:

? a b

在这里, a 和 b 必须是介于 0 和 N-1 (含)。 问题的答案将从标准输入以以下格式给出:

ans

在这里, ans 是 Y or N. Y 代表“是”; N 代表“否”。

最后,答案必须按以下格式写入标准输出:

! s_0s_1...s_{N-1}

在这里, s_i 必须是 1 如果人 i 是诚实的,并且 0 如果人 i 很不友善。

判断

  • 每次输出后,您必须刷新标准输出。 否则你可能会得到 TLE.
  • 打印答案后,必须立即终止程序。否则,法官的行为是不确定的。
  • 当你的输出无效或不正确时,判断的行为是未定义的(它不一定给出 WA).

样品

在以下示例中, A = 2, B = 1,答案是 101.

输入 输出
2 1
? 0 1
N
? 0 2
Y
? 1 0
Y
? 2 0
Y
? 2 2
Y
! 101

在以下示例中, A = 1, B = 2,答案是 Impossible.

输入 输出
1 2
Impossible