This problem is a twist on a well-known puzzle style.
We have \(n\) people standing in a line, one behind another. Each of them is given a hat with a number on it. The \(n\) numbers are pairwise different and each of them is between \(1\) and \(m\), inclusive. Everybody sees the numbers of all the people standing in front of them, and nobody sees their own number.
The people then speak in turn, from the back of the line to the front. Each of them wants to guess their own number. After the whole process is over, everyone who didn’t guess correctly gets a punishment (kitchen duty).
Each of the people, when it’s their turn, can only say one single integer, and that number must be a valid hat number (i.e., between \(1\) and \(m\), inclusive). Most importantly, all guesses must also be pairwise different – nobody may say a number that has already been said. Everybody hears everything. There is no confirmation whether the guesses were correct or not.
The people know \(n\) and \(m\) and they can agree on a strategy in advance.
The person at the back of the line speaks first. In general, no strategy can guarantee that this person will correctly guess their own number. We will call a strategy successful if it is guaranteed that everyone else always escapes punishment. In other words, a strategy is successful if for every assignment of the hat numbers each of the \(n-1\) people who do not stand at the back of the line correctly guesses their own number.
You will be given some pairs \((n, m)\).
For each of them, decide whether a successful strategy exists.
If yes, find one and provide instructions for the person at the end of the line: a function \(f\) which for every \((n-1)\)-tuple \((h_1,\dots,h_{n-1})\) of pairwise different hat numbers from \(\{1,\dots,m\}\), where \(h_i\) is the number of the \(i\)-th person from the front, gives the number \(f(h_1,\dots,h_{n-1})\) which should be said by the person at the back.
Such a function determines a successful strategy if and only if for every assignment of the numbers each of the other \(n-1\) people can determine and announce their own number from what they see and from what they hear before they speak.
Note that for a successful strategy \(f(h_1,\dots,h_{n-1})\) can never be equal to one of the \(h_i\), as this would mean that later person \(i\) won’t be able to announce their number \(h_i\), even if they can determine it.
The first line of an input file contains the number \(t\) of test cases. Note that in this task each \(t\) is very small.
Each of the following \(t\) lines contains two integers \(n\) and \(m\), with \(3 \le n \le m\).
For each test case, in the order in which they are given, output a single line with either
IMPOSSIBLE, if no successful strategy
exists, orWhitespace between the numbers on a line is arbitrary. Any valid successful strategy is accepted.
There are eight input files. For each of them we list the exact test cases it contains. The first seven inputs are worth 12 points each, the last one is worth 16 points.
D1.in = [ (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9) ]
D2.in = [ (4, 6), (4, 7) ]
D3.in = [ (4, 8), (4, 16), (4, 32), (4, 64) ]
D4.in = [ (3, 3), (3, 7), (3, 179), (3, 231), (3, 353), (3, 497), (3, 499) ]
D5.in = [ (3, 6), (3, 8), (3, 178), (3, 292), (3, 350), (3, 498), (3, 500) ]
D6.in = [ (3, 5), (4, 6), (5, 7), (6, 8), (7, 9), (8, 10), (9, 11) ]
D7.in = [ (3, 6), (4, 7), (5, 8), (6, 9), (7, 10), (8, 11), (9, 12) ]
D8.in = [ (4, 10), (5, 11), (6, 12), (4, 14), (4, 20), (4, 40), (4, 62) ]
Subproblems D1 and D2 are evaluated as public. All other subproblems are secret.
input2 3 3 4 4 | output3 2 3 1 2 1 4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1 |
Both test cases have \(m=n\), so the person at the back sees all the numbers except one and their strategy is forced: they say the only number they do not see.
The strategy for the first test case is printed as \(3\cdot 2=6\) integers, in the order \(f(1,2)\), \(f(1,3)\), \(f(2,1)\), \(f(2,3)\), \(f(3,1)\), \(f(3,2)\).
Similarly, the strategy for the second test case is printed as \(4\cdot 3\cdot 2=24\) integers, starting with \(f(1,2,3)\), \(f(1,2,4)\), \(f(1,3,2)\), \(f(1,3,4)\), …, and finishing with \(f(4,2,3)\), \(f(4,3,1)\), and \(f(4,3,2)\).