Tính toán (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B)
Đề bài
Mình gọi một số nguyên dương là số đẹp nếu tổng các chữ số của nó chia hết cho $9$. Ví dụ $9$ (tổng chữ số $9$), $18$ ($1 + 8 = 9$), $2007$ ($2 + 0 + 0 + 7 = 9$) đều là số đẹp, còn $20$ ($2 + 0 = 2$) thì không.
Cho số nguyên dương $n$. Hãy tính tổng của tất cả các số đẹp không vượt quá $n$.
Dữ liệu vào: một dòng chứa số nguyên dương $n$ $(n \le 10^9)$.
Kết quả: một dòng chứa một số nguyên là tổng tính được.
Subtask:
- Subtask 1 (80% số test): $n \le 10^6$.
- Subtask 2 (20% số test): không có ràng buộc gì thêm.
Giới hạn thời gian: 0,1 giây (rất chặt!), bộ nhớ: 1 GB. Dữ liệu nhập từ bàn phím và in ra màn hình.
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B. Đề được mình viết lại cho dễ đọc.
2027Giải thích: các số đẹp không vượt quá $20$ là $9$ và $18$, tổng bằng $9 + 18 = 27$.
Lời mở đầu
Bài mở màn của vòng loại đợt 1 bảng B: đề rất ngắn, cách "trâu" thì ai cũng nghĩ ra ngay – duyệt từng số, tính tổng chữ số. Nhưng giới hạn thời gian chỉ 0,1 giây và $n$ lên tới $10^9$ nên muốn trọn điểm thì phải nhìn ra một tính chất quen thuộc từ lớp 6: dấu hiệu chia hết cho 9. Mình sẽ đi 3 bước: duyệt trâu (ăn subtask 1) → chỉ duyệt các bội của 9 → công thức tính ngay.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE gồm 20 test (mình tự sinh theo đúng ràng buộc của đề), mỗi test chỉ là một số $n$. Test 1 là ví dụ của đề; test 1–16 thoả $n \le 10^6$ (subtask 1), test 17–20 có $n$ tới $10^9$ (subtask 2). Lời giải cuối cùng (cách 3) mình đã nộp thử trên bộ chấm chính thức của tinhoctre.vn và được 100 điểm.
| Nhóm | Test | $n$ nhỏ nhất | $n$ lớn nhất | Đáp án lớn nhất | Số test $n < 9$ (đáp án 0) |
|---|---|---|---|---|---|
| Subtask 1 | 1–16 | 1 | 1.000.000 | 55.555.944.444 | 2 |
| Subtask 2 | 17–20 | 187.063.046 | 1.000.000.000 | 55.555.555.944.444.444 | 0 |
- Có các test biên nhỏ: $n = 1$, $n = 8$ (chưa có số đẹp nào → in $0$), $n = 9, 10, 17, 18$ (ngay sát các bội của 9).
- Đáp án lớn nhất khoảng $5{,}6 \cdot 10^{16}$ – vượt xa kiểu
intnên phải dùnglong long.
Kết quả chạy thật của các cách bên dưới theo từng subtask (thời gian CPU, giới hạn 0,1s):
| Subtask | Điều kiện | Test | Cách 1 C++ | Cách 2 C++ | Cách 2 Python | Cách 3 C++ / Python |
|---|---|---|---|---|---|---|
| Subtask 1 (80%) | $n \le 10^6$ | 1–16 | 16/16 | 16/16 | 16/16 | 16/16 |
| Subtask 2 (20%) | không có ràng buộc gì thêm ($n \le 10^9$) | 17–20 | 0/4 | 4/4 | 0/4 | 4/4 |
Ý tưởngSố đẹp chính là bội của 9
Viết số $v$ dưới dạng các chữ số $v = \overline{c_k \dots c_1 c_0}$ $= c_k \cdot 10^k + \dots + c_1 \cdot 10 + c_0$. Vì $10 = 9 + 1$ nên $10^i$ chia 9 luôn dư 1, do đó
$$v \equiv c_k + \dots + c_1 + c_0 \pmod 9.$$
Em nhập $n$ rồi bấm Tiếp để xem từng số được kiểm tra: số nhỏ phía trên mỗi ô là tổng chữ số, ô xanh là số đẹp – để ý chúng cách đều nhau đúng 9 đơn vị:
Cách 1Duyệt từng số, tính tổng chữ số – O(n log n)
Làm đúng như đề nói: với mỗi $v$ từ $1$ đến $n$, tách từng chữ số bằng % 10 và / 10, cộng lại; nếu tổng chia hết cho 9 thì cộng $v$ vào đáp án.
- Vòng
while(t > 0)lấy chữ số cuốit % 10rồi bỏ nó đi bằngt /= 10– mỗi số tốn khoảng 7–10 vòng. ansphải làlong long: với $n = 10^6$ tổng đã khoảng $5{,}6 \cdot 10^{10}$.
Kết quả chạy thật: bản C++ đúng 16/20 test, quá thời gian test 17–20 (các test đúng chạy lâu nhất 0.009s). Toàn bộ subtask 1 qua, 4 test của subtask 2 ($n$ cỡ $10^9$, gần $10^{10}$ phép tính) bị quá thời gian. Bản Python đúng 8/20 test, quá thời gian test 8–11, 13–20 (các test đúng chạy lâu nhất 0.082s) – Python chậm hơn C++ khoảng 50 lần nên với giới hạn 0,1s chỉ qua được các test $n$ nhỏ.
Cách 2Chỉ duyệt các bội của 9 – O(n/9)
Nhờ nhận xét ở trên, ta không cần tính tổng chữ số nữa: chỉ cần cộng các số $9, 18, 27, \dots$ không vượt quá $n$. Số vòng lặp giảm còn $n / 9 \approx 1{,}1 \cdot 10^8$ khi $n = 10^9$.
Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.066s. Qua hết nhưng test lớn nhất mất cỡ 0,066s – sát giới hạn 0,1s, máy chấm chậm hơn một chút là có thể bị quá giờ. Bản Python đúng 16/20 test, quá thời gian test 17–20 (các test đúng chạy lâu nhất 0.035s): $10^8$ vòng lặp là quá sức với Python.
Cách 3Công thức cấp số cộng – O(1)
Đặt $k = \lfloor n / 9 \rfloor$ là số bội của 9 không vượt quá $n$. Tổng cần tính là
$$9 + 18 + \dots + 9k = 9 \cdot (1 + 2 + \dots + k) = 9 \cdot \frac{k(k+1)}{2}.$$
Thử với ví dụ: $n = 20$ → $k = 2$ → $9 \cdot \frac{2 \cdot 3}{2} = 27$ ✔.
- Tính
k * (k + 1) / 2trước rồi mới nhân 9: $k(k+1)$ luôn chẵn nên phép chia 2 không bị làm tròn, và kết quả trung gian nhỏ hơn. - Với $n = 10^9$: $k = 111\,111\,111$, $k(k+1) \approx 1{,}2 \cdot 10^{16}$ vẫn vừa
long long(giới hạn khoảng $9{,}2 \cdot 10^{18}$).
Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.023s. Full điểm, và đây cũng là lời giải mình đã nộp trên tinhoctre.vn (100 điểm).
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Duyệt từng số, tính tổng chữ số | C++ | 16/20 | 0.009s | quá giờ 17–20 – ăn subtask 1 |
| Python | 8/20 | 0.082s | quá giờ 8–11, 13–20 | |
| 2. Chỉ duyệt bội của 9 | C++ | 20/20 | 0.066s | Đúng hết – sát giới hạn 0,1s |
| Python | 16/20 | 0.035s | quá giờ 17–20 | |
| 3. Công thức $O(1)$ | C++ | 20/20 | 0.003s | Đúng hết |
| Python | 20/20 | 0.023s | Đúng hết |
Nhận xét
Đăng nhận xét