AT_joigsp2025_g.マルチコミュニケーション (Multi Communication)

K 理事长为春季训练的参与者准备了一款游戏。

春季训练共有 $N$ 名参与者，每位参与者都被编上 $1$ 到 $N$ 的编号。每人都有一块写字板。游戏按照以下步骤进行：

1. K 理事长会从 $N$ 名参与者中选出 $1$ 人作为“亲”，其余参与者则为“子”。哪位是“亲”不会告诉任何参与者。
2. K 理事长会在“亲”的写字板上写上字符 T，在所有“子”的写字板上写上字符 F。
3. 每名参与者首先阅读自己写字板上的字符。然后，所有参与者按照事先约定的“策略”，进行 $L$ 轮如下操作：
   1. 每名参与者擦掉自己写字板上的字符，重新写上 T 或 F。随后，将写字板交给K理事长。
   2. 对于每个 $i = 1, 2, \dots, N$，进行如下操作：
      • 参与者 $i$ 指定编号为 $p$ 的某一名参与者（$1 \leq \mathit{p} \leq N$），并把这个编号告诉 K 理事长。K 理事长会将编号为 $p$ 的参与者的写字板给 $i$ 看，$i$ 将读取上面的字符。注意，$i$ 可以选择自己作为被查看者。
4. 最后，每名参与者要回答谁是“亲”。

目标是在事先拟定的完美策略下，无论“亲”是谁，每位参与者最终都能答出“亲”的编号，并希望所需轮数 $L$ 尽可能小。

策略 指定如下内容，包括轮数 $L$ 以及每位参与者的行动方式：

• 对于每一名参与者 $i$（$1 \leq i \leq N$），在第 $t$ 轮（$1 \leq t \leq L$）开始之前所读到的字符顺序为 $a_0,a_1,\ldots,a_{t-1}$ 时，依据这些信息（$i, t, a_0, a_1,..., a_{t-1}$）来决定该轮要在写字板上写什么字符，以及要指定哪位参与者的编号。
• 对于每一名参与者 $i$，在第 $L$ 轮结束后所读到的字符为 $a_0,a_1,\ldots,a_L$ 时，根据这些信息（$i, L, a_0,a_1,...,a_L$）来确定自己的最终回答（即选出一名参与者的编号）。

请设计一个能实现目标的策略，并输出按照该策略、每种“亲”的可能下，每位参与者每轮所写的字符及指定的参与者编号。

---

从标准输入读入数据，格式如下：

$N$

请按以下格式输出：

$L$ $\text{acts}_1$ $\text{acts}_2$ $\vdots$ $\text{acts}_N$

其中 $\text{acts}_s$ 表示编号为 $s$ 的参与者为“亲”时，每个参与者每轮的操作。$\text{acts}_s$ 格式如下：

首先输出一行 $s$。

第 $i+1$ 行输出参与者 $i$ 在每一轮 $t$（$1 \leq t \leq L$）中要写的字符 $c_{i,t}$ 及要查看的参与者编号 $p_{i,t}$，依次输出 $L$ 组（共 $2L$ 项）。

$s$ $c_{1,1}$ $p_{1,1}$ $c_{1,2}$ $p_{1,2}$ $\cdots$ $c_{1,L}$ $p_{1,L}$ $c_{2,1}$ $p_{2,1}$ $c_{2,2}$ $p_{2,2}$ $\cdots$ $c_{2,L}$ $p_{2,L}$ $\vdots$ $c_{N,1}$ $p_{N,1}$ $c_{N,2}$ $p_{N,2}$ $\cdots$ $c_{N,L}$ $p_{N,L}$

输出结果被判定为正确的条件为：存在一种可以达成目标的策略，并且输出结果符合该策略行为，且仅当此时才被判定为正确。

具体来说，仅当以下两条均成立时输出才被判断为正确：

• 对于任意参与者 $i$（$1 \leq i \leq N$）、回合 $t$（$1 \leq t \leq L$）、任意两名不同的参与者 $x,y$（$1 \leq x, y \leq N$，$x \neq y$），如果当“亲”为 $x$ 时参与者 $i$ 在第 $t$ 回合开始前所读字符序列，与“亲”为 $y$ 时读到的完全一致，则 $i$ 在第 $t$ 回合的写入字符和指定对象必须一致。
• 对于任何参与者 $i$ 及任意两名不同的“亲” $x, y$，当“亲”分别为 $x, y$ 且 $i$ 在 $L$ 轮结束后的读字符序列不同。

评分标准

总分为各输入数据得分之和。

对每个输入数据，分数如下：

输出错误（格式不对，或“存在一种可以达成目标的策略并且输出是依照此策略”的条件不成立）记 $0$ 分。

输出正确时，分数见下表：

小测试	输入文件	$N$	得分分段	满分
1	input_01.txt	4	$L > 4$，0分；$2 < L \leq 4$，$16 - 7 \times (L - 2)$分；$L \leq 2$，16分	16
2	input_02.txt	32	$L > 27$，0分；$8 < L \leq 27$，$60 - 3 \times (L - 8)$分；$L \leq 8$，60分	60
3	input_03.txt	48	$L > 9$，0分；$L \leq 9$，24分	24

注意，$0$ 分时，评测系统显示“输出不正确”。

---

样例说明 1

下面的输出样例符合如下策略：

• 取 $L=3$。
• 对于每位参与者 $i$，每轮 $t$，如果自己是“亲”就写 T，否则写 F。根据开局 K 理事长所写字符，可以立即知道自己是否为“亲”。
• 每轮每位参与者都无论以往读到什么内容，始终指定第 $t$ 位。
• 经过第 $3$ 轮后，每名参与者至少看过一次所有人的写字板。可根据哪个人板子上写 T 来最终判断“亲”是谁。

所以无论谁为亲，所有人最终都能正确回答，达成了目标。因此样例输出被判定为正确。

注：本输入样例不满足约束，实际不会出现在测试数据中。

限制

• $N$ 只会取 $4, 32, 48$ 中的一个。

由 ChatGPT 5 翻译