24104번 - UFO の飛行場 (UFO) 4 점수다국어

IOI 星の宇宙人は日本にある JOI 公園 (ただし，一般の人には存在は秘密にされている) に UFO の飛行場 を作る計画を立てている．IOI 星の宇宙人は JOI 公園を調査し，UFO が着陸可能な場所を示した地図を作 成した．

JOI 公園は東西 W メートル，南北 H メートルの長方形であり，1 メートル四方の正方形の区画に分けら れている．区画は全部で W × H 個あり，西から x 列目，北から y 行目の区画を (x, y) と表す．北西の角の 区画は (1, 1) であり，南東の角の区画は (W, H) である．各区画は「着陸可能」か「着陸不可能」かのいず れかであり，「着陸可能」は “.”，「着陸不可能」は “w” で表される．

IOI 星の宇宙人が作る UFO は幅 B メートル，奥行き D メートルにおさまる．この UFO は仕様上，設計 図での上下左右がそれぞれ UFO において北，南，西，東の方角となるように，また設計図での左上の角が JOI 公園のいずれかの区画の左上と一致するように着陸しなければならない．UFO の設計図は D 行 B 列の マス目からなる．マスは全部で B × 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 行目には整数 B, D が空白を区切りとして書かれており，UFO の幅が B メートル，奥行きが D メー トルであることを表す．
• 続く D 行には UFO の設計図の情報が書かれている．j + 1 行目 (1 ≤ j ≤ D) には，B 文字の文字列が 書かれており，i 文字目 (1 ≤ i ≤ B) には設計図のマス (i, j) を表す “O” または “.” の文字が書かれて いる．
• D+2 行目には整数 W, H が空白を区切りとして書かれており，JOI 公園の東西方向の大きさが W メー トル，南北方向の大きさが H メートルであることを表す．
• 続く H 行には JOI 公園の地図の情報が書かれている．y + D + 2 行目 (1 ≤ y ≤ H) には，W 文字の文 字列が書かれており，x 文字目 (1 ≤ x ≤ W) には公園の区画 (x, y) を表す “.” または “w” の文字が書 かれている．

出力の y 行目 (1 ≤ y ≤ H) には公園の北から y 行目の状態を表す W 文字の文字列を書け．y 行目 (1 ≤ y ≤ H) の x 文字目 (1 ≤ x ≤ W) は区画 (x, y) の状態を表す “O” または “.” または “w” のいずれかの文字である．

• 1 ≤ B ≤ 5 UFO の幅 (メートル)
• 1 ≤ D ≤ 5 UFO の奥行き (メートル)
• 1 ≤ W ≤ 200 JOI 公園の東西方向の大きさ (メートル)
• 1 ≤ H ≤ 200 JOI 公園の南北方向の大きさ (メートル)

各入力ファイルには以下に示す X の値が割り当てられている．参加者が提出した計画書のうちの着陸で きる UFO の個数の最大値を Y とする．あなたの計画書が問題の条件を満たさない場合，あなたの得点は 0 点である．条件を満たす場合，α をあなたの計画書における着陸できる UFO の個数とし，

• α ≤ X の時は，4α/X の小数第 2 位を四捨五入した値，
• X < α の時は，4 + 16 × ((α − X)/(Y − X))² の小数第 2 位を四捨五入した値，

があなたの得点となる．

この出力例は，11 個の UFO を着陸させることができる計画書である．