시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 18 | 3 | 3 | 17.647% |
JOI 社はシムロードというシミュレーションゲームを販売している.このゲームでは,プレイヤーは舞 台となる国の統治者となり,その国を繁栄させるべく様々な操作を行う.
舞台となる国は原始時代である.国には集落が点在しているのだが,この国は多くが背の高い草で覆わ れており,その状態では集落間を容易に移動することはできない.プレイヤーであるあなたの最初のミッ ションは住人が集落間を容易に移動できるように草刈をすることである.
国の状態は東西 W マス,南北 H マスで区切られた 3 種類の状態で表されるマスからなる.‘w’ はそのマ スが草で覆われていることを示し,‘.’ はそのマスが更地である (草で覆われていない) ことを示し,‘@’ は そのマスには集落があることを示す.
住人は東西南北の隣り合った 4 方向のマスのうち集落または更地であるマスへは自由に移動することが できるが,草で覆われているマスは移動できない.そこで,住人が集落間を容易に移動できるように草で 覆われているマスの草を刈り取り更地にすることにより,どの集落からも全ての集落に移動できるように 草を刈らなければならない.
草で覆われているマスの草を刈るとそのマスを更地にすることができるが,草刈をするには住人を働か せる必要があり,1 マスの草を刈るためには 1 ドルのお金がかかる.後々の繁栄のことを考えると使うお 金は少ない方が良い.
当然,草の刈り取り方は多数存在することがある.与えられた国の状態から,出来る限り草を刈り取る マスが少ない方法で草を刈り,その後の国の状態を生成しなさい.
基本アルゴリズム (BASIC ALGORITHM): y' を H が偶数であれば H/2 とし,H が奇数であれば (H + 1)/2 とする.まず北から y' 行目のマスのう ち草で覆われたマスを全て刈り取り,次に全ての集落について南北方向に北から y' マス目との間にある草 で覆われたマスがあれば全て刈り取る.
入力ファイルは以 下のような形式で与えられる.
出力データはファイルで提出せよ.
得点は,あなたが出力した国の状態に依存する.あなたの各々のデータに対する得点は次のように決め られる.課題の仕様に合致しない出力である場合,得点は 0 点となる.仕様に合致している場合は,次の ように得点は計算される.Ey をあなたの出力した国の状態にするためにかかる金額とし,Eb を基本アル ゴリズムが生成する国の状態にするためにかかる金額とし,Em を競技参加者が提出した出力の国の状態に するためにかかる金額の最小値とする.この場合のあなたの得点は
の小数第 2 位を四捨五入した値である.
7 5 w@ww@w@ w.wwwww wwww@ww @wwwwww ww@.@w.
w@..@.@ w.ww.ww wwww@ww @www.ww ..@.@w.
この出力例の場合は,7 マスの草が覆われていたマスの草を刈り取り更地にしているため,7 ドルのお金 がかかっている.この出力例を提出した場合,もしあなたより小さな金額で作ることのできる国の状態の 出力を提出した人がいなければ 20 点を得るが,Em が 6 ドルであれば 12.9 点を得ることとなる.
上記の入力例に対する基本アルゴリズムの出力は次のようになり,10 マスの草が覆われていたマスの草 を刈り取り更地にしているため,10 ドルのお金がかかる.
w@ww@w@ w.ww.w. ....@.. @w.w.ww ww@.@w.