UFO(UFOの飛行場) - joi2011-day3
出力のみの課題 (Output-only task)
IOI 星の宇宙人は日本にある JOI 公園 (ただし，一般の人には存在は秘密にされている) に UFO の飛行場を作る計画を立てている．IOI 星の宇宙人は JOI 公園を調査し，UFO が着陸可能な場所を示した地図を作成した．
JOI 公園は東西 W メートル，南北 H メートルの長方形であり，1 メートル四方の正方形の区画に分けられている．区画は全部で W \times H 個あり，西から x 列目，北から yf 行目の区画を (x, y) と表す．北西の角の区画は (1, 1) であり，南東の角の区画は (W, H) である．各区画は「着陸可能」か「着陸不可能」かのいずれかであり，「着陸可能」は “.”，「着陸不可能」は “w” で表される．
IOI 星の宇宙人が作る UFO は幅 B メートル，奥行き D メートルにおさまる．この UFO は仕様上，設計図での上下左右がそれぞれ UFO において北，南，西，東の方角となるように，また設計図での左上の角がJOI 公園のいずれかの区画の左上と一致するように着陸しなければならない．UFO の設計図は D 行 B 列のマス目からなる．マスは全部で B \times D 個あり，左から i 列目，上から j 行目のマスを (i, j) と表す．左上のマスは (1, 1) であり，右下のマスは (B, D) である．マス (i, j) は UFO の西の端から i – 1 メートル ～ i メートル，北の端から j – 1 メートル ～ j メートルの正方形の範囲に UFO の一部が含まれるか否かを示す．各マスは UFO の一部が「含まれる」か「含まれない」かのいずれかであり，含まれる場合は “O” (大文字のオー)，含まれない場合は “.” で表される．
ある 1 個の UFO が着陸する時，設計図上のマスで UFO に「含まれる」全ての場所は，着陸時に「着陸可能」な区画に含まれなければならない．また複数個の UFO が着陸する時は，ある UFO の設計図上のマスで「含まれる」全ての場所は，別の UFO の設計図上のマスで「含まれる」いずれの場所とも辺を共有することはできない．ただし，UFO は角を共有する場所に着陸することはできる．
あなたは奇しくも IOI 星の親善大使として選ばれた．そこで，あなたには，出来る限り多くの UFO の着陸が可能な飛行場を作る計画書を作って欲しい．
課題
JOI 公園に作る UFO の飛行場の計画書を作成せよ．より多くの個数の UFO を着陸させる計画書を作ることにより，あなたはより高い得点を得る．計画書は JOI 公園の地図上に着陸した UFO を書き加えたものであり，JOI 公園の「着陸可能」な区画のうち，着陸した UFO が含まれる区画を “O” (大文字のオー)，着陸した UFO が含まれない区画を “.” で表し，「着陸不可能」な区画は “w” で表す．
制限
| 1 \leq B \leq 5 | UFO の幅 (メートル) |
| 1 \leq D \leq 5 | UFO の奥行き (メートル) |
| 1 \leq W \leq 200 | JOI 公園の東西方向の大きさ (メートル) |
| 1 \leq H \leq 200 | JOI 公園の南北方向の大きさ (メートル) |
入力
入力ファイルは以下の形式で与えられる．
- 1 行目には整数 B, D が空白を区切りとして書かれており，UFO の幅が B メートル，奥行きが D メートルであることを表す．
- 続く D 行には UFO の設計図の情報が書かれている．j + 1 行目 (1 \leq j \leq D) には，B 文字の文字列が書かれており，i 文字目 (1 \leq i \leq B) には設計図のマス (i, j) を表す “O” または “.” の文字が書かれている．
- D + 2 行目には整数 W, H が空白を区切りとして書かれており，JOI 公園の東西方向の大きさが W メートル，南北方向の大きさが H メートルであることを表す．
- 続く H 行には JOI 公園の地図の情報が書かれている．y + D + 2 行目 (1 \leq y \leq H) には，W 文字の文字列が書かれており，x 文字目 (1 \leq x \leq W) には公園の区画 (x, y) を表す “.” または “w” の文字が書かれている．
出力
出力の y 行目 (1 \leq y \leq H) には公園の北から y 行目の状態を表す W 文字の文字列を書け．y 行目 (1 \leq y \leq H) の x 文字目 (1 \leq x \leq W) は区画 (x, y) の状態を表す “O” または “.” または “w” のいずれかの文字である．
提出方法
各入力データに対する出力を提出せよ．その際，出力のセクションで指定された形式に一致するかのみがチェックされる．
採点基準
各入力ファイルには以下に示す X の値が割り当てられている．参加者が提出した計画書のうちの着陸できる UFO の個数の最大値を Y とする．あなたの計画書が問題の条件を満たさない場合，あなたの得点は 0 点である．条件を満たす場合，α をあなたの計画書における着陸できる UFO の個数とし，
- α \leq X の時は，\frac{4α}{X} の小数第 2 位を四捨五入した値，
- X < α の時は，4 + 16 \times ( \frac{α-X}{Y-X} ) ^2 の小数第 2 位を四捨五入した値，
があなたの得点となる．
| 入力ファイル | B | D | W | H | X |
|---|---|---|---|---|---|
| 01 | 1 | 1 | 15 | 15 | 90 |
| 02 | 1 | 1 | 10 | 200 | 750 |
| 03 | 3 | 3 | 100 | 100 | 500 |
| 04 | 5 | 5 | 180 | 180 | 1270 |
| 05 | 5 | 5 | 200 | 200 | 1050 |
入出力の例
| 入力例 | 出力例 |
|---|---|
| 4 3 O..O OOOO .O.. 20 10 .................... .w......w.......ww.. ....ww......w.w..... .w.....w............ ...w......w......... w................ww. ....w............... .w.....w........w.ww ............w....... ....w..............w |
..O..O......O..O.... .wOOOO.Ow.O.OOOOww.. ...Oww.OOOO.wOw.O..O .w.....wO..O..O.OOOO .O.wO.O..OwOOOO..O.. wOOOO.OOOO..O...OwwO ..O.w..O..O..O..OOOO Ow.O.O.wO.OOOO..wOww OOOO.OOOO..Ow....... .O..w.O............w |
この出力例は，11 個の UFO を着陸させることができる計画書である．