Số đặc biệt (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C2)

Nguồn: Tin học trẻ 2024 Độ khó: Dễ Toán Công thức tổng Căn bậc hai nguyên

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C2 (bài Số đặc biệt). Đề vòng khu vực dùng chung cho cả ba miền Bắc, Trung, Nam; bài này nằm trong đề Bảng C2 của miền Trung và miền Nam. Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

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.

Ví dụ – input

5
6

Ví dụ – output

11

Giả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$.

Hai chỗ cần để ý

• 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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởnggom khúcCách 1định nghĩaCách 2O(N + M)Cách 3công thức – 100đ

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.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 3) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

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ố.

Nhận xét

Vì các giá trị lặp lại theo từng "khúc" có độ dài biết trước, ta không cần cộng từng số: gom cả khúc rồi nhân. Với $u$ còn ra hẳn công thức đóng; với $v$ chỉ có khoảng $\sqrt{M} \le 10^4$ khúc.

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ị):

N = M =

Ví dụ nhanh:

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.

C++▶ Chạy tay từng dòng codeCách 1: tính đúng theo định nghĩa bằng hai vòng while.

Dữ liệu vào (stdin) – sửa thoải mái5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng while(a * 2 < X) dừng ở $a$ nhỏ nhất có $2a \ge X$ – đúng định nghĩa số quá bán.
2. 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.

Không gian$O(1)$

Thời gian$O(N^2 + M\sqrt{M})$

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).

Chuyện lạ: C++ "ăn" luôn Subtask 3

Vòng 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}$.

C++▶ Chạy tay từng dòng codeCách 2: công thức (X+1)/2 và giữ b tăng dần, O(N + M).

Dữ liệu vào (stdin) – sửa thoải mái5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. 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)$.
2. Không dùng sqrt số thực để tránh sai số làm tròn ở các số chính phương lớn.

Không gian$O(1)$

Thời gian$O(N + M)$

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.

C++▶ Chạy tay từng dòng codeCách 3: công thức đóng cho u, đếm theo khúc cho v.

Dữ liệu vào (stdin) – sửa thoải mái5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. 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$ ✓.
2. 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$ ✓.
3. 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.

Không gian$O(1)$

Thời gian$O(\sqrt{M})$

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%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Bài học của bài này: khi một đại lượng là hàm "bậc thang" (giữ nguyên trên từng khúc) như $\lceil X/2 \rceil$, $\lfloor\sqrt{X}\rfloor$, $\lfloor N/X \rfloor$..., hãy đếm theo khúc thay vì theo từng số. Và đừng quên đọc kỹ ví dụ để biết trường hợp đặc biệt (số 0) được tính thế nào.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇