#00 - Bài 3 - Nhảy

Xem PDF

Điểm: 1 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy gồm \(n+1\) ô xếp liên tiếp nhau từ ô \(0\) tới ô \(n\); trong đó có \(k\) ô \(A_1, A_2, \dots, A_k\) ta không thể bước chân vào (ô bị chặn).
Bạn ban đầu đứng ở ô \(0\), và bạn phải tìm cách di chuyển tới ô \(n\) bằng cách nhảy 1 ô hoặc nhảy 2 ô.
Cụ thể, nếu bạn đang ở ô \(i\), thì bạn có thể nhảy sang một trong hai ô sau, miễn là nơi bạn nhảy tới không phải là ô bị chặn và vẫn chưa nằm ngoài \(n+1\) ô:

  • nhảy sang ô \(i+1\), tốn \(a\) calo
  • nhảy sang ô \(i+2\), tốn \(b\) calo

Hãy tìm cách nhảy ít tốn sức nhất.

Dữ liệu đầu vào

  • Dòng thứ nhất chứa hai số lần lượt là \(n\)\(k\) \((0 \leq k \leq n \leq 10^9)\).
  • Dòng thứ hai chứa hai số lần lượt là \(a\)\(b\) \((0 \leq a, b \leq 10^9)\).
  • Nếu \(k>0\), dòng thứ ba chứa \(k\) số \(A_1, A_2, \dots, A_k\) \((1 \leq A_i < n)\).

Định dạng đầu ra

In ra một số duy nhất là số calo của cách nhảy ít tốn sức nhất.
Trong trường hợp không có cách nhảy nào thỏa mãn, in ra -1.

Điểm số

  • Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10^9; k=0\)
  • Subtask \(2\) (\(15\%\) số điểm): \(n \leq 10^5; b \geq 2a\)
  • Subtask \(3\) (\(20\%\) số điểm): \(n \leq 20\)
  • Subtask \(4\) (\(30\%\) số điểm): \(n \leq 10^5\)
  • Subtask \(5\) (\(25\%\) số điểm): \(n \leq 10^9; k \leq 10^5\)

Ví dụ

Ví dụ

Đầu vào
7 2
2 3
1 6
Đầu ra
11
Giải thích

Ta cần ít nhất 11 calo: \(0 \xrightarrow{\text{3 calo}} 2 \xrightarrow{\text{3 calo}} 4 \xrightarrow{\text{2 calo}} 5 \xrightarrow{\text{3 calo}} 7\)


Bình luận

Không có bình luận nào.