QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 5193. 挑战图灵奖

统计

题目背景

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

题目描述

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

输入格式

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

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

输出格式

输出共 12 行,第 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=6k=2 情况下对应的染色数为 3

提示

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