Số đặc biệt (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C2)
Đề bài
Số quá bán của số tự nhiên $X$ là số $a$ nhỏ nhất sao cho $a \times 2 \ge X$. Ví dụ: số quá bán của $4$ là $2$, của $9$ là $5$.
Số cấp dưới của số tự nhiên $X$ là số $b$ lớn nhất sao cho $b \times b < X$. Ví dụ: số cấp dưới của $4$ là $1$, của $5$ là $2$.
Cho hai số tự nhiên $N$ và $M$. Gọi $u$ là tổng các số quá bán của mọi số tự nhiên nhỏ hơn $N$, còn $v$ là tổng các số cấp dưới của mọi số tự nhiên nhỏ hơn $M$.
Yêu cầu: tính $u + v$.
Dữ liệu vào:
- Dòng thứ nhất: số tự nhiên $N$ ($N \le 10^8$).
- Dòng thứ hai: số tự nhiên $M$ ($M \le 10^8$).
Kết quả: một số tự nhiên duy nhất là $u + v$.
Subtask:
- Subtask 1 (30%): $10 \le N, M \le 1000$;
- Subtask 2 (20%): $N = 1$;
- Subtask 3 (20%): $M = 1$;
- Subtask 4 (30%): 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.
5
611Giải thích: các số tự nhiên nhỏ hơn $N = 5$ là $0, 1, 2, 3, 4$ với số quá bán lần lượt $0, 1, 1, 2, 2$ nên $u = 6$. Các số tự nhiên nhỏ hơn $M = 6$ là $0, 1, \dots, 5$; số $0$ không có số cấp dưới (không có $b$ nào để $b^2 < 0$), các số $1, 2, 3, 4, 5$ có số cấp dưới $0, 1, 1, 1, 2$ nên $v = 5$. Kết quả $6 + 5 = 11$.
- Số 0 không có số cấp dưới (không có $b$ nào thoả $b \cdot b < 0$) – ví dụ của đề cho thấy ta tính nó bằng $0$. Số quá bán của $0$ là $0$.
- Đề gốc ghi nhầm "Dòng thứ nhất" cho cả hai dòng dữ liệu; thực ra $N$ ở dòng thứ nhất, $M$ ở dòng thứ hai. Đáp án lớn nhất cỡ $2{,}5 \cdot 10^{15}$ nên phải dùng
long long.
Lời mở đầu
Bài nhẹ nhàng của Bảng C2 vòng khu vực: hai định nghĩa nghe hơi "lạ tai" nhưng thực chất là làm tròn lên của $X/2$ và căn bậc hai nguyên. Mình đi 3 bước: làm đúng định nghĩa (vòng while) → dùng công thức cho từng số $O(N + M)$ → gom nhóm để ra công thức tổng, chạy tức thì.
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. Test 1 là ví dụ của đề ($N = 5$, $M = 6$) – không thoả điều kiện $10 \le N, M$ của Subtask 1 nên mình xếp nó vào nhóm "không ràng buộc".
| Nhóm | Test | $N$ nhỏ nhất – lớn nhất | $M$ nhỏ nhất – lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|
| Subtask 1 | 2–7 | 10 – 1.000 | 10 – 1.000 | 270.553 |
| Subtask 2 | 8–11 | 1 – 1 | 1 – 100.000.000 | 666.616.655.001 |
| Subtask 3 | 12–15 | 2 – 100.000.000 | 1 – 1 | 2.500.000.000.000.000 |
| Subtask 4 | 1, 16–20 | 3 – 100.000.000 | 2 – 100.000.000 | 2.500.666.616.655.001 |
- Subtask 2 và 3 có các test biên $N = 1$ / $M = 1$ (một tổng bằng 0) và các test $10^8$ ở tổng còn lại; có cả giá trị $M = 99\,980\,001 = 9999^2$ (đúng một số chính phương) để bắt lỗi lệch 1 ở khúc cuối.
- Đáp án lớn nhất là $2\,500\,666\,616\,655\,001$ – vượt xa giới hạn
int.
Kết quả chạy thật các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python | Cách 3 C++ | Cách 3 Python |
|---|---|---|---|---|---|---|---|---|
| Subtask 1 (30%) | $10 \le N, M \le 1000$ | 2–7 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 |
| Subtask 2 (20%) | $N = 1$ | 8–11 | 1/4 | 1/4 | 4/4 | 1/4 | 4/4 | 4/4 |
| Subtask 3 (20%) | $M = 1$ | 12–15 | 4/4 | 1/4 | 4/4 | 1/4 | 4/4 | 4/4 |
| Subtask 4 (30%) | không ràng buộc thêm | 1, 16–20 | 2/6 | 2/6 | 6/6 | 2/6 | 6/6 | 6/6 |
Ý tưởngHai định nghĩa thật ra là gì?
Số quá bán. $a$ nhỏ nhất mà $2a \ge X$ chính là $\lceil X/2 \rceil$, trong C++ viết (X + 1) / 2. Các số $X = 1, 2, 3, 4, 5, 6, \dots$ có số quá bán $1, 1, 2, 2, 3, 3, \dots$ – mỗi giá trị lặp đúng 2 lần.
Số cấp dưới. $b$ lớn nhất mà $b^2 < X$, tức là $b^2 \le X - 1$, chính là căn bậc hai nguyên của $X - 1$: $b = \lfloor \sqrt{X - 1} \rfloor$. Giá trị $b$ giữ nguyên trên cả một khúc: với $X$ từ $b^2 + 1$ tới $(b+1)^2$ – khúc này dài $2b + 1$ số.
Em nhập $N$, $M$ rồi bấm Tiếp để xem các số được gom thành từng khúc (mỗi màu là một khúc cùng giá trị):
Cách 1Làm đúng định nghĩa (Subtask 1)
Với mỗi $X$, tăng dần $a$ từ 0 tới khi $2a \ge X$; tăng dần $b$ chừng nào $(b+1)^2 < X$ vẫn đúng. Code này bám sát định nghĩa nên rất khó sai – dùng làm "trọng tài" để kiểm tra các cách sau.
- Vòng
while(a * 2 < X)dừng ở $a$ nhỏ nhất có $2a \ge X$ – đúng định nghĩa số quá bán. - Vòng
while((b + 1) * (b + 1) < X)chỉ tăng $b$ khi số kế tiếp vẫn còn bình phương nhỏ hơn $X$, nên khi dừng $b$ là số lớn nhất có $b^2 < X$. Vòng thứ hai bắt đầu từ $X = 1$ vì số $0$ không có số cấp dưới.
Kết quả chạy thật: Bản C++ đúng 13/20 test, quá thời gian test 9–11, 16–18, 20 (các test đúng chạy lâu nhất 0.065s). Bản Python đúng 10/20 test, quá thời gian test 9–12, 14–18, 20 (các test đúng chạy lâu nhất 0.051s).
while(a * 2 < X) a++; bắt đầu từ $a = 0$ quá đơn giản nên trình biên dịch (với -O2) tự thay nó bằng công thức tính thẳng $a$, vì vậy phần tính $u$ chạy như $O(N)$ và bản C++ qua cả các test $M = 1$, $N = 10^8$. Vòng của $v$ thì không được tối ưu như vậy, nên khi $M$ lớn (Subtask 2, 4) vẫn quá thời gian. Bản Python không có "phép màu" này nên chỉ qua Subtask 1 và vài test rất nhỏ. Đừng trông chờ vào trình biên dịch – cứ tự tìm công thức như các cách dưới.Cách 2Công thức cho từng số – O(N + M)
Số quá bán là (X + 1) / 2, tính $O(1)$. Số cấp dưới thì không giảm khi $X$ tăng, nên giữ $b$ từ số trước và chỉ tăng thêm khi cần – giống hai con trỏ: tổng số lần b++ trên cả vòng lặp chỉ khoảng $\sqrt{M}$.
- Biến
bđược khai báo ngoài vòng lặp – đây là khác biệt duy nhất so với cách 1 nhưng biến $O(M\sqrt{M})$ thành $O(M)$. - Không dùng
sqrtsố thực để tránh sai số làm tròn ở các số chính phương lớn.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.147s. Bản Python đúng 10/20 test, quá thời gian test 9–12, 14–18, 20 (các test đúng chạy lâu nhất 0.024s) – $2 \cdot 10^8$ vòng lặp là quá sức Python trong 1 giây.
Cách 3Gom khúc thành công thức tổng (full)
Tính $u$. Đặt $K = N - 1$ (số lớn nhất được cộng). Các số quá bán của $1..K$ là $1, 1, 2, 2, \dots$:
- Nếu $K = 2p$: $u = 2(1 + 2 + \dots + p)$ $= p(p + 1)$.
- Nếu $K = 2p + 1$: thêm một số $p + 1$ nữa, $u = p(p + 1) + (p + 1) = (p + 1)^2$.
Tính $v$. Đặt $Y = X - 1$ thì $v$ là tổng $\lfloor\sqrt{Y}\rfloor$ với $Y = 0, 1, \dots, R$ ($R = M - 2$). Với mỗi $b \ge 1$, các $Y$ có $\lfloor\sqrt{Y}\rfloor = b$ là đoạn $[b^2, (b+1)^2 - 1]$ (khúc cuối bị cắt ở $R$), nên đóng góp $b \times$ (độ dài đoạn). Khúc $b = 0$ đóng góp 0 nên bỏ qua.
- Khi $N = 1$: $K = 0$, $p = 0$, $u = 0$ ✓. Khi $M = 1$ hoặc $M = 2$: $R < 1$ nên vòng lặp không chạy, $v = 0$ ✓.
- Thử với ví dụ: $K = 4 = 2 \cdot 2$ → $u = 2 \cdot 3 = 6$; $R = 4$: $b = 1$ ứng với $Y \in [1, 3]$ đóng góp $3$, $b = 2$ ứng với $Y \in [4, 4]$ đóng góp $2$ → $v = 5$. Tổng $11$ ✓.
- Muốn $O(1)$ hoàn toàn cũng được (dùng công thức $\sum b(2b+1)$), nhưng $10^4$ vòng lặp đã là tức thì nên mình giữ cho dễ hiểu.
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.022s. Full điểm cả hai ngôn ngữ.
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. Đúng định nghĩa (vòng while) | C++ | 13/20 | 0.065s | 50% |
| Python | 10/20 | 0.051s | 30% | |
| 2. Công thức cho từng số – $O(N + M)$ | C++ | 20/20 | 0.147s | 100% |
| Python | 10/20 | 0.024s | 30% | |
| 3. Công thức tổng – $O(\sqrt{M})$ | C++ | 20/20 | 0.003s | 100% |
| Python | 20/20 | 0.022s | 100% |
Nhận xét
Đăng nhận xét