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

View as PDF

Submit solution

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

Author:
Problem types

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 ~𝑛~ số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~. Sau đó, Vân sẽ tìm cách biến đổi dãy số nguyên ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~ về dãy đẹp bậc ~𝑑~ 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 ~𝑏_1, 𝑏_2, … , 𝑏_𝑛~ được gọi là dãy đẹp bậc ~𝑑~ nếu ~𝑏_𝑖 = 𝑏_{𝑖−1} + 𝑑~ với ~𝑖 = 2, 3, … , 𝑛~. Cụ thể, dãy ~𝑏_1, 𝑏_2 = 𝑏_1 + 𝑑, … , 𝑏_𝑛 = 𝑏_{𝑛−1} + 𝑑~ là dãy đẹp bậc ~𝑑~.

Ví dụ, dãy (~3, 2, 2~) với ~𝑑 = 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 ~𝑎_1, 𝑎_2, … 𝑎_𝑛~ và số nguyên dương ~𝑑~, hãy tính 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 ~𝑑~.

Dữ liệu vào

  • Dòng đầu chứa số nguyên ~𝑛~ (~𝑛 ≤ 1000~) và ~𝑑~;
  • Dòng thứ hai chứa ~𝑛~ số nguyên mô tả dãy ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Kết quả

  • 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 ~𝑑~.

Sample Input

3 1 
3 2 2

Sample Output

3

Ràng buộc:

  • Có 25% số test ứng với 25% số điểm của bài có ~𝑑 = 0~ và ~|𝑎_𝑖| ≤ 10^3~;
  • Có 25% số test khác ứng với 25% số điểm của bài có ~𝑑 = 0~ và ~|𝑎_𝑖| ≤ 10^9~;
  • Có 25% số test khác ứng với 25% số điểm của bài có ~𝑑 = 1~ và ~|𝑎_𝑖| ≤ 10^3~;
  • Có 25% số test còn lại ứng với 25% số điểm còn lại của bài có ~𝑑 ≤ 10^9~ và ~|𝑎_𝑖| ≤ 10^9~.

Nguồn: 2019 chính thức


View comments (3)

Comments


  • 0
    PhamtUan123  commented on 3:54 p.m. 2 jul, 2022 edited

    bài này làm kiểu gì vậy ạ ?(đã ac:D)


  • -2
    20NguyenLeMinh  commented on 7:16 a.m. 22 apr, 2021 edited

    .


    • 1
      boysitinh  commented on 4:45 p.m. 12 aug, 2021

      Anh bạn à, sửa cmt đi