PHẦN 1: BẢNG ĐÁNH GIÁ ĐỘ KHÓ TỔNG QUAN (THANG ĐIỂM 1★ ĐẾN 10★)
Đề thi gồm 4 câu tự luận lập trình thực hiện trong thời gian 150 phút. Hệ thống chấm điểm tự động qua phần mềm Themis với cơ cấu điểm số chia đều 5.0 điểm cho mỗi bài toán (Tổng điểm toàn bài: 20.0 điểm).
| STT | Câu hỏi | Tên Bài (Mã bài) | Trọng số | Độ khó (1-10★) | Đánh giá tổng quan |
|---|---|---|---|---|---|
| 1 | Câu 1 | Số phong phú (PNT) | 5.0 điểm | ★★☆☆☆☆☆☆☆☆ | Bài toán Số học cơ bản về tìm ước số. Dễ dàng ăn điểm tối đa nếu biết cách tối ưu vòng lặp căn bậc hai $\sqrt{X}$. |
| 2 | Câu 2 | Ký tự số (KTS) | 5.0 điểm | ★★★★☆☆☆☆☆☆ | Bài toán Xử lý chuỗi ký tự kết hợp sàng lọc số. Thách thức nằm ở việc bẫy dữ liệu số siêu lớn vượt quá giới hạn lưu trữ kiểu số thông thường. |
| 3 | Câu 3 | Dãy số (DS) | 5.0 điểm | ★★★★★★☆☆☆☆ | Bài toán tối ưu hóa trên mảng một chiều. Đòi hỏi kỹ thuật Hai con trỏ (Two Pointers) hoặc Tìm kiếm nhị phân để vượt qua toàn bộ các test dữ liệu lớn. |
| 4 | Câu 4 | Đèn nháy (DN) | 5.0 điểm | ★★★★★★★★☆☆ | Bài toán chốt hạ tư duy toán học thuần túy kết hợp Tin học. Giới hạn cực lớn $N \le 10^{18}$ bắt buộc phải tìm ra quy luật Số chính phương để giải trong $O(1)$. |
PHẦN 2: MA TRẬN KIẾN THỨC VÀ TIÊU CHÍ ĐẠT ĐIỂM CHI TIẾT
Câu 1: SỐ PHONG PHÚ (PNT) - 5.0 Điểm
- Mô tả bài toán: Đếm số lượng "số phong phú" trong đoạn $[L, R]$. Một số được gọi là số phong phú nếu tổng các ước dương của nó (không kể chính nó) lớn hơn chính nó.
- Giới hạn: $1 \le L \le R \le 10^5$.
| Mức điểm đạt được | Phân loại Subtask | Độ khó | Kiến thức & Giải thuật cần áp dụng | Độ phức tạp |
|---|---|---|---|---|
| 3.0 - 4.0 điểm | Subtask 1 (Duyệt trâu) | ★☆☆☆☆ | Duyệt qua từng số $X$ trong đoạn $[L, R]$. Với mỗi số, dùng vòng lặp chạy từ $1$ đến $X-1$ để cộng dồn các ước số dương. | $O((R-L) \times X)$ |
| 5.0 điểm | Subtask 2 (Tối ưu) | ★★☆☆☆ | Cải tiến 1: Áp dụng duyệt ước đến $\sqrt{X}$ để tìm cặp ước $(i, X/i)$. Cải tiến 2 (Tối ưu nhất): Sử dụng thuật toán tương tự Sàng số nguyên tố (Sàng tổng ước) để tính trước tổng ước của tất cả các số tới $10^5$ trước khi truy vấn đoạn. |
$O(R \log R)$ |
Câu 2: KÝ TỰ SỐ (KTS) - 5.0 Điểm
- Mô tả bài toán: Cho xâu ký tự $S$. Hãy tìm và in ra số nguyên lớn nhất được tạo thành từ các ký tự số liên tiếp nhau nằm trong xâu $S$.
- Giới hạn: Độ dài xâu $|S| \le 10^5$.
| Mức điểm đạt được | Phân loại Subtask | Độ khó | Kiến thức & Giải thuật cần áp dụng | Độ phức tạp |
|---|---|---|---|---|
| 2.5 - 3.5 điểm | Subtask 1 (Số nhỏ) | ★★★☆☆ | Duyệt qua xâu, tách chuỗi ký tự số liên tiếp, ép kiểu (Cast type) sang dạng số nguyên lớn (long long trong C++ hoặc int trong Python) để so sánh bằng hàm max(). Bẫy: Bị tràn số (Overflow) nếu độ dài dãy chữ số $> 18$ ký tự. |
$O( |
| 5.0 điểm | Subtask 2 (Số lớn) | ★★★★☆☆ | So sánh số lớn bằng Xâu (String Matching): Trích xuất các cụm số lưu vào mảng xâu (string), thực hiện chuẩn hóa xóa các chữ số '0' vô nghĩa ở đầu cụm số. Xây dựng hàm so sánh hai xâu số lớn: Cụm nào dài hơn thì lớn hơn; nếu dài bằng nhau thì so sánh theo thứ tự từ điển chuẩn. |
$O( |
Câu 3: DÃY SỐ (DS) - 5.0 Điểm
- Mô tả bài toán: Cho dãy gồm $N$ số nguyên dương $A_1, A_2, ..., A_N$ và một số nguyên dương $K$. Hãy tìm một dãy con gồm các phần tử liên tiếp dài nhất sao cho tổng các phần tử của dãy con đó không vượt quá $K$.
- Giới hạn: $N \le 10^5, K \le 10^{18}$.
| Mức điểm đạt được | Phân loại Subtask | Độ khó | Kiến thức & Giải thuật cần áp dụng | Độ phức tạp |
|---|---|---|---|---|
| 2.0 điểm | Subtask 1 | ★★★☆☆ | Vét cạn (Brute Force): Sử dụng 2 vòng lặp lồng nhau cố định chỉ số đầu $i$ và chỉ số cuối $j$ để kiểm tra tổng mọi đoạn con liên tiếp $[i, j]$. Chỉ ăn được các test có $N \le 10^3$. | $O(N^2)$ |
| 3.5 điểm | Subtask 2 | ★★★★☆☆ | Mảng tiền tố + Tìm kiếm nhị phân: Tạo mảng cộng dồn $PrefixSum$ với $P[i] = P[i-1] + A_i$. Vì mảng gồm các số nguyên dương nên mảng $P$ tăng nghiêm ngặt. Với mỗi vị trí $i$, dùng std::upper_bound trên mảng $P$ để tìm kiếm nhị phân vị trí kết thúc $j$ xa nhất thỏa mãn $P[j] - P[i-1] \le K$. |
$O(N \log N)$ |
| 5.0 điểm | Subtask 3 | ★★★★★★ | Kỹ thuật Hai con trỏ (Two Pointers / Sliding Window): Duy trì hai con trỏ trượt $L$ và $R$ cùng dịch chuyển từ trái sang phải. Mở rộng biên phải $R$ để tăng tổng; khi tổng vượt quá $K$, thực hiện co biên trái $L$ cho đến khi tổng hợp lệ. Cập nhật độ dài lớn nhất liên tục. | $O(N)$ |
Câu 4: ĐÈN NHÁY (DN) - 5.0 Điểm
- Mô tả bài toán: Có $N$ bóng đèn ban đầu đều tắt. Lần thứ $i$ thực hiện đảo trạng thái (bật $\leftrightarrow$ tắt) của các bóng đèn có số thứ tự chia hết cho $i$. Yêu cầu đếm số lượng bóng đèn đang bật trong đoạn từ vị trí $p$ đến vị trí $q$ sau $N$ lần thực hiện quy tắc trên.
- Giới hạn dữ liệu: $1 \le p < q \le N \le 10^{18}$.
| Mức điểm đạt được | Phân loại Subtask | Độ khó | Kiến thức & Giải thuật cần áp dụng | Độ phức tạp |
|---|---|---|---|---|
| 1.0 - 2.0 điểm | Subtask 1 | ★★★★☆☆ | Mô phỏng trâu: Sử dụng một mảng kiểu Logic (bool) kích thước $N$ phần tử để bật/tắt thủ công theo từng bước của đề bài. Chỉ chạy được với dữ liệu rất nhỏ $N \le 10^6$ do giới hạn bộ nhớ và thời gian 1s. |
$O(N \log N)$ |
| 3.0 điểm | Subtask 2 | ★★★★★★ | Nhận xét Toán học sơ cấp: Một bóng đèn tại vị trí $X$ thay đổi trạng thái phụ thuộc vào số lượng ước số của $X$. Đèn sẽ ở trạng thái BẬT cuối cùng nếu và chỉ nếu nó có số lượng ước là số lẻ $\rightarrow$ $X$ bắt buộc phải là Số chính phương. Duyệt trâu từ $p$ đến $q$, kiểm tra xem số nào là số chính phương thì tăng biến đếm. | $O(q - p)$ |
| 5.0 điểm | Subtask 3 | ★★★★★★★★ | Công thức Toán tối ưu toán học: Quy bài toán về việc đếm số lượng số chính phương trong đoạn $[p, q]$. Số lượng số chính phương từ $1$ đến $X$ luôn bằng $\lfloor\sqrt{X}\rfloor$. Do đó kết quả đoạn $[p, q]$ tính nhanh bằng công thức: $$\text{Result} = \lfloor\sqrt{q}\rfloor - \lfloor\sqrt{p - 1}\rfloor$$ Lưu ý kĩ thuật: Cần dùng kiểu dữ liệu unsigned long long hoặc __int128 (C++) kết hợp hàm căn bậc hai cẩn thận để tránh sai số dấu phẩy động ở các số lớn tiệm cận $10^{18}$. |
$O(1)$ |
PHẦN 3: ĐÁNH GIÁ CHUNG VÀ CHIẾN THUẬT LÀM BÀI ĐẠT ĐIỂM CAO
- Cấu trúc đề thi: Đề thi phân loại học sinh rất tốt nhờ phân bổ phổ điểm đều nhưng mức độ tư duy thuật toán nâng cao tăng dần qua từng câu. Cấu trúc gồm cả Số học, Thuật toán mảng tối ưu, và Xử lý chuỗi lớn.
- Chiến thuật tối ưu phòng thi:
- Mức điểm 10 - 12 (Đạt điểm điều kiện/Khá): Ăn trọn vẹn điểm Câu 1 (bằng vòng lặp căn bậc hai), xử lý tách chuỗi cơ bản ở Câu 2, viết thuật toán vét cạn trâu cho Câu 3 và Câu 4 để lấy các điểm số ở subtask đầu.
- Mức điểm 16 - 20 (Tranh chấp giải cao/Thủ khoa): Bắt buộc phải cài đặt thành thạo kỹ thuật Hai con trỏ tối ưu tuyến tính ở Câu 3 để không bị quá thời gian (TLE). Ở Câu 4, không được phép dùng bất kỳ vòng lặp nào mà phải dùng tư duy toán để đưa về công thức khai căn $O(1)$ xử lý số lớn.