Nhảy xa
Xem dạng PDFThể dục thể thao, nâng cao sức khỏe. FPT Software Academy đang tổ chức cuộc thi nhảy xa để tìm ra nhà vô địch cho mùa giải mới. Tuy nhiên, luật chơi không chỉ yêu cầu sức khỏe mà còn yêu cầu một cái đầu có tư duy thuật toán thật là tốt. Là một thành viên của phòng marketing nhưng vẫn muốn giành chiến thắng trong giải đấu này, chị Thơ Nguyễn nhờ Đậu - Một thành viên mẫn cán của CLB TAS nghĩ lời giải cho cuộc thi.
Suy nghĩ mãi mà Đậu vẫn chưa tìm ra được chiến lược tối ưu. Các bạn cùng nghĩ với Đậu để giải quyết bài toán học búa này của nhà FSoft Academy nhé.
Luật chơi như sau:
Có ~N~ cột mốc, được đánh số từ 1 đến ~N~. Với mỗi chỉ số ~i~, độ cao của cột mốc thứ ~i~ là ~h_i~.
Đậu xuất phát từ cột mốc thứ nhất. Biết rằng, nếu Đậu đang đứng ở cột mốc thứ ~i~, cậu ta có thể nhảy đến được các cột mốc thứ ~i + 1, i + 2, ..., i + K~. Mỗi lần nhảy, Đậu sẽ tốn số năng lượng là ~|h_i - h_j|~, với ~j~ là cột mốc mà cậu ta muốn nhảy đến.
Các bạn hãy giúp Đậu tìm ra số năng lượng tiêu tốn tối thiểu để nhảy từ cột mốc đầu tiên đến cột mốc thứ ~N~.
Input
- Dòng đầu tiên là 2 số nguyên dương ~N~ và ~K~, lần lượt là số cột mốc và giới hạn nhảy của Đậu. ~(2 \leq N \leq 10^6, 1 \leq K \leq 100)~
- Dòng thứ hai gồm ~N~ số nguyên ~h_i~, là độ cao của cột mốc thứ ~i~. ~(1 \leq i \leq N, 1 \leq h_i \leq 10^{8})~
Output
- Gồm một số nguyên, là năng lượng ít nhất để nhảy từ cột mốc đầu tiên đến cột mốc thứ ~N~.
Chia độ khó
| Độ khó | Điều kiện |
|---|---|
| Dễ (50% tổng số điểm) | ~1 \leq N \leq 10^5, 1 \leq h_i \leq 10^4~ |
| Trung bình (50% tổng số điểm) | ~1 \leq N \leq 10^6, 1 \leq h_i \leq 10^8~ |
Sample input 1
2 1
10 10
Sample output 1
0
Sample input 2
3 1
10 30 10
Sample output 2
40
Sample input 3
5 3
10 30 40 50 20
Sample output 3
30
Notes
- Ở ví dụ thứ nhất, bước nhảy tối ưu là ~1 \to 2~. Năng lượng tiêu tốn sẽ là ~|10 - 10| = 0~
- Ở ví dụ thứ hai, bước nhảy tối ưu là ~1 \to 2 \to 3~. Năng lượng tiêu tốn sẽ là ~|10 - 30| + |30 - 10| = 40~
- Ở ví dụ thứ ba, bước nhảy tối ưu là ~1 \to 2 \to 5~. Năng lượng tiêu tốn sẽ là ~|10 - 30| + |30 - 20| = 30~
Bình luận
Để long long thì sai test 21-> 30 còn để int thì sai test 11->20 :D. Ad định để bọn em cắn test để AC r.
Bài này solution của web bị sai, thật hài hước!
Tôi hiện đang không thấy sol của bài này :v ông chỉ tôi được không, tôi fix ngay
Bài thi cho h[i] cận trên là 10^12, nhưng khi nhập dữ liệu dùng kiểu long long thì sai 1/3 số test, dùng int thì AC, vậy thì solution sai hay đúng?
Submission mà bạn AC là dùng int ở mảng h và dùng long long ở mảng dp. Ở đây mảng h trong bộ test không tới 10^12 tuy nhiên khi tính toán thì kết quả max có thể tới xấp xỉ N * h và vượt ra ngoài kiểu số int.
Vì vậy không phải test sai mà là test chưa đủ chặt so với giới hạn thôi, không phải "dùng long long thì sai, dùng int thì AC".
tôi gửi 3 submission, chỉ khác nhau việc dùng int và long long. Lẽ ra cái dùng long long toàn bộ phải là cái đúng nhất, nhưng nó lại sai (sai chứ không phải TLE). Điều này chứng tỏ solution để sinh kết quả của bài này viết sai.
Chào bạn, cảm ơn bạn đã có ý kiến về bài này. Bạn thử kiểm tra lại code xem nhé, mình vẫn ac bình thường và không có vấn đề gì ở đây cả.
Tất nhiên là mình đã AC, và vì vậy mình biết chất lượng bộ test có vấn đề, cụ thể là 10 test cuối có giá trị của h[i] nằm ngoài khoảng int. Nhưng solution dùng để sinh test đã viết ẩu và dùng kiểu int để read dữ liệu (thay vì long long), hệ quả là kết xuất output không chính xác. Thay vì cố gắng bao biện, các bạn hãy tập trung xem xét solution cho cẩn thận.
Cảm ơn bạn, mình sẽ xem xét lại bộ test của bài toán này. Rất mong sẽ có những đóng góp quan trọng của bạn trong thời gian tới để bọn mình cải thiện hơn.