H - Hurdling Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

すぬけ君は数直線上でハードル走をします。 座標 0 がスタート地点、座標 L がゴール地点です。 数直線上には N 個のハードルがあり、左から i 番目のハードルは座標 x_i にあります。(0 < x_1 < x_2 < \cdots < x_N < L が成立します。)

すぬけ君は、以下の 3 種類の行動のうち一つを選んで実行する、ということを繰り返し行うことができます。

  • 行動 1: 距離 1 を走って進む。
  • 行動 2: 距離 0.5 を走って進み、ジャンプして距離 1 を進み、また距離 0.5 を走って進む。合計で 2 の距離を進むことになる。
  • 行動 3: 距離 0.5 を走って進み、ジャンプして距離 3 を進み、また距離 0.5 を走って進む。合計で 4 の距離を進むことになる。

すぬけ君は、走っているときは距離 1 あたり T_1 秒、ジャンプ中は距離 1 あたり T_2 秒の速さで進みます。ただし、すぬけ君がジャンプ中でないときに座標 x にいて、座標 x にハードルがある場合、その地点を通り過ぎるのに追加で T_3 秒の時間がかかります。T_1, T_2, T_3 は全て偶数です。

すぬけ君が座標 L を通るまでにかかる秒数の最小値を求めてください。(座標 L をジャンプして通過する場合は、ジャンプ中に座標 L を通過するまでの秒数が「座標 L を通るまでにかかる秒数」です。) 答えは整数であることが証明できます。

制約

  • 入力は全て整数
  • 2 \leq L \leq 10^5
  • 1 \leq N < L
  • 0 < x_1 < x_2 < \cdots < x_N < L
  • 2 \leq T_1, T_2, T_3\leq 1000
  • T_1, T_2, T_3 は偶数

入力

入力は以下の形式で標準入力から与えられる。

N L
x_1 x_2 \cdots x_N
T_1 T_2 T_3

出力

すぬけ君が座標 L を通るまでにかかる秒数の最小値を整数として出力せよ。(答えは整数であることが証明できる。)

入力例 1

2 5
1 4
2 2 20

出力例 1

10

ハードルが座標 1 と 4 にあります。この場合、以下のようにするのが最適です。

  1. 行動 2 を実行する。走って進む距離は 1、ジャンプして進む距離は 1 であるため、合計で 2 \times 1 + 2 \times 1 = 4 秒かかる。
  2. 行動 1 を実行する。2 秒かかる。
  3. 行動 3 を実行する。行動の途中で座標 L=5 に到達し、到達までに走って進む距離は 0.5、ジャンプして進む距離は 1.5 であるため、合計で 2 \times 0.5 + 2 \times 1.5 = 4 秒かかる。

以上が最適であり、合計で 4 + 2 + 4 = 10 秒かかるため、10 を出力します。

入力例 2

4 5
1 2 3 4
2 20 100

出力例 2

164

入力例 3

10 19
1 3 4 5 7 8 10 13 15 17
2 1000 10

出力例 3

138

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Snuke will run the hurdles on a number line. He will start at coordinate 0 and finish at coordinate L. There are N hurdles on the number line, and the i-th hurdle from the left is at coordinate x_i. (0 < x_1 < x_2 < \cdots < x_N < L holds.)

Snuke can repeatedly choose one of the three actions below and do it:

  • Action 1: Run the distance of 1.
  • Action 2: Run the distance of 0.5, jump the distance of 1, and run the distance of 0.5, for a total distance of 2.
  • Action 3: Run the distance of 0.5, jump the distance of 3, and run the distance of 0.5, for a total distance of 4.

Snuke goes at the speed of 1 unit distance per T_1 seconds while running, and 1 unit distance per T_2 seconds while in the air. However, if Snuke is at coordinate x while he is not in the air and there is a hurdle at coordinate x, it takes extra T_3 seconds to go past the point. Here, T_1, T_2, and T_3 are even numbers.

Find the minimum number of seconds Snuke needs before he passes coordinate L. (If he jumps over coordinate L, we consider the time when he passes coordinate L in the air.) We can prove that the answer is an integer.

Constraints

  • All values in input are integers.
  • 2 \leq L \leq 10^5
  • 1 \leq N < L
  • 0 < x_1 < x_2 < \cdots < x_N < L
  • 2 \leq T_1, T_2, T_3\leq 1000
  • T_1, T_2, and T_3 are even numbers.

Input

Input is given from Standard Input in the following format:

N L
x_1 x_2 \cdots x_N
T_1 T_2 T_3

Output

Print the minimum number of seconds Snuke needs before he passes coordinate L, as an integer. (It can be proved that this number is an integer.)

Sample Input 1

2 5
1 4
2 2 20

Sample Output 1

10

There are hurdles at coordinate 1 and 4. In this case, the optimal strategy is as follows:

  1. Do Action 2. We run the distance of 1 in total and jump the distance of 1, so it takes 2 \times 1 + 2 \times 1 = 4 seconds in total.
  2. Do Action 1. It takes 2 seconds.
  3. Do Action 3, during which we pass coordinate L=5. Before we pass this point, we run the distance of 0.5 and jump the distance of 1.5, so it takes 2 \times 0.5 + 2 \times 1.5 = 4 seconds in total.

The time taken in this optimal strategy is 4 + 2 + 4 = 10 seconds in total, so we should print 10.

Sample Input 2

4 5
1 2 3 4
2 20 100

Sample Output 2

164

Sample Input 3

10 19
1 3 4 5 7 8 10 13 15 17
2 1000 10

Sample Output 3

138