← 返回题目列表

AtCoder · joisc2010_simroad1

simroad1. 模拟道路

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

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

シムロード (SimRoad) - 原题 PDF 第 1 页
原题PDF第6页
シムロード (SimRoad) - 原题 PDF 第 2 页
原题PDF第7页
シムロード (SimRoad) - 原题 PDF 第 3 页
原题PDF第8页
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo


                                                                          Contest day 3 - SimRoad


                  シムロード(SimRoad)



  JOI 社はシムロードというシミュレーションゲームを販売している.このゲームでは,プレイヤーは舞
台となる国の統治者となり,その国を繁栄させるべく様々な操作を行う.
 舞台となる国は原始時代である.国には集落が点在しているのだが,この国は多くが背の高い草で覆わ
れており,その状態では集落間を容易に移動することはできない.プレイヤーであるあなたの最初のミッ
ションは住人が集落間を容易に移動できるように草刈をすることである.
 国の状態は東西W マス,南北H マスで区切られた3 種類の状態で表されるマスからなる.‘w’ はそのマ
スが草で覆われていることを示し,‘.’ はそのマスが更地である(草で覆われていない) ことを示し,‘@’ は
そのマスには集落があることを示す.


課題(TASK)

 住人は東西南北の隣り合った4 方向のマスのうち集落または更地であるマスへは自由に移動することが
できるが,草で覆われているマスは移動できない.そこで,住人が集落間を容易に移動できるように草で
覆われているマスの草を刈り取り更地にすることにより,どの集落からも全ての集落に移動できるように
草を刈らなければならない.
 草で覆われているマスの草を刈るとそのマスを更地にすることができるが,草刈をするには住人を働か
せる必要があり,1 マスの草を刈るためには1 ドルのお金がかかる.後々の繁栄のことを考えると使うお
金は少ない方が良い.
 当然,草の刈り取り方は多数存在することがある.与えられた国の状態から,出来る限り草を刈り取る
マスが少ない方法で草を刈り,その後の国の状態を生成しなさい.


基本アルゴリズム(BASIC ALGORITHM)

   y′ をH が偶数であればH/2 とし,H が奇数であれば(H + 1)/2 とする.まず北からy′ 行目のマスのう
ち草で覆われたマスを全て刈り取り,次に全ての集落について南北方向に北からy′ マス目との間にある草
で覆われたマスがあれば全て刈り取る.


制限(CONSTRAINTS)

   1 ≦W ≦100 国の東西方向のマスの数
   1 ≦H ≦100 国の南北方向のマスの数





                                                                                    Page 1 of 3

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo


                                                                          Contest day 3 - SimRoad


入力(INPUT)

 入力データは全部で5 つあり,ファイル名はsimroad-ink.txt (k = 1, 2, 3, 4, 5) である.入力ファイルは以
下のような形式で与えられる.

   • 1 行目には整数W とH が空白を区切りとして書かれている.

   • 続くH 行には各行W 文字の文字列が書かれており,国の状態を表す.これらの行のy 行目のx 文字
   目には,‘w’ または‘.’ または‘@’ の文字が書かれており,北からy マス目,西からx マス目のマス
   の状態を表す.


出力(OUTPUT)

 出力データはファイルで提出せよ.出力ファイルのファイル名はsimroad-outk.txt (k = 1, 2, 3, 4, 5) であ
る.simroad-outk.txt にはsimroad-ink.txt に対応した以下の形式のファイルを提出せよ.

   • 草刈をした後の国の状態を書け.出力はH 行からなり,各行はW 文字の文字列である.これらの行
   のy 行目のx 文字目には,北からy マス目,西からx マス目のマスの状態を表す‘w’ または‘.’ また
    は‘@’ の文字を書け.


採点基準(GRADING)

 得点は,あなたが出力した国の状態に依存する.あなたの各々のデータに対する得点は次のように決め
られる.課題の仕様に合致しない出力である場合,得点は0 点となる.仕様に合致している場合は,次の
ように得点は計算される.Ey をあなたの出力した国の状態にするためにかかる金額とし,Eb を基本アル
ゴリズムが生成する国の状態にするためにかかる金額とし,Em を競技参加者が提出した出力の国の状態に
するためにかかる金額の最小値とする.この場合のあなたの得点は

   • Ey ≧Eb ならば0

                      1/Ey −1/Eb
   • Ey < Eb ならば20
                   1/Em −1/Eb

の小数第2 位を四捨五入した値である.





                                                                                    Page 2 of 3

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo


                                                                          Contest day 3 - SimRoad


入出力例(EXAMPLE)

  入力例(Sample Input)
   7 5
   w@ww@w@
   w.wwwww
   wwww@ww
   @wwwwww
   ww@.@w.

 上記の入力例に対する基本アルゴリズムの出力は次のようになり,10 マスの草が覆われていたマスの草
を刈り取り更地にしているため,10 ドルのお金がかかる.

  基本アルゴリズムによる出力(Output by the basic algorithm)
   w@ww@w@
   w.ww.w.
   ....@..
   @w.w.ww
   ww@.@w.

 以下は,上記の入力例に対する出力例である.

  入力例(Sample Input)  出力例(Sample Output)
   7 5                 w@..@.@
   w@ww@w@             w.ww.ww
   w.wwwww             wwww@ww
   wwww@ww             @www.ww
   @wwwwww             ..@.@w.
   ww@.@w.

 この出力例の場合は,7 マスの草が覆われていたマスの草を刈り取り更地にしているため,7 ドルのお金
がかかっている.この出力例を提出した場合,もしあなたより小さな金額で作ることのできる国の状態の
出力を提出した人がいなければ20 点を得るが,Em が6 ドルであれば12.9 点を得ることとなる.





                                                                                    Page 3 of 3