PHẦN 1: BẢNG ĐÁNH GIÁ ĐỘ KHÓ ĐỀ THI (THANG ĐIỂM 1★ ĐẾN 5★)

Đề thi gồm có 4 câu với tổng điểm là 20 điểm, thời gian làm bài 150 phút. Cấu trúc điểm tập trung mạnh vào các câu đầu để học sinh dễ ăn điểm điều kiện, nhưng phân loại rất cao ở các subtask cuối của câu 3 và câu 4 nhờ yêu cầu tối ưu thuật toán.

PHẦN 2: CHI TIẾT KIẾN THỨC VÀ TIÊU CHÍ ĐẠT ĐIỂM THEO TỪNG BÀI

CÂU 1: TỔNG NHỎ NHẤT (TONGNN - 6.0 điểm)

• Mô tả bài toán: Cho trước $m = UCLN(A, B)$ và $n = BCNN(A, B)$. Tìm cặp số nguyên dương $(A, B)$ sao cho tổng $A+B$ đạt giá trị nhỏ nhất.
• Yêu cầu kiến thức & Phân bậc điểm số:
• Mức độ 1★ (Ăn khoảng 60% số điểm - Subtask dữ liệu nhỏ $m, n \le 10^6$):
  • Kiến thức: Thuật toán tìm ước chung lớn nhất (UCLN) bằng Euclid, vòng lặp for/while tuyến tính đơn giản.
  • Chi tiết: Đặt $A = m \times x$ và $B = m \times y$ với $UCLN(x, y) = 1$. Ta có mối liên hệ $A \times B = UCLN(A,B) \times BCNN(A,B) \Rightarrow m^2 \times x \times y = m \times n \Rightarrow x \times y = n / m$. Nếu $n$ không chia hết cho $m$, in ra $-1$. Ngược lại, duyệt trâu biến $x$ từ $1$ đến $n/m$ để tìm cặp thỏa mãn điều kiện.
• Mức độ 2★ (Ăn 100% số điểm - Subtask dữ liệu lớn $m, n \le 10^{12}$):
  • Kiến thức: Phân tích thừa số/ước số tối ưu trong phạm vi $O(\sqrt{k})$, kỹ năng sử dụng kiểu dữ liệu số nguyên lớn (long long trong C++, số nguyên lớn tự động trong Python) để tránh tràn số khi nhân/tính tổng.
  • Chi tiết: Chỉ cần chạy vòng lặp duyệt ước $x$ của giá trị $k = n/m$ trong khoảng từ $1$ đến $\sqrt{k}$. Nếu $k \pmod x == 0$ và kiểm tra thấy $UCLN(x, k/x) == 1$, ta tiến hành cập nhật tổng $A+B = m \times (x + k/x)$ để tìm giá trị nhỏ nhất.

CÂU 2: TÁCH MÃ SỐ (TACHMASO - 5.0 điểm)

• Mô tả bài toán: Cho một chuỗi chứa tập hợp liên tục các mã sản phẩm (gồm chữ cái đi kèm chữ số). Hãy tách riêng các phần chữ số đó ra và sắp xếp chúng theo thứ tự tăng dần. Nếu có các số có giá trị bằng nhau, phải giữ nguyên thứ tự xuất hiện của chúng trong xâu ban đầu.
• Yêu cầu kiến thức & Phân bậc điểm số:
• Mức độ 2★ (Ăn khoảng 60% số điểm - Subtask độ dài xâu $\le 255$):
  • Kiến thức: Kỹ năng duyệt xâu, cắt chuỗi con (substring), hàm kiểm tra ký tự số isdigit(). Ép kiểu dữ liệu từ xâu sang số nguyên (stoi, val hoặc int()) và sử dụng các thuật toán sắp xếp cơ bản.
• Mức độ 3★ (Ăn 100% số điểm - Subtask độ dài xâu lên đến $10^6$ ký tự):
  • Kiến thức: Kỹ thuật xử lý Số Nguyên Lớn (Big Integer) biểu diễn dưới dạng chuỗi, kỹ năng viết hàm so sánh tùy biến (Custom Comparator), thuật toán sắp xếp ổn định (std::stable_sort trong C++ hoặc Timsort mặc định của Python) để bảo toàn thứ tự ban đầu khi giá trị bằng nhau.
  • Chi tiết: Vì xâu con chứa chữ số có thể dài tới hàng triệu chữ số nên không thể chuyển đổi sang kiểu số thông thường. Thí sinh phải để nguyên dưới dạng chuỗi ký tự, tiến hành chuẩn hóa xóa các chữ số '0' vô nghĩa ở đầu. Khi so sánh hai xâu số: xâu 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 tự nhiên.

CÂU 3: THỐNG KÊ SẢN PHẨM (TKSP - 5.0 điểm)

• Mô tả bài toán: Đếm số lượng các dãy con liên tiếp trong một mảng sản phẩm thỏa mãn các quy luật thống kê hoặc tần suất lặp lại cho trước.
• Yêu cầu kiến thức & Phân bậc điểm số:
• Mức độ 2★ (Ăn khoảng 40% số điểm - Subtask số phần tử $N \le 10^3$):
  • Kiến thức: Thuật toán duyệt trâu sử dụng 2 vòng lặp for lồng nhau để vét cạn mọi cặp chỉ số đầu - cuối (i, j) của dãy con liên tiếp với độ phức tạp $O(N^2)$. Sử dụng mảng tần suất đơn giản để kiểm tra.
• Mức độ 4★ (Ăn 100% số điểm - Subtask số phần tử $N \le 10^5$):
  • Kiến thức: Cấu trúc dữ liệu mảng đếm phân phối hoặc Bảng băm (std::map, unordered_map trong C++, dict trong Python). Áp dụng kỹ thuật Hai con trỏ nâng cao (Two Pointers) hoặc kỹ thuật Cửa sổ trượt (Sliding Window).
  • Chi tiết: Tối ưu thuật toán về độ phức tạp thời gian tuyến tính $O(N)$. Sử dụng con trỏ phải để liên tục mở rộng cửa sổ, đồng thời cập nhật bảng băm đếm tần suất sản phẩm. Khi cửa sổ chạm hoặc vi phạm điều kiện biên, ta thu hẹp con trỏ trái một cách thông minh để tính toán số dãy con hợp lệ mà không cần duyệt lại từ đầu.

CÂU 4: ĐÈN CHIẾU SÁNG CÔNG CỘNG (CHIEUSANG - 4.0 điểm)

• Mô tả bài toán: Cho tọa độ của $N$ ngôi nhà và $M$ cột đèn công cộng trên một trục thẳng Ox. Hãy tìm bán kính/phạm vi chiếu sáng $d$ nhỏ nhất sao cho đảm bảo tất cả $N$ ngôi nhà đều được chiếu sáng bởi ít nhất một cột đèn.
• Yêu cầu kiến thức & Phân bậc điểm số:
• Mức độ 2★ (Ăn khoảng 40% - 50% số điểm - Subtask dữ liệu nhỏ):
  • Kiến thức: Thuật toán tìm giá trị nhỏ nhất/lớn nhất trên mảng, duyệt vét cạn tuyến tính lồng nhau với độ phức tạp $O(N \times M)$.
  • Chi tiết: Với mỗi ngôi nhà tại tọa độ $a_i$, duyệt qua toàn bộ $M$ cột đèn $b_j$ để tính khoảng cách nhỏ nhất từ nhà đó đến cột đèn gần nhất. Giá trị $d$ cần tìm chính là giá trị lớn nhất trong số các khoảng cách ngắn nhất vừa tìm được của tất cả các ngôi nhà.
• Mức độ 4★ (Ăn 100% số điểm - Subtask dữ liệu lớn $N, M \le 10^5$, tọa độ lên tới $\pm 10^9$):
  • Kiến thức: Thuật toán Sắp xếp dữ liệu (std::sort). Kỹ thuật Tìm kiếm nhị phân trên không gian kết quả (Binary Search on Answer) hoặc giải thuật Tìm kiếm nhị phân vị trí (std::lower_bound, upper_bound trong C++, thư viện bisect trong Python).
  • Chi tiết 1 (Chặt nhị phân kết quả): Thực hiện tìm kiếm nhị phân giá trị bán kính $d$ trong khoảng khả thi $[0, 2 \times 10^9]$. Với mỗi giá trị mid, viết hàm kiểm tra check(mid) xem phạm vi này có bao phủ toàn bộ các nhà hay không bằng kỹ thuật hai con trỏ phối hợp.
  • Chi tiết 2 (Chặt nhị phân vị trí đèn): Sắp xếp lại mảng chứa tọa độ các cột đèn. Duyệt qua từng ngôi nhà $a_i$, dùng hàm tìm kiếm nhị phân tìm ra vị trí của cột đèn nằm ngay trước và ngay sau ngôi nhà đó. Tính khoảng cách đến 2 cột đèn này và lấy giá trị nhỏ hơn. Kết quả cuối cùng là giá trị lớn nhất trong các khoảng cách nhỏ nhất đó. Độ phức tạp tối ưu đạt $O((N + M) \log M)$.

TÓM TẮT CHIẾN THUẬT PHÒNG THI

1. Quản lý kiểu dữ liệu: Đề thi của Nghệ An nổi tiếng với các bài toán số học có dữ liệu lớn. Hãy luôn ghi nhớ dùng kiểu dữ liệu số nguyên 64-bit (long long trong C++) ngay từ Câu 1 để tránh việc bị mất điểm oan do tràn số (Overflow).
2. Kỹ năng xử lý chuỗi: Đối với bài toán tách và so sánh số lớn (Câu 2), tuyệt đối không đưa về kiểu số mà phải thực hiện thao tác so sánh độ dài chuỗi sau chuẩn hóa để tối ưu bộ nhớ và thời gian.
3. Thành thạo các giải thuật tối ưu nền tảng: Để bứt phá lấy điểm tuyệt đối (giải Nhất, giải Nhì), học sinh bắt buộc phải nhuần nhuyễn bộ đôi kỹ thuật: Hai con trỏ/Sliding Window và Tìm kiếm nhị phân nâng cao.