SQRT Cup 2025 - Vòng loại thứ nhất - Chia hết cho 9
Xem dạng PDF
Gửi bài giải
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig
Điểm:
1900 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
DIV.inp
Output:
DIV.out
Dạng bài
Ngôn ngữ cho phép
Huy có một dãy số ~a_1, a_2, ..., a_n~. Huy có thể thực hiện ~k~ lần biến đổi, mỗi lần Huy có thể thay đổi một chữ số trong dãy. Huy muốn tổng các số chia hết cho ~9~ trong dãy là lớn nhất có thể. Bạn hãy tìm cách để Huy có thể biến đổi dãy số thỏa mãn yêu cầu. Lưu ý rằng sau khi biến đổi có thể có một hoặc nhiều số bắt đầu bằng chữ số ~0~.
Dữ liệu - Nhập từ tệp văn bản DIV.inp:
- Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le n \le 2000, 0 \le k \le 10000)~.
- Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.
Kết quả - Ghi ra tệp văn bản DIV.out:
- Một dòng duy nhất gồm tổng các số chia hết cho ~9~ trong dãy sau khi biến đổi.
Chấm điểm
| Điểm | Ràng buộc bổ sung |
|---|---|
| ~11~ | ~k = 0~ |
| ~14~ | ~k \le 1~ |
| ~22~ | ~n = 1~ |
| ~25~ | ~k \le 2~ |
| ~28~ | Không có ràng buộc gì thêm |
Ví dụ
Dữ liệu (DIV.inp)
4 2
28 4 20 7
Kết quả (DIV.out)
117
Giải thích
Huy có thể thay đổi chữ số cuối cùng của phần tử đầu tiên thành chữ số ~7~, sau đó thay đổi chữ số đầu tiên của phần từ thứ ba thành chữ số ~9~ để được tổng ~27 + 90 = 117~. Có thể thấy đây là tổng lớn nhất có thể tạo được.
Bình luận