Background

Translated from Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection) D1T3。$\texttt{1s,0.5G}$。

Problem Description

Hint: The problem setter provides a brief summary of the task at the end of the statement.

A teacher is playing a broken telephone game with $N$ children. They all know the same $M$ words, which we label as $1 \sim M$.

The game works like this:

• The children stand in a line.
• The teacher whispers word $1$ to the first child.
• For $1 \le i \lt N$, the $i$-th child whispers the word he heard to the $(i+1)$-th child.
• The $N$-th child says out loud the word he heard.

Because there were OIers nearby typing loudly on keyboards, the game was disturbed, and the children often misheard words. However, magically, for the $i$-th child, no matter who whispers to him and no matter where he is in the line, if he is whispered the same word $A$, he will always hear the same word $B$ (it is possible that $A = B$).

The teacher repeated the game for $N!$ rounds, trying every possible permutation once. She noticed that there is a word that was said out loud exactly $K$ times. She is curious, so she asks you to recreate such a situation.

More specifically, given integers $N, K$, construct positive integers $M, X$, and a way that the children mishear words, such that among the $N!$ rounds, $X$ is said out loud exactly $K$ times.

The smaller the $M$ you find, the higher your score. See 【Scoring】 for details.

Simply put: Given $N, K$. Construct $N$ functions $f_1(x), f_2(x), \ldots, f_{N}(x)$ from $[1,M]$ to $[1,M]$ (where $M$ is a positive integer you choose), such that:

• Let $p_1, p_2, \ldots, p_N$ range over all $N!$ permutations of $1 \sim N$.
  • Put into a multiset $S$ the value of $f_{p_N}(f_{p_{N-1}}\cdots(f_{p_2}(f_{p_1}(1)))\cdots)$ for each of the $N!$ permutations $p$. Then there exists some $X \in S$ such that $X$ appears exactly $K$ times in $S$.

Here, $[1,M]$ means $[1,M]\cap \mathbb{Z}$.

The goal is to make $M$ as small as possible.

Input Format

This problem contains multiple testdata cases within a single test point.

The first line contains a positive integer $\mathrm{id}$, which indicates the subtask number.

The second line contains a positive integer $T$, the number of testdata cases.

The next $T$ lines each contain two integers $N, K$, describing one test case.

Output Format

For each test case, output $(N+1)$ lines:

The first line contains two positive integers $M, X$. You must ensure $1\le X\le M\le 10^4$.

The next $N$ lines each contain $M$ positive integers.

In the $i$-th line, the $j$-th positive integer $f_{i}(j)$ means: if you whisper $j$ to the $i$-th child, he will hear $f_{i}(j)$. You must ensure $f_i(j)\in [1,M]$.

1
2
3 2
2 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

2
2
3 3
4 0

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

Hint

For $100\%$ of the data, it is guaranteed that:

• $\mathrm{id}\in \{1,2\}$.
• $1\le N\le 12$.
• $0\le K\le N!$.
• $1\le T\le 10$.

【Scoring】

This problem is scored with two subtasks.

• Subtask $1$ ($30$ pts): $1\le N\le 7$.

  As long as your construction is valid, you get full points. Otherwise, you get $0$ points.

• Subtask $2$ ($70$ pts): $1\le N\le 12$.

  If your output is invalid, you get $0$ points.

  Otherwise, the score for one test case is $70\cdot k$, where $k$ is computed as follows:

  $$k= \begin{cases} \displaystyle 1, & M\le N+1 \\ \displaystyle 0.7 + \frac{0.15}{M-N-1}\, \in [0.7,0.85], & N+1\lt M\le N+5 \\ \displaystyle 0.5 + 0.05 \left(5-\frac{M}{N}\right) \, \in[0.5,0.7], & N+5\lt M\le 5\cdot N \\ \displaystyle \frac{0.5}{\log_{10}(M/5N)+1}\, \in [0,0.5]& 5\cdot N\lt M\le 10^4 \\ \end{cases}$$

  The score for a single test point is the minimum score among all testdata cases. For example, in Sample $2$, the two test cases have $k$ values $0.77$ and $1$. This output gets $0.7\cdot 70$ points.

Translated by ChatGPT 5