問題一覧 > 通常問題

No.2010 Magical Floor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-8}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 20
作問者 : 👑 Kiri8128Kiri8128 / テスター : tarattata1tarattata1
1 ProblemId : 5554 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-07 02:01:54

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。