Bedao Mini Contest 26 - Bản nhạc thế kỉ
Xem dạng PDF
Kadoc là một Producer nổi tiếng trong giới Showbiz. Năm nay, Kadoc muốn tiếng vang sự nghiệp của anh trở nên vang dội hơn. Do đó, anh muốn viết ra một bản nhạc nổi tiếng thế kỉ. Để thực hiện bản nhạc thế kỉ này, Kadoc đã thực hiện thu âm từ ~n~ loại nhạc cụ khác nhau, mỗi bản thu của các loại nhạc cụ có độ lớn âm lượng khác nhau, bản thu của loại nhạc cụ thứ ~i~ có độ lớn âm lượng là ~a_i~. Kadoc cho rằng để một bản nhạc có thể trở thành bản nhạc thế kỉ, âm lượng của các bản thu của các loại nhạc cụ phải thỏa mãn tính chất: $$a_{i+1} = a_i + k$$ Tại một thời điểm, Kadoc có thể chọn ra một bản thu của nhạc cụ bất kì và tăng hoặc giảm một đơn vị độ lớn. Ngoài ra, độ lớn âm lượng sau khi biến đổi cũng phải là số nguyên dương. Kadoc muốn tính toán xem anh sẽ mất ít nhất bao lâu để làm cho bản nhạc của mình trở thành bản nhạc thế kỉ. Hãy giúp Kadoc làm điều đó.
Input
Dòng đầu tiên gồm hai số nguyên ~n, k~ (~1 \le n, k \le 5000~) — lần lượt là số nhạc cụ và giá trị ~k~.
Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~1 \le a_i \le 5000~) — là độ lớn âm lượng của bản thu của loại nhạc cụ thứ ~i~.
Output
Gồm một dòng duy nhất là thời gian ngắn nhất để biến bản nhạc của Kadoc thành bản nhạc thế kỉ.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~30 \%~ | ~n \le 10, a_i \le 5~ |
| ~2~ | ~70 \%~ | Không có ràng buộc gì thêm |
Sample Input 1
5 1
2 1 3 4 5
Sample Output 1
2
Sample Input 2
5 2
2 4 5 4 5
Sample Output 2
9
Notes
Trong test ví dụ thứ nhất, cấu hình của bản nhạc thế kỉ là [~1, 2, 3, 4, 5~].
Trong test ví dụ thứ nhất, cấu hình của bản nhạc thế kỉ là [~1, 3, 5, 7, 9~].
Bình luận
bài này có thể dùng bin search cho nhanh nha
SPOIL!!! * * ** CÁCH LÀM CỦA MÌNH LÀ MÌNH DUYỆT TỪ 1 ĐẾN MAX(A[I). Mình cho vào 1 vòng lặp while (i < maxx) , ví dụ khi i = 1, thì mình lưu vào 1 mảng, mình xin được phép gọi là mảng kq, kq[0] = i, sau đó thì cho vòng lặp for duyệt từ 1 đến n - 1 với cú pháp kq[i] = kq[i-1] + k. Sau đó thì chạy 1 vòng lặp for từ 0 đến n - 1, ta tính được: result += abs(kq[i) - A[i]), cập nhật min và tăng i lên. Sau đó thì in ra giá trị min. CODE THAM KHẢO: https://ide.usaco.guide/OPzG59lfi-NQ-8aT3CJ
nên spoil nhé
Cảm ơn bạn
ai hỏi không ông?
Sao bạn nhắn tin thô tục vậy, mình góp ý rất đầy đủ, chi tiết và dễ hiểu mà. Nếu bạn không thích thì đừng xem, ai biểu bạn xem không? Nhà không có người dạy à?
tại tôi nhớ ông cái bài HSG THPT TPHCM 2021 - Tìm đường https://oj.vnoi.info/problem/ hcm _thpt _21 _c
Bạn tên là Nguyễn Trần Hào Việt trường Hồng Bàng Q5 đk?