← 返回题目列表

AtCoder · joisc2011_ufo4

ufo4. 不明飞行物机场 (UFO)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

UFOの飛行場 (UFO) - 原题 PDF 第 1 页
原题PDF第6页
UFOの飛行場 (UFO) - 原题 PDF 第 2 页
原题PDF第7页
UFOの飛行場 (UFO) - 原题 PDF 第 3 页
原题PDF第8页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                             Contest Day 3 – UFO

                  UFO の飛行場(UFO)
                       出力のみの課題(Output-only task)


  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 ≦5    UFO の幅(メートル)
   1 ≦D ≦5   UFO の奥行き(メートル)
   1 ≦W ≦200  JOI 公園の東西方向の大きさ(メートル)
   1 ≦H ≦200   JOI 公園の南北方向の大きさ(メートル)


                           UFO の飛行場– 1 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                             Contest Day 3 – UFO


入力

 入力ファイルは以下の形式で与えられる.

   • 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” のいずれかの文字である.


提出方法

 各入力データに対する出力を提出せよ.その際,出力のセクションで指定された形式に一致するかのみ
がチェックされる.





                           UFO の飛行場– 2 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                             Contest Day 3 – UFO


採点基準

 各入力ファイルには以下に示すX の値が割り当てられている.参加者が提出した計画書のうちの着陸で
きるUFO の個数の最大値をY とする.あなたの計画書が問題の条件を満たさない場合,あなたの得点は
0 点である.条件を満たす場合,α をあなたの計画書における着陸できるUFO の個数とし,
   • α ≦X の時は,4α の小数第2 位を四捨五入した値,
               X
                       (α −X )2
   • X < α の時は,4 + 16 ×     の小数第2 位を四捨五入した値,
                        Y −X

があなたの得点となる.

  入力ファイル  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......O..O....
 O..O                                    .wOOOO.Ow.O.OOOOww..
 OOOO                                    ...Oww.OOOO.wOw.O..O
 .O..                                    .w.....wO..O..O.OOOO
 20 10                                   .O.wO.O..OwOOOO..O..
 ....................                    wOOOO.OOOO..O...OwwO
 .w......w.......ww..                    ..O.w..O..O..O..OOOO
 ....ww......w.w.....                    Ow.O.O.wO.OOOO..wOww
 .w.....w............                    OOOO.OOOO..Ow.......
 ...w......w.........                    .O..w.O............w
 w................ww.
 ....w...............
 .w.....w........w.ww
 ............w.......
 ....w..............w

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




                           UFO の飛行場– 3 / 3