← 返回题目列表

AtCoder · ijpc_honest

C. 诚实的狐狸和不诚实的人

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

狐狸二郎是一只旅行狐狸。有一天,二郎徒步旅行时,来到了一个岔路口。

一条路的尽头就是“骗子村”,那里有很多只会说谎的坏人。路的另一端是精事村,那里有很多从不说谎的善良狐狸。

二郎自然想去“精事木村”,可惜岔路口没有任何指示牌。很可能是某个坏人在搞鬼。

在那条路附近 N 看起来有人。其中有一些是“骗子村”的坏人。其他人类实际上是来自“精事村”的善良狐狸,他们伪装成人类以避免被坏人戏弄。

光凭外表是无法判断一个人是“精事村”的狐狸还是“骗子村”的人。二郎就是那个 N 我想通过询问人们的问题来识别所有来自“精事村”的狐狸。

问太多的问题会占用很多时间,而且会让二郎的脑袋一片混乱。你能帮二郎问一些问题,让他能正常去精事村吗?

課題

N 有人,0 它们的编号最大为 N-1 它们用不同的整数编号,最大为 。每个人要么是诚实的,要么是骗子,我们希望通过重复以下两类问题来识别所有诚实的人。

  • 有人 i 为了“人” j 诚实吗? ” 对于
  • 有人 i 为了 ”N 有多少人是诚实的? ”

具有以下参数的过程 识别(N) 实施 :

  • N ——人数。对人们 它们使用不同的整数进行编号,最多为 0 它们的编号最大为 N-1 它们用不同的整数编号,最大为 。

识别(N) 实施 里面 问题(Q, i, j) 可以重复调用。问题(Q, i, j) 的规格如下:

  • Q=1 当 什么时候 问题(Q, i, j) 是一个人 i 为了“人” j 诚实吗? ”是问题的答案,返回值代表Yes 1 或否 0 中的任意一个。
  • Q=2 什么时候 问题(Q, i, j) 是一个人 i 为了 ”N 有多少人是诚实的? ”是问题的答案。返回值为 小于或等于 0 以上 N 的整数。此时 j 的值在内部被丢弃,因此您指定什么并不重要。
  • 其他 值为 Q 如果调用 问题(Q, i, j) ,会被认为是无效的库调用,会被判断为不正确。

当被问到问题时,诚实的人总是给出正确的答案,而说谎者总是给出错误的答案。骗子的回答可以是任何错误,但可以保证的是,如果重复问同一个问题,骗子会给出相同的答案。

重复问题并询问每个人 确定一个人在 i 方面是诚实的还是说谎的 答案(i, X) 致电 。X 是一个人 i 代表诚实。 1 或骗子 0 中的任意一个。答案(i, X) 致电 是什么? 它可以按 i 顺序调用,但必须为每个人调用一次。

然而,无论你如何提问,你都不一定能识别出所有诚实的人。在这种情况下 切勿致电 识别(N) 实施 是 答案(i, X) 致电 而是 不可能() 您需要调用 来完成。识别(N) 实施 没有返回值。

此外 问题(Q, i, j) 保证不会返回矛盾的答案。即 至少有一种诚实人组合满足 问题(Q, i, j) 的所有结果。

例

例1

N = 2 考虑 的情况。问题 假设您使用以下参数调用 并得到如下所示的响应。

参数 返回值
问题(1, 0, 1) 0
问题(2, 1, -1) 0

这是一个人 0 是“人” 1 诚实吗? “如果你对这个问题回答“否”, 1 是“2 有多少人是诚实的? ” 对于这个问题 0 表示您已回复某人。 假设

人 1 是一个诚实的人,那么至少有一个诚实的人,这与问题的答案相矛盾。 1 是个骗子。另一方面,人们 他很诚实,因为他给出了关于 0 是一个人 1 的正确答案。因此 识别 看起来像这样: 答案 必须拨打 电话。

参数
答案(0, 1)
答案(1, 0)

例2

N = 2 考虑 的情况。问题 假设您使用以下参数调用 并得到如下所示的响应。

参数 返回值
问题(2, 0, -1) 2
问题(2, 1, -1) 2
问题(1, 0, 1) 1
问题(1, 1, 0) 1

这是一个人 0, 1 双方都声称有两个诚实的人,并且各自声称对方是诚实的。

满足本题结果的组合是 有两种情况, 0, 1 都是诚实的,一种是骗子,不能再问其他问题。因此 识别 是 不可能 来完成。

小課題

小課題 1 (16 点)

  • 1 ≤ N ≤ 10 您调用
  • 识别(N) 实施 是 问题(Q, i, j) 多少次并不重要。

小課題 2 (29 点)

  • 1 ≤ N ≤ 1 000
  • 识别(N) 实施 是 问题(Q, i, j) 多少次并不重要。

小課題 3 (17 点)

  • 1 ≤ N ≤ 100 000
  • 识别(N) 实施 是 它可能以 问题(Q, i, j) 被调用的次数是 必须小于或等于 200 500 倍。

小課題 4 (38 点)

  • 1 ≤ N ≤ 100 000
  • 识别(N) 实施 是 它可能以 问题(Q, i, j) 被调用的次数是 必须小于或等于 100 500 倍。

实施细节

制限

  • CPU时间限制:1秒
  • 内存限制:256 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹:诚实/(原型: 诚实.zip)
  • 竞争对手实现的文件:或honest.cpp
  • 提交文件接口:honest.h
  • 示例评分程序:或grader.cpp
  • 评分程序的示例输入:grader.in.1、grader.in.2、...
    注意:示例评分程序按以下格式读取输入。
    • 1 行目: N
    • 2 行目: N 个整数 X[0], X[1], ..., X[N-1] 用空格分隔。X[i] 是一个人 i 表明此人是诚实的还是说谎的。
    • 3 行目: N 个整数 A[0], A[1], ..., A[N-1] 用空格分隔。A[i] 是一个人 i 代表当被问及诚实人的数量时的回答。
  • 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
    注意:示例评分程序按以下格式写入输出。
    • 如果诚实人完全可识别: N 个整数 X[0], X[1], ..., X[N-1] 是用空格分隔的输出。含义与输入相同。
    • 如果无法识别诚实者:字符串“不可能。" 输出仅包含 " 的行。
  • 示例评分程序按以下格式将信息写入标准错误输出。
    • 1 行目: "#问题= 输出 Q“。然而, Q 在本次运行中 调用 问题 假设您使用以下参数调用 的次数。