Trò chơi trên dãy số (DHBB CT '19)

View as PDF

Points: 200 (p) Time limit: 1.0s Memory limit: 1023M Input: stdin Output: stdout

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\)\(|a_i| \leq 10^3\)
  • Subtask #2 (\(25\%\) số điểm): \(d = 0\)\(|a_i| \leq 10^9\)
  • Subtask #3 (\(25\%\) số điểm): \(d = 1\)\(|a_i| \leq 10^3\)
  • Subtask #4 (\(25\%\) số điểm): \(d \leq 10^9\)\(|a_i| \leq 10^9\)

Example

Test 1

Input
3 1 
3 2 2
Output
3

Nguồn: 2019 chính thức


Comments