【問題14】ルパン四世 (50点)
 |
|---|
怪盗“ルパン四世”は会津藩士を末裔とする美女“富士峰子”より、会津若松市に会津藩が残した軍資金が眠っていることを聞かされる。ルパンの長年の仲間である“石川越ェ門”の報告によれば、軍資金は千両箱に収められいくつかの蔵に保管されている。蔵に見張りはいないが厳重に施錠されている。しかし、越ェ門は彼が父から伝授された秘伝“鋼鉄斬り”の技を繰り出せば瞬時に蔵を破れるという。
残った問題は千両箱の運搬だ。体力のないルパンと越ェ門は千両箱を1つも持てない。そこで、頼りになる男“無限大介”に運搬を頼んだ。大介は米俵を使った訓練を重ね、超人的な運搬能力を身につけた。すべての千両箱を運び出すために、ルパンは以下のような計画を立案した。まず、ルパンの運転で最初の蔵へ行き、越ェ門と大介を降ろす。
- 越ェ門が蔵を破る
- 大介が全ての千両箱を運び出す
- その千両箱を持ったままルパンが決めた次の蔵へ向かう
これを繰り返し、最後の蔵まで破り千両箱を運び出す。その間にルパンはヘリコプターを準備し、最後の蔵で2人と千両箱を運び上げ脱出する。大介はどんなに重いものも運搬できるが、荷物の重さに応じて移動速度は遅くなる。ルパンは、このことを考慮して蔵を破る順番を決めなければならない。
ルパンに代わって、最初の蔵を破ってから最後の蔵に辿りつくまでの移動時間が最小となるような蔵を破る順番を出力して終了するプログラムを作成してください。ただし、
- 蔵はすべて鶴ヶ城からまっすぐ北に走る通りに面している。蔵の数は高々15個であり、城からの距離は高々1万m以下である。
- 千両箱の重さはいずれもひとつ20kgである。それぞれの蔵に収められている千両箱の個数は1万個以下である。
- 蔵から蔵への移動は、通りにそって地下に設置されている地下道を使う。
- 大介は“w”kgの荷物を運ぶのに、分速2000／(70+“w”)mで移動する。
- 富士峰子は計画を妨害する恐れがあるので事前に睡眠薬を飲ませて眠らせる。このほかの妨害についても、遺漏なく対処する。
入力データは、それぞれの蔵について蔵の番号(100以下の整数)と城からの距離(m)とその蔵に保管されている千両箱の個数が与えられる。
入力
1行目 蔵の個数n（整数）
2行目 第1の蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））
3行目 第2の蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））
：
：
n+1行目 第nの蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））
出力
蔵を破る順番（整数；半角空白区切り）
| 入力例1 | 出力例1 |
|---|---|
| 2 1 100 1 2 200 2 |
1 2 |
| 入力例2 | 出力例2 |
|---|---|
|
3 11 100 1 13 200 20 12 300 3 |
11 12 13 |
| 入力例3 | 出力例3 |
|---|---|
| 5 13 199 1 51 1000 1 37 350 10 27 300 2 99 200 1000 |
51 37 27 13 99 |
次ページでは、今回の大会の審査委員からコメントを掲載しよう。
