I - ハウスシャッフル /

Time Limit: 2 sec / Memory Limit: 256 MB

16:38 入力例の三番目のケースに誤りがありましたので,修正しました.

問題文

ヘンゼルはビスケット,キャンディ,マシュマロの絵の書かれたタイルを使って平面上にお菓子の家を作る遊びをしている.

そこでグレーテルが,お菓子の家を使ったゲームを提案した.

ゲームの内容は以下のとおりである.

  • まず,グレーテルがお菓子の家の大きさ N を指定する
  • 次に,ヘンゼルは一辺の長さ N の正三角形状にタイルを並べ, お菓子の家を作り,下の図のように座標をつける.
    このとき,最下段はビスケットのタイルで土台を作り, それ以外の段はキャンディとマシュマロのタイルで構成する.
  • グレーテルは,1 から N までがそれぞれ一度ずつ出現する 順列 σ を用意する.順列 σi 番目を σ_i で表すとする.
    なお,この順列 σ はヘンゼルには知られないようにする.
  • グレーテルは,その順列 σ から,以下の規則にしたがってお菓子の家をシャッフルする.
    ただし,シャッフルする前の座標 (i, j) の位置のタイルを a[i,j] , シャッフルした後の座標 (i, j) の位置のタイルを b[i,j] として表すものとする.
    • σ_i < σ_j のとき,b[i, j] = a[σ_j, σ_i]
    • σ_i ≥ σ_j のとき,b[i, j] = a[σ_i, σ_j]
  • ヘンゼルはシャッフルされたお菓子の絵を見て,順列 σ の内容を推測する.
    推測通りであれば,ヘンゼルの勝ち,間違っていればグレーテルの勝ちである.
以下は,N = 7 のときのお菓子の絵の例とその座標である.

以上のゲームを複数回行う. この問題の目的は,ヘンゼル役のAIプログラムを作成し, ジャッジ側の用意したグレーテル役のAIプログラムと対戦をして, 全てのゲームに勝つことである.


入出力

初めの入力は以下の一行のみで与えられる.

N

N (6 \leq N \leq 200) はお菓子の家の大きさを表す整数である.

この入力の後に,解答プログラムはお菓子の家を表す文字列を, マシュマロを o ,キャンディを @ , ビスケットを # として出力せよ. お菓子の家の上から i 段目を,長さ i の文字列 s_i として以下の形式で出力すること. 各行の先頭には空白を入れず横詰めで出力し,末尾には改行を出力せよ.

s_1
:
s_N

次に,シャッフル後のお菓子の家を表す文字列が同じ形式で与えられる. その後,順列 σ を空白区切りで以下のような形式で出力すること. 出力の後には改行を出力せよ.

σ_1 ... σ_N

この後,すぐに次のゲームがはじまり, 次のゲームのお菓子の家の大きさを表す整数が入力として与えられる. 全てのゲームが終了すると,お菓子の家の大きさを表す整数の代わりに 0 が入力として与えられるので,それを受け取ったら即座にプログラムを終了すること. なお,ひとつの入力で行われるゲームの回数は多くとも 10 回である.

各出力の後には,出力をフラッシュする必要があることに注意せよ.例えば C/C++ では

scanf("%d", &N);

としてお菓子の家のサイズNを受け取り, これに対して文字列s

printf("%s\n", s); fflush(stdout);

と出力すればよい. グレーテル役のAIプログラムから与えられる入力は最後まで受け取ること.受け取らなかった場合,Time Limit Exceeded の結果が得られることがあるため,注意すること.

部分点

以下の制約を満たすデータセットに全て正解した場合は 3 点の部分点が与えられる.

  • N = 6


入出力例

以下の入力例では N = 4 の場合について示しているが,このような入力は与えられないことに注意せよ.

手番 プログラムの出力 プログラムへの入力 説明
グレーテル 4 お菓子の家のサイズの指定
ヘンゼル @
o@
@oo
####
お菓子の家の作成
グレーテル @
o@
@oo
####
σを元にシャッフル
ヘンゼル 2 1 4 3 σの出力
グレーテル 4 お菓子の家のサイズの指定
ヘンゼル @
o@
@oo
####
お菓子の家の作成
グレーテル @
o@
@oo
####
σを元にシャッフル
ヘンゼル 1 2 3 4 σの出力
グレーテル 4 お菓子の家のサイズの指定
ヘンゼル @
o@
oo@
####
お菓子の家の作成
グレーテル @
@o
@oo
####
σを元にシャッフル
ヘンゼル 4 3 2 1 σの出力
グレーテル 0 全てのゲームが終了


Source Name

京都大学プログラミングコンテスト2015