Long và Vân cùng nhau chơi trò chơi trên dãy số như sau: Long sẽ chọn một dãy gồm \(n\) số \(a_1, a_2,\dots , a_n\). Sau đó, Vân sẽ tìm cách biến đổi dãy số nguyên \(a_1, a_2,\dots , a_n\) về dãy đẹp bậc \(d\) bằng dãy các bước biến đổi như sau: Mỗi bước, chọn một số trong dãy, tăng hoặc giảm số đó đi một đơn vị. Một dãy \(b_1, b_2,\dots , b_n\) được gọi là dãy đẹp bậc \(d\) nếu \(b_i = b_{i−1} + d\) với \(i = 2, 3,\dots , n\). Cụ thể, dãy \(b_1, b_2 = b_1 + d, … , b_n = b_{n−1} + d\) là dãy đẹp bậc \(d\).
Ví dụ, dãy (\(3, 2, 2\)) với \(d = 1\) mất ít nhất \(3\) phép biến đổi để đưa về dãy (\(1, 2, 3\)) là một dãy đẹp bậc \(1\).
Yêu cầu: Cho dãy số nguyên \(a_1, a_2,\dots , a_n\) và số nguyên dương \(d\), hãy tính số bước ít nhất cần dùng để biến đổi dãy \(a_1, a_2,\dots , a_n\) thành một dãy đẹp bậc \(d\).
Input
- Dòng đầu chứa số nguyên \(n\) (\(n \leq 1000\)) và \(d\);
- Dòng thứ hai chứa \(n\) số nguyên mô tả dãy \(a_1, a_2,\dots , a_𝑛\).
Output
- Một dòng, chứa một số nguyên là số bước ít nhất cần dùng để biến đổi dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) thành một dãy đẹp bậc \(𝑑\).
Scoring
- Subtask #1 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^3\)
- Subtask #2 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^9\)
- Subtask #3 (\(25\%\) số điểm): \(d = 1\) và \(|a_i| \leq 10^3\)
- Subtask #4 (\(25\%\) số điểm): \(d \leq 10^9\) và \(|a_i| \leq 10^9\)
Example
Test 1
Input
3 1
3 2 2
Output
3
Nguồn: 2019 chính thức
Comments
bài này làm kiểu gì vậy ạ ?(đã ac:D)
This comment is hidden due to too much negative feedback. Click here to view it.