QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

#5193. 挑战图灵奖

الإحصائيات

题目背景

图染色问题是这样的——给定一个 $n$ 个点,$m$ 条边的图,要求将每个点染上一种颜色,满足任意有边相连的两个点颜色不同,问最少需要多少种颜色。众所周知,图染色是 $\mathsf{NPC}$ 问题之 一,如果有人能在多项式时间内解决图染色问题,那就相当于证明了 $\mathsf{P}=\mathsf{NP}$,恭喜你,下一位图灵奖得主非你莫属!

题目描述

今天,你的好朋友——敏珂找到了你,宣称他证明了半个图染色问题,希望你帮他看看他的做法对不对,如果你能帮他验证,他会考虑与你分享图灵奖的奖金。敏珂宣称自己解决的问题是这样的:对于一个 $n$ 个点的无向图,图上所有节点编号为 $1,2,...n$,两点之间有连边,当且仅当两点编号在模 $n$ 意义下相差不超过 $k$,即 $(x,y)$ 之间有一条无向边,当且仅当 $x \neq y$ 且存在 $i$ 满足 $1 \le i \le k$ ,$(x+i) \equiv y \pmod n$ 或 $(y+i) \equiv x \pmod n$,他能够快速求出这个图的染色数。作为评审,你只需要解决一个判定性问题——对于每组数据,敏珂会给出三个正 整数 $n$,$k$ 和 $x$,表示在给定 $n$ 和 $k$ 时($n$,$k$ 的意义如上文所述),他认为这个图的染色数是 $x$,你需要判断他的答案是否正确。

如果你认为他的答案是正确的,输出一行 Correct, but it doesn't necessarily mean that you can win the Turing Award.;如果你认为他的答案是错误的,在第一行输出 Wrong, don't cheat me, you are too far away from the Turing Award.。为了让你的答案更有信服力,你还需要在第二行输出一个字符 010 表示你认为敏珂的答案小于这个图的实际染色数,1 表示你认为他的答案大于这个图的实际染色数;如果你认为这个问题以当下计算机算力无法作出准确判断,输出一行 The problem is unsolvable, please stop cheating me, Mr.Minke.

输入格式

输入只有一行,包含三个正整数,分别表示 $n$,$k$,$x$,意义如题面所述。

其中 $1\le x, n \le 10^{1,000,000}$,$1 \le k \le 100$,所有输入均为正整数,且对于所有数据,$n$ 只可能满足 $n \le 10^5$ 或 $n \ge 10^{100}$。

输出格式

输出共 $1$ 或 $2$ 行,第 $1$ 行表示你的判断结果,格式如题面所述;

如果你顺利完成判断并认为敏珂的答案是错误的,则需要在第 $2$ 行输出一个字符 0​10 表示敏珂的答案小了,1 表示敏珂的答案大了。

样例数据

样例 1 输入

6 2 4

样例 1 输出

Wrong, don't cheat me, you are too far away from the Turing Award.
1

样例 1 解释

很显然,给 $1-6$ 号点分别染色为 $1,2,3,1,2,3$ 是可行的,所以 $n=6$,$k=2$ 情况下对应的染色数为 $3$。

提示

  1. 如果没有 idea,请再次阅读题面给的数据范围,也许能对解题有一些帮助。
  2. Hint 1 可能没有用。
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.