QOJ.ac

QOJ

時間限制: 1.0 s 記憶體限制: 512 MB 總分: 100 可 Hack ✓

#7062. 王子与公主

统计

Mochi 王国的 Mochi 王子爱上了 Tofu 王国的 Tofu 公主,但 Tofu 王国的女王不同意这门婚事。

女王向他们的爱情发起了挑战,并为 Mochi 王子布置了一项任务。完成这项任务是他们获得幸福的前提。由于能力有限,Mochi 王子不得不向你寻求帮助。

任务如下:Tofu 公主、Tofu 国王、女王、大臣、侍女、厨师以及许多其他人都在一起执行任务,且每个人都住在不同的房间里。注意,没有空房间。每个人都知道自己住在哪里,也知道其他人住在哪里。

Mochi 王子需要找到公主。他可以向任何人询问以下三种类型的问题:

  • 你是谁?
  • 指定房间里住的是谁?
  • Tofu 公主住在哪个房间?

他们从不拒绝回答问题,但可能不会说实话。支持这门婚事的人(包括 Tofu 公主本人)会提供事实。反对者(如女王)总是会提供错误的答案。其他参与者的回答则是随意的。

Mochi 王子不想花费太多时间,因此他希望询问次数尽可能少。你能告诉他在任何情况下,为了确定他心爱的人在哪里,他真正需要询问的最少问题数量吗?但有时这项任务是不可能完成的,在这种情况下,你也应该提醒他开始一段新的恋情。

输入格式

输入仅一行,包含三个整数 $a$ ($1 \le a \le 2 \times 10^5$),$b$ 和 $c$ ($0 \le b, c \le 2 \times 10^5$),分别代表支持这门婚事的参与者人数、反对这门婚事的参与者人数以及对此事不关心的参与者人数。

输出格式

如果 Mochi 王子无法确定公主的位置,输出 “NO”(不含引号)。否则,第一行输出 “YES”(不含引号),第二行输出王子需要询问的最少问题数量。

样例

输入 1

2 0 0

输出 1

YES
1

输入 2

1 1 0

输出 2

NO

说明

在第二个样例中,Mochi 王子可以向两位参与者询问所有可能的问题。然而,当他们总是给出相同的回答时,王子无法确定公主在哪里。因此答案是 “NO”。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.