/
Time Limit: 2 sec / Memory Limit: 1024 MiB
Submission on AtCoder
There are three inputs, with N=4,32,48. Submit a program that reads the input from standard input and prints your result for the corresponding input to standard output.
Score: 100 points
Problem Statement
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:
- 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.
- Chairman K writes the letter ‘
T’ on the parent’s board and the letter ‘F’ on all the children’s boards. - 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, \ldots, N):
- Participant i selects a participant p (1 \le p \le 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.
- (1) Each participant erases the letter on their board and writes either ‘
- 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 \le i \le N), at the beginning of turn t (1 \le t \le L), if the sequence of letters they have read up to that point is a_{0}, a_{1}, \ldots, a_{t - 1}, then based only on this information (i, t, a_{0}, a_{1}, \ldots, 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 \le i \le N), after the L-th turn, if the sequence of letters they have read up to that point is a_{0}, a_{1}, \ldots, a_{L}, then based only on this information (i, L, a_{0}, a_{1}, \ldots, 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, \ldots, 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.
Input
Read the following data from the standard input.
N
Output
Print the output in the following format:
L
\mathrm{acts}_1
\mathrm{acts}_2
\vdots
\mathrm{acts}_N
Here, \mathrm{acts}_s represents the sequence of actions taken by each participant when participant s is the parent. The format of \mathrm{acts}_s is as follows:
First, print the integer s. For each participant i (1 \le i \le 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 \le t \le L) in sequence. Thus, the output format for \mathrm{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}
Grading
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 \le i \le N), turn t (1 \le t \le L), and any two distinct parent candidates x, y (1 \le x, y \le 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 \le i \le N) and any two distinct parent candidates x, y (1 \le x, y \le 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.
Submission
Submit only the output files output_01.txt, output_02.txt, output_03.txt, corresponding to the given input files input_01.txt, input_02.txt, input_03.txt.
Constraints
- N is one of 4, 32, or 48.
Scoring
The total score is the sum of the scores for the three input cases.
If the output is incorrect (e.g., incorrect format or failing to follow a valid strategy), the score for that test case is 0.
If the output is correct, the score is calculated as following criteria:
| Subtask | Input File | N | Score | Maximum Score |
|---|---|---|---|---|
| 1 | input_01.txt |
4 | 0 if 4 < L 16 - 7(L - 2) if 2 < L \le 4 16 if L \le 2 |
16 |
| 2 | input_02.txt |
32 | 0 if 27 < L 60 - 3(L - 8) if 8 < L \le 27 60 if L \le 8 |
60 |
| 3 | input_03.txt |
48 | 0 if 9 < L 24 if L \le 9 |
24 |
Note that if your score is 0, the grading system displays “Output isn’t correct”.
Sample Input 1
3
Sample Output 1
3 1 T 1 T 2 T 3 F 1 F 2 F 3 F 1 F 2 F 3 2 F 1 F 2 F 3 T 1 T 2 T 3 F 1 F 2 F 3 3 F 1 F 2 F 3 F 1 F 2 F 3 T 1 T 2 T 3
This output example can be obtained as the result of participants following the strategy below:
- Set L = 3.
- In each turn t (1 \le t \le L), participant i writes ‘
T’ if they are the parent, ‘F’ if they are a child. Note that they know whether they are a parent or a child according to the character they see in the initial step. - In each turn t (1 \le t \le L), participant i observes participant t, regardless of the letters they have read so far.
- By the end of turn 3, each participant will have read the board of every participant including themselves at least once. Each participant then identifies the participant whose board contained ‘
T’ and submits their number as the parent.
This ensures that everyone correctly identifies the parent, achieving the game’s objective. Since the strategy successfully meets the game’s objective for any chosen parent, the output is considered correct.
Note that the given example does not correspond to an actual test case, as it does not satisfy the given constraints.
AtCoder での提出方法
N=4,32,48 の 3 つの入力があるので,入力で場合分けしてあなたの結果を出力してください.
配点 : 100 点
問題文
K 理事長は春季トレーニングの参加者にゲームを用意した.
春季トレーニングには N 人の参加者がおり,それぞれ 1 から N までの番号が付けられている. それぞれの参加者は 1 つボードを持っている. ゲームは以下の手順で行われる.
- K 理事長は,N 人の参加者の中から 親 となる参加者を 1 人選ぶ.親でない参加者は 子 となる.どの参加者が親であるかは,参加者には伝えられない.
- K 理事長は,親のボードに文字
Tを,すべての子のボードに文字Fを書く. - 各参加者は自分のボードに書かれた文字を読む.
その後,参加者の間で事前に定めた 戦略 に従って,以下のターンを L 回行う.
- 各参加者は自分のボードに書かれた文字を消し,新たに
TかFを書き込む.その後,各参加者はボードを K 理事長に渡す. - i = 1, 2, \dots, N について,以下を行う.
- 参加者 i は,ある参加者 p (1 \leqq \mathit{p} \leqq N) を指定し,その番号 \mathit{p} を K 理事長に伝える.K 理事長は,参加者 \mathit{p} のボードを参加者 i に見せ,そのボードに書かれた文字を参加者 i は読む.このとき,参加者 i は自分自身を指定してもよい.
- 各参加者は自分のボードに書かれた文字を消し,新たに
- 各参加者は,誰が親であるかを答える.
戦略を事前にうまく定めておくことによって,親としてどの参加者が選ばれたとしても,最終的に全員が親である参加者の番号を答えられるようにすることがこのゲームの目標である. また,できるだけ小さいターン数 L で目標を達成したい.
戦略 とは,ターン数を表す非負整数 L および参加者の行動を決定する以下のような方法の組である.
- 参加者 i (1 \leqq i \leqq N) が,t ターン目 (1 \leqq t \leqq L) が始まるまでに読んだ文字が順に a_0,a_1,\ldots,a_{t - 1} であったとき,それらの情報 (i,t,a_0,a_1,\ldots,a_{t - 1}) のみから,参加者 i が t ターン目でボードに書く文字および指定する参加者の番号を定める方法.
- 参加者 i (1 \leqq i \leqq N) が,L ターン目の終了までに読んだ文字が順に a_0,a_1,\ldots,a_{L} であったとき,それらの情報 (i,L,a_0,a_1,\ldots,a_{L}) のみから,参加者 i が最終的に答える参加者の番号を定める方法.
目標を達成できるようなある戦略を定め,その戦略に従ったときに,親が 1,2,\ldots,N だった場合のそれぞれについて,各参加者が各ターンにおいてボードに書く値および次に指定する参加者を出力せよ.
入力
入力は以下の形式で標準入力から与えられる.
N
出力
標準出力に,以下の形式で出力せよ.
L
\text{acts}_1
\text{acts}_2
\vdots
\text{acts}_N
\text{acts}_s は,参加者 s が親であった場合の各参加者の各ターンにおける行動を表す. \text{acts}_s は以下の形式で出力せよ.
まず 1 行目に s を出力せよ.
i + 1 行目には,参加者 i が t ターン目でボードに書く文字 c_{i,t} と指定する参加者の番号 p_{i,t} を,各ターン t (1 \leqq t \leqq L) について順に出力せよ.
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}
出力が正しいと判定されるのは,目標を達成できるようなある戦略が存在して,出力がその戦略に従った結果であるとき,かつそのときのみである.
具体的には,出力が正しいと判定されるのは以下の 2 つの条件を共に満たした場合である.
- 任意の参加者 i (1 \leqq i \leqq N),ターン t (1 \leqq t \leqq L),参加者 x,y (1 \leqq x,y \leqq N,x \neq y) に対して,参加者 x が親であるときに参加者 i が t ターン目が始まるまでに読んだ文字の情報と,参加者 y が親であるときに参加者 i が t ターン目が始まるまでに読んだ文字の情報が等しいならば,参加者 i がターン t にボードに書き込む文字および指定する参加者が等しい.
- 任意の参加者 i (1 \leqq i \leqq N),参加者 x, y (1 \leqq x,y \leqq N,x \neq y) に対して,参加者 x が親であるときに参加者 i が L ターン目の終了までに読んだ文字の情報と,参加者 y が親であるときに参加者 i が L ターン目の終了までに読んだ文字の情報が異なる.
提出方法
入力データ input_01.txt, input_02.txt, input_03.txt に対する出力データ output_01.txt, output_02.txt, output_03.txt のみを提出せよ.
制約
- N は 4,32,48 のいずれかである.
採点基準
3 個の入力データの得点の合計が課題の得点である.
各入力データに対し,得点は以下のように計算される.
あなたの出力が誤っている場合,すなわちフォーマットが間違っている場合や,「目標を達成できるようなある戦略が存在して,出力がその戦略に従った結果である」という条件が満たされないとき,あなたの得点は 0 点となる.
あなたの出力が正しい場合,以下で定める点数となる.
各入力データにおける,N の値と配点は,以下の通りである.
| 小課題 | 入力データ | N | 得点 | 配点 |
|---|---|---|---|---|
| 1 | input_01.txt |
4 | 4 < L の場合 0 点 2 < L \leqq 4 の場合 16 - 7 \times (L - 2) 点 L \leqq 2 の場合 16 点 |
16 |
| 2 | input_02.txt |
32 | 27 < L の場合 0 点 8 < L \leqq 27 の場合 60 - 3 \times (L - 8) 点 L \leqq 8 の場合 60 点 |
60 |
| 3 | input_03.txt |
48 | 9 < L の場合 0 点 L \leqq 9 の場合 24 点 |
24 |
ただし,0 点の場合,採点システム上では 出力は正しくない と表示されることに注意せよ.
入力例 1
3
出力例 1
3 1 T 1 T 2 T 3 F 1 F 2 F 3 F 1 F 2 F 3 2 F 1 F 2 F 3 T 1 T 2 T 3 F 1 F 2 F 3 3 F 1 F 2 F 3 F 1 F 2 F 3 T 1 T 2 T 3
この出力例は,以下のような戦略に従った結果である.
- L = 3 とする.
- 参加者 i (1 \leqq i \leqq N) は,t (1 \leqq t \leqq L) ターン目では,自分が親であるならば
Tを,子であるならばFをボードに書く.自分が親であるかどうかは,初めに K 理事長によって自分のボードに書かれた文字を読むことで分かることに注意せよ. - 参加者 i (1 \leqq i \leqq N) は,t (1 \leqq t \leqq L) ターン目では,これまでに読んだ文字の情報に関わらず参加者 t を指定する.
- それぞれの参加者は,3 ターン目の終了時点で,自分を含むすべての参加者がボードに書いた文字を 1 回以上ずつ読んでいる.それぞれの参加者は,ボードに
Tと書いていた参加者の番号を最終的に答える.
この戦略に従った結果,親としてどの参加者が選ばれたとしても,最終的に全員が親である参加者の番号を正しく答えることができており,目標が達成されている. そのため,この出力例は正しいと判定される.
この入力例は制約を満たさず,また実際の入力データに含まれないことに注意せよ.