AtCoder Regular Contest 019

D - ほんとうのたたかい


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

ついに魔王を倒し、世界に平和が訪れた!

しかしながら、私のたたかいはまだ終わっていない!月 1 回の高級おやつを巡って、妹との勝負が残っているのだ!

何を隠そう私の妹は競技プログラミングに長けていて、毎回私と競技プログラミングで戦っては勝利し、高級おやつは妹のものになってしまうのだ!

(まあ、私の家が競技プログラミングの家系で、高級おやつは競技プログラミングの出来具合で決まるというきまりになっているから、しょうがないね。)

毎回妹に負けてしまい、延々高級おやつにありつけず、年上としての威厳もズタズタである私は、密かに競技プログラミングのスキル上昇に精進していたのだ!その一環として先程のゲーム Ancient Royal Coders をプレイしていたのである!

そして今回も高級おやつを巡って妹と勝負をすることになっている。

今回の競技は以下の条件を満たす縦 N 行、横 N 列のマス目を作成し、提出することで勝負するらしい。

  • N2 ≦ N ≦ 150 を満たす整数でなければならない。
  • 各マスには 1 つの O が描かれているか、描かれていないかのいずれかである。
  • 縦横の辺がいずれも行または列に平行な、どの長方形を取り出しても、その長方形の 4 隅のいずれか 1 つは O が描かれていないマスである。言い換えると、1 ≦ i < k ≦ N および 1 ≦ j < l ≦ N をみたす任意の 4 つの整数 i,j,k,l において、以下の条件が成立することである。
    • pq 列にあるマスのことを (p,q) と呼ぶことにしたとき、(i,j),(i,l),(k,j),(k,l) のうち少なくとも 1 つは O が描かれていないマスである。

このような条件を満たす縦 N 行、横 N 列のマス目のうち、より多く O が含まれるものを提出したほうが勝利である。

今月のおやつはあの伝説のプリンらしい。ここ数年、このプリンを口にしていない。因みにこの数年の起点が、妹が競技プログラミングを始めた日と合致していることは内緒である。

幸い、今回はプリンという分配可能なおやつなので、今回は双方の出来具合でプリンを分配するよう提案し、可決された。これは私が妹の分のおやつを取ったことで妹が悲しまないようにするためで、別にちょっとだけでも貰おうとかいう考えじゃないぞ!

何よりも今回は負けない自信がある。さあ、今こそ Ancient Royal Coders で鍛えたプログラミングスキルを披露しようじゃないか!


入力

今回、入力は与えられない。

部分点

この問題には部分点が設定されている。

  • あなたが提出した出力に関して、出力が示すマス目に描かれている O の個数を S としたとき、以下の基準で得点が与えられる。
    • 出力が条件を満たさないか、S ≦ 294 となる場合、残念ながらプリンは分けてもらえず、0 点である。
    • 出力が条件を満たし、295 ≦ S ≦ 399 となる場合、プリンを微量分けてもらえる。このとき、5 点が得られる。
    • 出力が条件を満たし、400 ≦ S ≦ 899 となる場合、プリンを 1 口分けてもらえる。このとき、10 点が得られる。
    • 出力が条件を満たし、900 ≦ S ≦ 1299 となる場合、プリンを 1 口半分けてもらえる。このとき、20 点が得られる。
    • 出力が条件を満たし、1300 ≦ S ≦ 1499 となる場合、プリンを 2 口分けてもらえる。このとき、30 点が得られる。
    • 出力が条件を満たし、1500 ≦ S ≦ 1699 となる場合、プリンを 1/4 分けてもらえる。このとき、50 点が得られる。
    • 出力が条件を満たし、1700 ≦ S となる場合、プリンを半分こできる。このとき、100 点が得られる。

出力

出力は以下ように記述すること。

  • 1 行目には整数 N を出力する。N2 以上 150 以下なら任意に設定できる。
  • 2 行目から N 回だけ、長さ N の文字列を出力する。各文字は O. のいずれかであり、i 回目 (1 ≦ i ≦ N) の出力に置ける文字列の左から j 文字目 (1 ≦ j ≦ N) に関して、
    • その文字が O なら、ij 列のマスには O が描かれていること
    • その文字が . なら、ij 列のマスには O が描かれていないこと
    を表す。

なお、出力の最後には改行を入れること。改行がない場合、他の部分が正しくてもWAとなってしまう点に注意。特に、出力後の結果画面に表示されるソースコード欄では最終行の改行の有無が判別しづらい場合があります。


出力について

この問題では、ソースコードのところに出力したい内容を書き、言語のところを Text (cat) を選択して提出することで、出力したい内容をそのまま出力として提出することができる。もちろん、この機能を使わずに他の言語のソースコードを提出しても構わないが、その場合はこの問題が指定する時間制限やメモリ制限等を満たさなければならない。


ジャッジの応答について

ジャッジの応答として、ACWA の記述が表す意味がやや特殊である。

  • AC は、出力が条件を満たした場合に、最終的に得られる得点によらず出力される。
  • WA は、出力が条件を満たさない場合に出力される。
そのため、AC と出力されていても実際は 0 点であることがある。


出力例 1

5
.....
.....
..OOO
...O.
..O..
  • この出力の場合、出力は条件を満たす。しかしながら S = 5 となるため、この出力を提出しても 0 点である。

出力例 2

4
....
.OOO
..O.
.OO.
  • この出力の場合、22 列、23 列、42 列、43 列のいずれにも O が描かれているため、出力は条件を満たさない。よって、この出力を提出しても WA となり,0 点である。

Submit提出する