prithivMLmods/Coder-Stat

1 2 3 4<H1>ルパン四世</H1>5 6<p>7怪盗「ルパン四世」は会津藩士を末裔とする美女「富士峰子」より、会津若松市に会津藩が残した軍資金が眠っていることを聞かされる。ルパンの長年の仲間である「石川越ェ門」の報告によれば、軍資金は千両箱に収められいくつかの蔵に保管されている。蔵に見張りはいないが厳重に施錠されている。しかし、越ェ門は彼が父から伝授された秘伝「鋼鉄斬り」の技を繰り出せば瞬時に蔵を破れるという。8</p>9 10<center>11<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_lupin">12</center>13<br/>14 15<p>16残った問題は千両箱の運搬だ。体力のないルパンと越ェ門は千両箱を一つも持てない。そこで、頼りになる男「無限大介」に運搬を頼んだ。<!--大介は米俵を使った訓練を重ね、超人的な運搬能力を身につけた。-->17すべての千両箱を運び出すために、ルパンは以下のような計画を立案した。18</p>19 20<p>21まず、ルパンの運転で最初の蔵へ行き、越ェ門と大介を降ろす。22</p>23 24<ul>25<li>越ェ門が蔵を破る</li>26<li>大介がすべての千両箱を運び出す</li>27<li>その千両箱を持ったままルパンが決めた次の蔵へ向かう</li>28</ul>29 30<p>31これを繰り返し、最後の蔵まで破り千両箱を運び出す。その間にルパンはヘリコプターを準備し最後の蔵で二人と千両箱を運び上げ脱出する。大介はどんなに重いものも運搬できるが、荷物の重さに応じて移動速度は遅くなる。ルパンは、このことを考慮して蔵を破る順番を決めなければならない。32</p>33 34<p>35ルパンに代わって、最初の蔵を破ってから最後の蔵に辿りつくまでの移動時間が最小となるような蔵を破る順番を出力するプログラムを作成してください。ただし、36</p>37 38<ul>39<li>蔵はすべて鶴ヶ城からまっすぐ北に走る通りに面している。蔵の数は高々 15 個であり、城からの距離は高々 10000 メートル以下である。</li>40<li>千両箱の重さはいずれもひとつ 20 キログラムである。それぞれの蔵に収められている千両箱の個数は 10000 個以下である。</li>41<li>蔵から蔵への移動は、通りに沿って地下に設置されている地下道を使う。</li>42<li>大介は <var>w</var> キログラムの荷物を運ぶのに、分速 2,000／(70 + <var>w</var>) メートルで移動する。</li>43<!--<li>富士峰子は計画を妨害する恐れがあるので事前に睡眠薬を飲ませて眠らせる。このほかの妨害についても、遺漏なく対処する。</li>-->44</ul>45 46<p>47入力データは、それぞれの蔵について蔵の番号（100 以下の整数）と城からの距離（メートル）とその蔵に保管されている千両箱の個数が与えられる。48</p>49 50<H2>Input</H2>51 52<p>53入力は以下の形式で与えられます。54</p>55 56<pre>57<var>n</var>58<var>s<sub>1</sub></var> <var>d<sub>1</sub></var> <var>v<sub>1</sub></var>59<var>s<sub>2</sub></var> <var>d<sub>2</sub></var> <var>v<sub>2</sub></var>60:61<var>s<sub>n</sub></var> <var>d<sub>n</sub></var> <var>v<sub>n</sub></var>62</pre>63 64<p>651 行目に蔵の個数 <var>n</var>（<var>n</var> &le; 15）、続く <var>n</var> 行に第 <var>i</var> の蔵の情報が与えられます。蔵の情報として、蔵の番号 <var>s<sub>i</sub></var> (1 &le; <var>s<sub>i</sub></var> &le; 100)、城からの距離 <var>d<sub>i</sub></var> (1 &le; <var>d<sub>i</sub></var> &le; 10000)、 千両箱の数 <var>v<sub>i</sub></var> (1 &le; <var>v<sub>i</sub></var> &le; 10000) が１行に与えられます。66</p>67 68 69<H2>Output</H2>70 71<p>72蔵を破る順番を１行に出力してください。蔵の番号を空白で区切ってください。73</p>74 75<H2>Sample Input 1</H2>76 77<pre>782791 100 1802 200 281</pre>82 83<H2>Output for the Sample Input 1</H2>84 85<pre>861 287</pre>88 89 90<H2>Sample Input 2</H2>91 92<pre>9339411 100 19513 200 209612 300 397</pre>98 99<H2>Output for the Sample Input 2</H2>100 101<pre>10211 12 13103</pre>104 105 106 107 108<H2>Sample Input 3</H2>109 110<pre>111511213 199 111351 1000 111437 350 1011527 300 211699 200 1000117</pre>118 119<H2>Output for the Sample Input 3</H2>120 121<pre>12251 37 27 13 99123</pre>124 125 126 127 128