I - マルチコミュニケーション (Multi Communication) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点： 100 点

AtCoder での提出方法について

N=4,32,48 の 3 つの入力があるので，入力で場合分けしてあなたの結果を出力してください．

K 理事長は春季トレーニングの参加者にゲームを用意した．

春季トレーニングには N 人の参加者がおり，それぞれ 1 から N までの番号が付けられている． それぞれの参加者は 1 つボードを持っている． ゲームは以下の手順で行われる．

  1. K 理事長は，N 人の参加者の中から 親 となる参加者を 1 人選ぶ．親でない参加者は 子 となる．どの参加者が親であるかは，参加者には伝えられない．
  2. K 理事長は，親のボードに文字 T を，すべての子のボードに文字 F を書く．
  3. 各参加者は自分のボードに書かれた文字を読む． その後，参加者の間で事前に定めた 戦略 に従って，以下のターンを L 回行う．
    1. 各参加者は自分のボードに書かれた文字を消し，新たに T か F を書き込む．その後，各参加者はボードを K 理事長に渡す．
    2. i = 1, 2, \dots, N について，以下を行う．
      • 参加者 i は，ある参加者 p (1 \leqq \mathit{p} \leqq N) を指定し，その番号 \mathit{p} を K 理事長に伝える．K 理事長は，参加者 \mathit{p} のボードを参加者 i に見せ，そのボードに書かれた文字を参加者 i は読む．このとき，参加者 i は自分自身を指定してもよい．
  4. 各参加者は，誰が親であるかを答える．

戦略を事前にうまく定めておくことによって，親としてどの参加者が選ばれたとしても，最終的に全員が親である参加者の番号を答えられるようにすることがこのゲームの目標である． また，できるだけ小さいターン数 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 ターン目の終了までに読んだ文字の情報が異なる．

制約

  • 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 と書いていた参加者の番号を最終的に答える．

この戦略に従った結果，親としてどの参加者が選ばれたとしても，最終的に全員が親である参加者の番号を正しく答えることができており，目標が達成されている． そのため，この出力例は正しいと判定される．

この入力例は制約を満たさず，また実際の入力データに含まれないことに注意せよ．