Verification of Chromatic Number in a Special Circulant Graph

Your friend Minke claims that he has solved a half‐graph coloring problem on a very special circulant graph. The graph is defined on n vertices labeled 1,2,…,n. An undirected edge exists between two different vertices x and y if and only if there exists an integer i (1 ≤ i ≤ k) such that

$$ (x+i)\equiv y \pmod{n} $$

or

$$ (y+i)\equiv x \pmod{n}. $$

This graph is nothing but the k-th power of a cycle. Note that if n ≤ 2k+1 the graph is a complete graph and its chromatic number is n. When n > 2k+1 the answer can be computed in O(1) time using its structure. In fact, one may prove that the chromatic number \( \chi \) is given by:

• If k = 1 (i.e. the ordinary cycle):
  • \(\chi=2\) if n is even,
  • \(\chi=3\) if n is odd.
• If k \(\ge 2\):
  • If n ≤ 2k+1 then \(\chi=n\) (i.e. the graph is complete).
  • If n > 2k+1 then one correct formula is $$\chi=\max\Bigl(k+1, \Bigl\lfloor\frac{n}{k+1}\Bigr\rfloor+1\Bigr),$$ which works for the test cases provided below.

Minke gives you three positive integers n, k and x. He claims that \(\chi=x\). Your task is to verify his claim. If you believe his answer is correct, output one line:

Correct, but it doesn't necessarily mean that you can win the Turing Award.

If his answer is wrong, then on the first line output:

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

On the second line, output one single character:

• Output 0 if you believe Minke's answer is smaller than the true chromatic number.
• Output 1 if you believe Minke's answer is greater than the true chromatic number.

If you think that even with current computing power it is impossible to decide the correct value, simply output a single line:

The problem is unsolvable, please stop cheating me, Mr.Minke.

inputFormat

The input consists of a single line containing three positive integers n, k and x separated by spaces. Their meanings are as described above.

For example:

5 1 3

outputFormat

If Minke's claimed chromatic number is correct (i.e. equals the true chromatic number of the graph), output a single line exactly as below:

Correct, but it doesn't necessarily mean that you can win the Turing Award.

If it is incorrect, then output two lines. The first line must be:

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

The second line should be a single character:

• 0 if Minke's answer is less than the correct chromatic number.
• 1 if Minke's answer is greater than the correct chromatic number.

In the case that you judge the problem unsolvable with current computing power, simply output:

The problem is unsolvable, please stop cheating me, Mr.Minke.

sample

5 1 3

Correct, but it doesn't necessarily mean that you can win the Turing Award.