34111번 - Multi Communication 서브태스크점수다국어

문제

Chairman K has prepared a game for the participants of the spring training camp.

There are $N$ participants in the training camp, each assigned a unique number from 1ドル$ to $N$. Each participant has a board. The game follows these steps:

1. Chairman K selects one participant to be the parent, while all other participants become children. However, the identity of the parent is not revealed to the participants.
2. Chairman K writes the letter ‘T’ on the parent’s board and the letter ‘F’ on all the children’s boards.
3. Each participant reads the letter on their own board. Then, following a predefined strategy, they perform the following turn-based process for $L$ turns:
   1. Each participant erases the letter on their board and writes either ‘T’ or ‘F’. Then, they submit their board to Chairman K.
   2. For each participant $i$ ($i = 1, 2, \dots , N$):
      • Participant $i$ selects a participant $p$ (1ドル ≤ p ≤ N$) and informs Chairman K of the number $p$. Chairman K shows the board of participant $p$ to participant $i,ドル who then reads the letter on it. A participant is allowed to choose themselves as $p$.
4. After $L$ turns, each participant must guess who the parent is.

The goal of the game is to establish a strategy beforehand so that, regardless of who is chosen as the parent, all participants can correctly identify the parent by the end of the process.

A smaller value of $L$ results in a higher score. Your goal is to devise a strategy that minimizes $L$ while ensuring that all participants correctly identify the parent by the end of the process.

A strategy consists of a non-negative integer $L,ドル representing the number of turns, and a set of rules that determine the actions of each participant. The rules are as follows:

• For participant $i$ (1ドル ≤ i ≤ N$), at the beginning of turn $t$ (1ドル ≤ t ≤ L$), if the sequence of letters they have read up to that point is $a_0, a_1, \dots , a_{t-1},ドル then based only on this information $(i, t, a_0, a_1, \dots , a_{t-1}),ドル they must determine:
  • The letter they will write on their board for turn $t$.
  • The participant number they will choose to observe for turn $t$.
• For participant $i$ (1ドル ≤ i ≤ N$), after the $L$-th turn, if the sequence of letters they have read up to that point is $a_0, a_1, \dots , a_L,ドル then based only on this information $(i, L, a_0, a_1, \dots , a_L),ドル they must determine the participant number of the parent.

Devise a strategy that allows all participants to correctly identify the parent, regardless of who is chosen as the parent. Then, for each possible parent selection $(1, 2, \dots , N),ドル output the values that each participant writes on their board and the participant they choose to observe in each turn, following the established strategy.

입력

Read the following data from the standard input.

$N$

출력

Print the output in the following format:

$L$

$acts_1$

$acts_2$

$\vdots$

$acts_N$

Here, $acts_s$ represents the sequence of actions taken by each participant when participant $s$ is the parent. The format of $acts_s$ is as follows:

First, print the integer $s$. For each participant $i$ (1ドル ≤ i ≤ N$), print a single line containing the sequence of actions they take during the $L$ turns. Each line should have the following values:

• The character $c_{i,t}$ (‘T’ or ‘F’), which the participant writes on their board in turn $t$.
• The participant number $p_{i,t},ドル which they choose to observe in turn $t$.

These values should be printed for each turn $t$ (1ドル ≤ t ≤ L$) in sequence. Thus, the output format for $acts_s$ is:

$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}$

제한

• $N$ is one of 4ドル,ドル 32ドル,ドル or 48ドル$.

채점

The output is considered correct if and only if it can be obtained as the result of participants following a valid strategy that ensures all of them can correctly identify the parent. Specifically, the following two conditions must be met:

• For any participant $i$ (1ドル ≤ i ≤ N$), turn $t$ (1ドル ≤ t ≤ L$), and any two distinct parent candidates $x,ドル $y$ (1ドル ≤ x, y ≤ N,ドル $x \ne y$): If the sequence of letters read by participant $i$ before turn $t$ is identical when $x$ is the parent and when $y$ is the parent, then participant $i$ must take the same action in turn $t$ (i.e., write the same letter and choose the same participant).
• For any participant $i$ (1ドル ≤ i ≤ N$) and any two distinct parent candidates $x,ドル $y$ (1ドル ≤ x, y ≤ N,ドル $x \ne y$): The sequence of letters read by participant $i$ by the end of turn $L$ must be different when $x$ is the parent compared to when $y$ is the parent.

서브태스크

Note that if your score is 0, the grading system displays “Output isn’t correct”.

힌트