No.2010 Magical Floor
タグ : / 解いたユーザー数 22
作問者 :
Kiri8128
/ テスター :
tarattata1
問題文
$xy$ 平面上に $N$ 個の魔法の床があり、
$i$ 番目（$1 \le i \le N$）の魔法の床は $H_{i-1} \le y < H_{i}$ の範囲を占めています。
ここで $0 = H_0 < H_1 < \cdots < H_N = H$ が成立します。
この平面上を移動するときの速さは場所によって変わり、 $i$ 番目の魔法の床の上では、距離 $1$ を進むのに $A_i$ の時間がかかります。
あなたはこの平面上の $0 \le y < H$ の部分を通って $(0,\ 0)$ から $(X,\ 0)$ まで移動したいです。
移動するのにかかる時間の最小値を求めてください。
$T$ 個のテストケースに答えてください。
入力
最初にテストケース数 $T$ が $1$ 行で与えられます。 $T$ は整数で $1 \le T \le 100$ を満たします。$T$
続く $3T$ 行で各テストケースの情報が与えられます。
各テストケースの情報は $3$ 行ごとに、次の形式で与えられます。
$N\ X$ $H_1\ H_2\ \cdots \ H_N$ $A_1\ A_2\ \cdots \ A_N$
（制約）
入力はすべて整数
$1 \le N \le 100$
$1 \le X \le 10^9$
$0 < H_1 < H_2 < \cdots < H_N \le 10^9$
$0 \le A_i \le 10^9$
出力
$(0,\ 0)$ から $(X,\ 0)$ まで移動するのにかかる時間の最小値を出力してください。
最後に改行してください。
正しい答えとの絶対誤差または相対誤差が $10^{-8}$ 以下であれば正解とみなされます。
なお、本問の制約下では必ず最小値が存在することが証明できます。
サンプル
サンプル1
入力
3 2 2 1 2 2 1 2 5 2 3 1 0 2 4 1 2 2 1
出力
4 4 7.464101615137754
このサンプルでは $3$ つのテストケースがあります。
$1$ つ目のテストケースでは、
$(0,\ 0)$ からまっすぐ $(2,\ 0)$ に向かうと $4$ の時間がかかります。
これより短い時間では到達できないので、 $4$ を出力します。
$2$ つ目のテストケースでは、
$(0,\ 0)$ からまっすぐ $(5,\ 0)$ に向かうと $5$ の時間がかかりますが、
$(0,\ 0)$ → $(0,\ 2)$ → $(5,\ 2)$ → $(5,\ 0)$ の順に移動すると $4$ の時間で到達できます。
$2$ 番目の魔法の床ではどれだけ移動しても時間はかかりません。
$3$ つ目のテストケースでは、
$(0,\ 0)$ からまっすぐ $(4,\ 0)$ に向かうと $8$ の時間がかかりますが、
うまく $2$ 番目の魔法の床を使うと少し早く到達できます。
正しい答えとの絶対誤差または相対誤差が $10^{-8}$ 以下であれば正解とみなされます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。