prithivMLmods/Coder-Stat

1 2 3 4 5<h1>KND Factory</h1>6<h2>Problem</h2>7 8<p>9KND君は会津大学に在籍する学生プログラマである。彼の住む町の周辺には<var> N </var>個の町がある。彼は生クリームが大好きなので毎日生クリームを食べるためにある町に工場を建設した。その工場では毎日<var> F </var>リットルの生クリームが製造される。生クリームは運ぶたびに、移動元の町の気温と移動先の町の気温の絶対差だけ傷んでしまう。困ったことにこの近辺の町の気温は寒暖計によって計測できない。しかしながら調査によって、それぞれの町の気温を変数とした<var> N </var>個の一次方程式からなる<var> N </var>元一次連立方程式を導くことができた。あなたはこれを解くことによって各町の気温を知ることができる。また、ある町から他の町へ生クリームを運搬するにはパイプラインを用いる。パイプラインは一日に送ることのできる生クリームの量が限られている。一日に<var> F </var>リットルの生クリームを工場がある町<var> s </var>からKND君が住む町<var> t </var>へ生クリームをなるべく良い状態で送りたい。町には0から始まる番号がつけられているものとする。方程式の各項は高々ひとつの変数からなり定数項がひとつある。<var> F </var>リットルの生クリームはどのような運び方をしても一日以内で任意の町へ送られる。<br>10</p>11 12<h2>Input</h2>13<p>入力は複数のテストケースからなる。ひとつのテストケースは以下の形式で与えられる。テストケースの数は入力として与えられる。</p>14<pre>15<var>T</var>16<var>N</var> <var>s</var> <var>t</var> <var>F</var>17<var>a<sub>1,1</sub></var> <var>a<sub>1,2</sub></var> ... <var>a<sub>1,N</sub></var> <var>c<sub>1</sub></var>18<var>a<sub>2,1</sub></var> <var>a<sub>2,2</sub></var> ... <var>a<sub>2,N</sub></var> <var>c<sub>2</sub></var>19...20<var>a<sub>N,1</sub></var> <var>a<sub>N,2</sub></var> ... <var>a<sub>N,N</sub></var> <var>c<sub>N</sub></var>21<var>M<sub>1</sub></var>22<var>d<sub>1,1</sub></var> <var>d<sub>1,2</sub></var> ... <var>d<sub>1,M<sub>1</sub></sub></var>23<var>f<sub>1,1</sub></var> <var>f<sub>1,2</sub></var> ... <var>f<sub>1,M<sub>1</sub></sub></var>24<var>M<sub>2</sub></var>25<var>d<sub>2,1</sub></var> <var>d<sub>2,2</sub></var> ... <var>d<sub>2,M<sub>2</sub></sub></var>26<var>f<sub>2,1</sub></var> <var>f<sub>2,2</sub></var> ... <var>f<sub>2,M<sub>2</sub></sub></var>27...28<var>M<sub>N</sub></var>29<var>d<sub>N,1</sub></var> <var>d<sub>N,2</sub></var> ... <var>d<sub>N,M<sub>2</sub></sub></var>30<var>f<sub>N,1</sub></var> <var>f<sub>N,2</sub></var> ... <var>f<sub>N,M<sub>2</sub></sub></var>31</pre>32<p>ここで、33</p>34<ul>35<li><var>T</var>:テストケースの数</li>36<li><var>N</var>:町の数</li>37<li><var>s</var>:工場のある町</li>38<li><var>t</var>:KND君の住む町</li>39<li><var>F</var>:一日に作られる生クリームの量</li>40<li><var>a<sub>i,j</sub></var>:連立方程式の未知数としてのi番目の方程式中でj番目の町の気温にかかる係数。もし<var>a<sub>i,j</sub></var>=0ならj番目の町の気温はこの方程式に現れないことになる。以下の例も参照してほしい。</li>41<li><var>c<sub>i</sub></var>:i番目の方程式の定数項</li>42<li><var>M<sub>i</sub></var>:i番目の町が持っている生クリームを移動させる機械の数</li>43<li><var>d<sub>i,j</sub></var>:i番目の町が持っているj番目の機械が生クリームを移動させる先の町</li>44<li><var>f<sub>i,j</sub></var>:i番目の町が持っているj番目の機械が生クリームを1日に移動させられるリットル量</li>45</ul>46<p>47である。48</p>49<p>50<var>N</var>元一次連立方程式を表す行列の入力例:<br>51</p>52<pre>53 a +  b      = 6       1  1 0  6543a + 2b + c  = 10  =>  3  2 1 1055 a - 2b + 3c = 6       1 -2 3  656</pre>57<p>58a,b,cが町0,1,2の気温を表す。59</p>60 61<h2>Constraints</h2>62<p>入力は以下の条件を満たす。</p>63<ul>64<li>入力はすべて整数。</li>65<li>0 &lt;<var> T </var>&le; 40</li>66<li>2 &lt;<var> N </var>&le; 100</li>67<li>0 &le;<var> s </var>&lt;<var> N </var></li>68<li>0 &le;<var> t </var>&lt;<var> N </var></li>69<li><var>s</var> &ne; <var>t</var></li>70<li>0 &lt;<var> F </var>&le; 1000</li>71<li>0 &le;<var> M<sub>i</sub> </var>&le;<var> N </var></li>72<li>-1000 &le; <var>a<sub>i,j</sub></var> &le; 1000</li>73<li>0 &le;<var>f<sub>i,j</sub></var>&lt; 1000</li>74<li>それぞれの町の気温は一意に定まる。</li>75</ul>76 77<h2>Output</h2>78<p>79各テストケースにつき、一日に<var> F </var>リットルの生クリームを工場がある町<var> s </var>からKND君が住む町<var> t </var>に運んだとき、生クリームの傷みの和を最小化した値を一行で出力せよ。この値はジャッジ出力の値と10<sup>-5</sup>より大きい差を持ってはならない。また、町<var> s </var>から町<var> t </var>へ<var> F </var>リットルの生クリームを一日に運べない場合はimpossibleを一行で出力せよ。80</p>81 82<h2>Sample Input</h2>83<pre>843853 0 2 5861 1 1 6873 2 1 10881 -2 3 6892901 2913 3921932943950963 0 2 5971 1 1 6983 2 1 10991 -2 3 610021011 21022 2103110421052106010710 2 7 201088 9 -5 6 -9 5 1 0 4 9 41093 -1 -8 0 -5 4 3 0 -3 2 4110-4 5 8 -4 1 -8 -6 3 3 5 -7111-7 0 2 5 8 -5 -9 -8 1 -2 -11123 8 1 -3 8 2 -5 8 -3 4 -4113-2 5 0 -2 -4 4 -3 9 6 -1 -21144 1 2 -9 3 5 6 -4 4 -1 -4115-4 6 6 9 -2 1 -9 -3 -7 3 -41161 -1 6 3 1 -5 9 5 -5 -9 -5117-7 4 6 8 8 4 -4 4 -7 -8 -511851191 5 0 6 312015 17 14 7 1512131221 5 71236 8 14124101253 5 3 5 9 5 9 5 1 412612 6 16 11 16 7 9 3 13 13127101289 1 5 6 2 5 8 5 9 412915 8 8 14 13 13 18 1 12 1113051313 5 0 4 613214 15 4 14 1113391345 0 6 2 7 8 8 6 61356 5 7 17 17 17 17 19 313691377 7 2 7 8 4 7 7 01384 13 16 10 19 17 19 12 1913931401 5 11413 7 1614281435 7 4 9 1 4 6 81444 3 6 12 6 19 10 114541461 3 6 31475 15 18 14148</pre>149 150<h2>Sample Output</h2>151<pre>15210.0000000000153impossible15411.9354380207155</pre>