Trò chơi trên dãy số (DHBB CT '19)
View as PDFLong 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 2Sample Output
3Rà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
Comments
bài này làm kiểu gì vậy ạ ?(đã ac:D)
.
Anh bạn à, sửa cmt đi