新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
Special Judge
問題 
あるとき、Bessieは標高がE(-25<=E<=25)で、R(1<=R<=100)×C(1<=C<=100)の格子の左上の角にいることに気付いた。彼女はその右下の角にできるだけ早く移動しなくてはならないが、北、南、東、西にしか移動できない。
Bessieの初速はV(1<=V<=1,000,000)である。彼女は速度と標高についての関係を発見した。標高Aの地点から標高Bの地点に移動すると、彼女の速度は2^(A-B)倍になるのである。ある地点から別の地点に移動するのにかかる時間は、最初の地点での速度の逆数になる。
目的地に到達するまでの最小の時間を求めよ。
入力
一行目に、スペース区切りの三つの整数V,R,Cが与えられる。順番に、Bessieの最初の速度、格子の行数、格子の列数である。
二行目からR+1行目にはC個ずつの整数が与えられ、対応する格子上の地点の標高Eである。
出力
格子の右下に到達するまでの最短時間を、ちょうど小数点以下2桁まで出力する。
入力の例
1 3 3 1 5 3 6 3 5 2 4 3
出力の例
29.00
ヒント
Bessieの最短経路は以下の通り。
1,1 の地点を時刻 0 速度 1 で出発し、
東の地点 1,2 に時刻 1 速度 1/16 で到達する。
南の地点 2,2 に時刻 17 速度 1/4 で到達する。
南の地点 3,2 に時刻 21 速度 1/8 で到達する。
東の地点 3,3 に時刻 29 速度 1/4 で到達する。
出典
USACO 2005 October Gold
