P7608 [THUPC 2021] Challenge the Turing Award

The graph coloring problem is as follows: given a graph with $n$ vertices and $m$ edges, you need to color each vertex with a color such that any two vertices connected by an edge have different colors. The question is the minimum number of colors needed. As everyone knows, graph coloring is one of the NPC problems. If someone can solve the graph coloring problem in polynomial time, that would be equivalent to proving $P = NP$. Congratulations, you would definitely be the next Turing Award winner.

Today, your good friend—Minke—came to you and claimed that he proved “half” of the graph coloring problem, and he wants you to check whether his method is correct. If you can help him verify it, he will consider sharing the Turing Award prize money with you. Minke claims that he solved the following problem: for an undirected graph with $n$ vertices, where all vertices are numbered $1,2,\ldots,n$, there is an edge between two vertices if and only if their indices differ by at most $k$ in modulo $n$. That is, there is an undirected edge between $(x,y)$ if and only if $x \neq y$ and there exists an integer $i$ satisfying $1 \le i \le k$ such that $$(x+i) \equiv y \pmod n$$ or $$(y+i) \equiv x \pmod n $$ He can quickly compute the chromatic number of this graph. As a judge, you only need to solve a decision problem: for each test case, Minke will give three positive integers $n$, $k$, and $x$. When $n$ and $k$ are fixed (with the meanings described above), he believes the **chromatic number** of this graph is $x$. You need to determine whether his answer is correct. If you think his answer is **correct**, output one line `Correct, but it doesn't necessarily mean that you can win the Turing Award.`. If you think his answer is **wrong**, output `Wrong, don't cheat me, you are too far away from the Turing Award.` in the first line. To make your answer more convincing, you also need to output a character `0` or `1` in the second line: `0` means you think Minke’s answer is smaller than the actual chromatic number of this graph, and `1` means you think his answer is larger than the actual chromatic number. If you think this problem **cannot be judged accurately with current computing power**, output one line `The problem is unsolvable, please stop cheating me, Mr.Minke.`.

The input contains only one line, with three positive integers $n, k, x$, with meanings as described in the statement. Constraints: $1 \le x, n \le 10^{1,000,000}$, $1 \le k \le 100$. All inputs are positive integers, and for all testdata, $n$ can only satisfy $n \le 10^5$ or $n \ge 10^{100}$.

Output consists of $1$ or $2$ lines. The first line is your judgment result, in the format described in the statement. If you successfully make a judgment and think Minke’s answer is wrong, then you need to output a character `0` or `1` in the second line: `0` means Minke’s answer is too small, and `1` means Minke’s answer is too large.

**[Sample Explanation]** Obviously, coloring vertices $1 \sim 6$ as $1, 2, 3, 1, 2, 3$ is feasible, so when $n = 6$ and $k = 2$, the chromatic number is $3$. **[Hint]** 1. If you have no idea, please read the Constraints in the statement again. It may help you solve the problem. 2. Hint 1 may be useless. **[Source]** From the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021). Solutions and other resources can be found at [https://github.com/yylidiw/thupc_1/tree/master](https://github.com/yylidiw/thupc_1/tree/master). Translated by ChatGPT 5