P11991 [JOIST 2025] 多方通信 / Multi Communication

你可以提交数据生成器，也可以提交三个 $\texttt{.txt}$ 文件（$\texttt{1.txt}\sim \texttt{3.txt}$）。

**这是一道提交答案题。** K 主席为春季训练营的参与者准备了一个游戏。 训练营中共有 $N$ 名参与者，每人被分配一个从 $1$ 到 $N$ 的唯一编号。每位参与者拥有一块白板。游戏按以下步骤进行： 1. K 主席选择一名参与者作为父节点（parent），其余参与者成为子节点（children）。但**父节点的身份不会向参与者公开**。 2. K 主席在父节点的白板上写下字母 $\texttt{T}$，在所有子节点的白板上写下字母 $\texttt{F}$。 3. 每位参与者阅读自己白板上的字母。然后，按照预先定义好的策略，执行以下回合制流程（共 $L$ 个回合）： - 每位参与者擦除白板上的字母，并写下 $\texttt{T}$ 或 $\texttt{F}$，然后将白板提交给 K 主席。 - 对于每个参与者 $i$（$i = 1, 2, \ldots, N$）： - 参与者 $i$ 选择一个参与者 $p$（$1 \leq p \leq N$）并将编号 $p$ 告知 K 主席。 - K 主席将参与者 $p$ 的白板展示给参与者 $i$，参与者 $i$ 读取上面的字母。参与者可以选择自己作为 $p$。 4. 经过 $L$ 个回合后，每位参与者必须猜测谁是父节点。 游戏的目标是预先制定一个策略，使得无论谁被选为父节点，所有参与者都能在此流程结束时正确识别父节点。 **更小的 $L$ 值意味着更高的得分**。你的目标是设计一个策略，在保证所有参与者能正确识别父节点的前提下，最小化 $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, \ldots, a_{t-1}$），必须确定： - 在该回合要写入白板的字母； - 在该回合选择观察的参与者编号。 - 对于参与者 $i$（$1 \leq i \leq N$），在第 $L$ 个回合结束后，若其已读取的字母序列为 $a_0, a_1, \ldots, a_L$，则仅基于这些信息（$i$, $L$, $a_0, a_1, \ldots, a_L$），必须推断出父节点的编号。 请设计一个允许所有参与者正确识别父节点的策略（无论父节点是谁）。然后，针对每个可能的父节点选择（$1, 2, \ldots, N$），输出每位参与者按此策略在各回合写入白板的值和选择观察的参与者编号。

一行一个正整数 $N$。

输出格式如下： > $L$\ > $\mathrm{acts}_1$\ > $\mathrm{acts}_2$\ > $\vdots$\ > $\mathrm{acts}_N$ 其中，$\mathrm{acts}_s$ 表示当参与者 $s$ 是父节点时，每位参与者的行动序列。其格式如下： 1. 首先输出整数 $s$。 2. 对于每个参与者 $i$（$1 \leq i \leq N$），输出一行表示其在 $L$ 个回合中的行动序列。每行应包含以下值： - 字符 $c_{i,t}$（$\texttt{T}$ 或 $\texttt{F}$），表示该参与者在第 $t$ 个回合写入白板的字母。 - 参与者编号 $p_{i,t}$，表示该参与者在第 $t$ 个回合选择观察的对象。 这些值需按回合顺序（$t=1,2,\ldots,L$）依次输出。因此，$\mathrm{acts}_s$ 的输出格式为： > $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}$

### 样例解释 样例中，参与者的策略如下： - 令 $L = 3$。 - 在每回合 $t$（$1 \leq t \leq L$）中： - 参与者 $i$ 若其为父节点则写入 $\texttt{T}$，若为子节点则写入 $\texttt{F}$（根据初始步骤看到的字符，他们知道自己是否为父节点）。 - 在每回合 $t$（$1 \leq t \leq L$）中： - 参与者 $i$ 观察参与者 $t$，无论其当前已读取的字母序列如何。 - 经过 $3$ 个回合后，每位参与者将恰好读取过包括自己在内的所有参与者的白板各一次。每位参与者将选择白板上出现过 $\texttt{T}$ 的参与者编号作为父节点。 该策略确保所有人正确识别父节点，达成游戏目标。由于此策略在任何父节点选择下均满足游戏要求，因此输出被视为正确。 注意：样例不在实际测试数据中，因其不满足题目给定的约束条件。 ### 数据范围 $N\in \{4,32,48\}$。 更为具体地说： - 测试点 $1$ 中，$n=4$。 - 测试点 $2$ 中，$n=32$。 - 测试点 $3$ 中，$n=48$。 ### 计分方式 当且仅当输出符合以下条件时，才被视为正确：该输出是通过参与者遵循一个**有效策略**（确保所有参与者都能正确识别父节点）所产生的结果。具体而言，必须满足以下两个条件： 1. 对于任意参与者 $i$（$1 \leq i \leq N$）、任意回合 $t$（$1 \leq t \leq L$）以及任意两个不同的父节点候选 $x$ 和 $y$（$1 \leq x, y \leq N$ 且 $x \neq y$）：若参与者 $i$ 在回合 $t$ 之前读取的字母序列在 $x$ 为父节点和 $y$ 为父节点时完全相同，则参与者 $i$ 必须在回合 $t$ 采取相同的行动（即写入相同的字母并选择相同的观察对象）。 2. 对于任意参与者 $i$（$1 \leq i \leq N$）以及任意两个不同的父节点候选 $x$ 和 $y$（$1 \leq x, y \leq N$ 且 $x \neq y$）：当 $x$ 为父节点时，参与者 $i$ 在第 $L$ 个回合结束时读取的字母序列必须与 $y$ 为父节点时的序列不同。 --- 该题的得分为三个测试点的得分之和。 若输出不正确（例如格式错误或未遵循有效策略），则该测试点得 $0$ 分。 否则，若输出正确，则按以下标准计算得分： | 测试点编号 | $N=$ | 计分方式 | 满分 | |:-:|:-:|-|:-:| | $1$ | $4$ | $\displaystyle \textsf{得分}=\begin{cases} 0 & 4\lt L \\ 16-7\cdot (L-2) & 2\lt L\le 4 \\ 16 & L\le 2\end{cases}$| $16$ | | $2$ | $32$ | $\displaystyle \textsf{得分}=\begin{cases} 0 & 27\lt L \\ 60-3(L-8) & 8 < L \leq 27 \\ 60 & L\le 8\end{cases}$ | $60$ | | $3$ | $48$ | $\displaystyle \textsf{得分}=\begin{cases} 0 & 9\lt L \\ 24 & L\le 9 \end{cases}$ | $24$ |