Tính toán (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng B, C2)
Đề bài
Alice muốn làm đồ chơi tặng các bạn nhỏ trong $n$ ngày. Ở ngày thứ $t$ ($1 \le t \le n$) Alice làm được:
- $t$ đồ chơi loại 1;
- $\lceil \sqrt{t}\, \rceil$ đồ chơi loại 2 (căn bậc hai của $t$, làm tròn lên);
- $\lfloor \sqrt[3]{t}\, \rfloor$ đồ chơi loại 3 (căn bậc ba của $t$, làm tròn xuống).
Trong đó $\lceil x \rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$, còn $\lfloor x \rfloor$ là số nguyên lớn nhất không vượt quá $x$.
Yêu cầu: cho $n$, hãy tính tổng số đồ chơi (cả ba loại) mà Alice làm được trong $n$ ngày.
Dữ liệu vào: một dòng chứa số nguyên dương $n$ ($n \le 2 \cdot 10^{12}$).
Kết quả: một dòng chứa tổng số đồ chơi.
Subtask:
- Subtask 1 (50% số điểm): $n \le 2 \cdot 10^3$;
- Subtask 2 (40% số điểm): $n \le 2 \cdot 10^9$;
- Subtask 3 (10% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
28Giải thích (mình viết thêm, đề gốc không có): ngày 1 làm $1 + \lceil\sqrt 1\rceil$ $+ \lfloor\sqrt[3]1\rfloor$ $= 1 + 1 + 1$ $= 3$ đồ chơi; ngày 2 làm $2 + \lceil\sqrt 2\rceil$ $+ \lfloor\sqrt[3]2\rfloor$ $= 2 + 2 + 1$ $= 5$ đồ chơi. Tổng cộng $3 + 5 = 8$.
Lời mở đầu
Bài mở màn của đề khu vực miền Nam. Đọc đề thấy "dễ quá, cứ cộng từng ngày là xong" – và đúng là cách đó ăn ngay 50% số điểm. Nhưng để lấy trọn điểm, em phải vượt qua hai "cửa ải": $n$ tới $2 \cdot 10^{12}$ (không thể lặp từng ngày) và đáp án tới khoảng $2 \cdot 10^{24}$ (tràn cả long long). Mình sẽ đi qua ba cách, mỗi cách mở khoá thêm một subtask.
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 do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 20 test, mỗi test chỉ một số $n$ (test 1 là ví dụ của đề; có các test biên $n = 1$, $n$ là số chính phương / lập phương, và $n$ đạt đúng giới hạn của từng subtask).
| Nhóm | Test | $n$ nhỏ nhất | $n$ lớn nhất | Đáp án lớn nhất | Số chữ số | Số test đáp án vượt long long |
|---|---|---|---|---|---|---|
| Subtask 1 | 1–10 | 1 | 2.000 | 2.079.558 | 7 | 0 |
| Subtask 2 | 11–18 | 1.000.000.000 | 2.000.000.000 | $\approx 2{,}000 \cdot 10^{18}$ | 19 | 0 |
| Subtask 3 | 19–20 | 1.999.998.409.369 | 2.000.000.000.000 | $\approx 2{,}000 \cdot 10^{24}$ | 25 | 2 |
Hai cột cuối là điểm mấu chốt: chỉ 2 test của subtask 3 có đáp án lớn hơn $2^{63} - 1 \approx 9{,}22 \cdot 10^{18}$ (giới hạn của long long), còn subtask 2 thì đáp án lớn nhất cỡ $2 \cdot 10^{18}$ – vẫn vừa, nhưng sát nút!
Kết quả chạy thật các cách bên dưới theo từng subtask (số test đúng / số test):
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 gom nhóm, long long | Cách 3 gom nhóm, __int128 |
|---|---|---|---|---|---|
| Subtask 1 (50%) | $n \le 2 \cdot 10^3$ | 1–10 | 10/10 | 10/10 | 10/10 |
| Subtask 2 (40%) | $n \le 2 \cdot 10^9$ | 11–18 | 0/8 | 8/8 | 8/8 |
| Subtask 3 (10%) | $n \le 2 \cdot 10^{12}$ | 19–20 | 0/2 | 0/2 | 2/2 |
Ý tưởngBa tổng riêng – và gom các ngày giống nhau thành nhóm
Tổng cần tính tách được thành 3 tổng độc lập:
$$S = \underbrace{\sum_{t=1}^{n} t}_{S_1} + \underbrace{\sum_{t=1}^{n} \lceil \sqrt t\, \rceil}_{S_2} + \underbrace{\sum_{t=1}^{n} \lfloor \sqrt[3] t\, \rfloor}_{S_3}.$$
- $S_1 = 1 + 2 + \dots + n$ $= \dfrac{n(n+1)}{2}$ – công thức quen thuộc.
- $S_2$: giá trị $\lceil\sqrt t\,\rceil$ thay đổi rất chậm. Nó bằng $c$ khi và chỉ khi $(c-1)^2 < t \le c^2$. Ví dụ $\lceil\sqrt t\,\rceil = 3$ với $t = 5, 6, 7, 8, 9$. Vậy thay vì cộng từng ngày, ta cộng theo nhóm: nhóm $c$ gồm các ngày từ $(c-1)^2 + 1$ tới $\min(c^2, n)$, đóng góp $c \times (\text{số ngày trong nhóm})$. Chỉ có khoảng $\sqrt n$ nhóm.
- $S_3$: tương tự, $\lfloor\sqrt[3] t\,\rfloor = c$ khi và chỉ khi $c^3 \le t < (c+1)^3$. Chỉ có khoảng $\sqrt[3] n$ nhóm.
Em nhập $n$ rồi bấm Tiếp để xem các ngày được gom thành nhóm như thế nào (mỗi ô là một ngày, số trong ô là số đồ chơi loại đó):
Với $n = 2 \cdot 10^{12}$: $\sqrt n \approx 1{,}42 \cdot 10^6$ nhóm cho loại 2 và $\sqrt[3] n \approx 12\,600$ nhóm cho loại 3 – máy chạy trong nháy mắt.
Cách 1Vét cạn từng ngày – O(n) (Subtask 1)
Làm đúng như đề nói: với mỗi ngày $t$ tính 3 số rồi cộng vào tổng. Khó khăn duy nhất là tính chính xác $\lceil\sqrt t\,\rceil$ và $\lfloor\sqrt[3] t\,\rfloor$.
sqrt, cbrt trả về số thực nên có thể lệch một chút (ví dụ máy tính ra $\sqrt[3]{64} = 3{,}9999999$, ép kiểu thành 3 thay vì 4). Cách an toàn: lấy giá trị gần đúng rồi chỉnh lại bằng số nguyên – tăng/giảm cho tới khi đúng định nghĩa: $b$ là số nhỏ nhất có $b^2 \ge t$, $c$ là số lớn nhất có $c^3 \le t$.- Hai vòng
whilesausqrtlđảm bảo $(b-1)^2 < t \le b^2$, tức $b = \lceil\sqrt t\,\rceil$ đúng tuyệt đối. Tương tự hai vòng saucbrtlđảm bảo $c^3 \le t < (c+1)^3$. - Thường mỗi vòng
whilechỉ kiểm tra 1–2 lần, nên mỗi ngày tốn $O(1)$, cả chương trình $O(n)$. - Bản Python dùng
math.isqrt(căn bậc hai nguyên, chính xác tuyệt đối) cho loại 2.
Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.004s). Bản Python đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.024s). Đúng như dự đoán: subtask 1 ($n \le 2000$) chạy tức thì, nhưng từ subtask 2 thì $n$ tới $2 \cdot 10^9$ vòng lặp – quá 1 giây (mình cho chạy tối đa ~4 giây vẫn chưa xong) → 50 điểm.
Cách 2Gom nhóm – O(√n) với long long (Subtask 1, 2)
Áp dụng ý tưởng ở trên: $S_1$ dùng công thức, $S_2$ và $S_3$ duyệt theo nhóm $c$.
- Vòng loại 2 chạy khi $(c-1)^2 < n$, tức là nhóm $c$ còn ít nhất một ngày $\le n$. Nhóm cuối có thể bị "cắt" bởi $n$ nên
hi = min(n, c * c). - Vòng loại 3 chạy khi $c^3 \le n$; nhóm cuối cũng bị cắt bởi
hi = min(n, (c+1)^3 - 1). - Thử với $n = 2$: $S_1 = 3$; loại 2: nhóm $c = 1$ là $[1, 1]$ đóng góp 1, nhóm $c = 2$ là $[2, \min(2, 4)] = [2, 2]$ đóng góp 2; loại 3: nhóm $c = 1$ là $[1, \min(2, 7)]$ đóng góp $1 \cdot 2 = 2$. Tổng $3 + 3 + 2 = 8$ ✓.
Kết quả chạy thật: Bản C++ đúng 18/20 test, sai test 19–20 (các test đúng chạy lâu nhất 0.003s) → 90 điểm.
long long chỉ chứa được tới $9{,}22 \cdot 10^{18}$. Thậm chí phép nhân n * (n + 1) ($\approx 4 \cdot 10^{24}$) đã tràn trước khi kịp chia 2. Kết quả in ra là một số "rác" (có thể âm). Với $n \le 2 \cdot 10^9$ thì $n(n+1) \approx 4 \cdot 10^{18}$ – vẫn vừa nên subtask 2 không sao.Cách 3Gom nhóm + __int128 – full điểm
GCC có sẵn kiểu số nguyên 128 bit __int128, chứa được tới khoảng $1{,}7 \cdot 10^{38}$ – thừa sức cho $2 \cdot 10^{24}$. Chỉ cần:
- Khai báo tổng là
__int128và ép kiểu trước khi nhân:(__int128)n * (n + 1)(nếu viết(__int128)(n * (n + 1))thì phép nhân vẫn làm trênlong longvà đã tràn rồi mới ép). coutkhông in được__int128, nên tự viết hàmprint128: lấy từng chữ số bằng% 10,/ 10rồi đảo ngược.
- Các biến
c,lo,hivẫn làlong long(tối đa $2 \cdot 10^{12}$, và $c^2$, $c^3$ cũng chỉ cỡ $2 \cdot 10^{12}$), chỉ có phần tích để cộng vào tổng là cần 128 bit. - Python có số nguyên không giới hạn nên bản Python không cần lo tràn số; vòng lặp khoảng $1{,}42 \cdot 10^6$ lần vẫn kịp 1 giây.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.007s. Bản Python đúng 20/20 test, chạy lâu nhất 0.842s. Full đ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 (test đúng) | Điểm theo subtask |
|---|---|---|---|---|
| 1. Vét cạn từng ngày $O(n)$ | C++ | 10/20 | 0.004s | 50% |
| Python | 10/20 | 0.024s | 50% | |
2. Gom nhóm $O(\sqrt n)$, long long | C++ | 18/20 | 0.003s | 90% |
3. Gom nhóm $O(\sqrt n)$, __int128 | C++ | 20/20 | 0.007s | 100% |
| Python | 20/20 | 0.842s | 100% |
__int128 (hoặc Python).
Nhận xét
Đăng nhận xét