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

Đề thi gồm có 5 câu, tổng điểm là 10 điểm. Cấu trúc đề phân bổ điểm nhỏ giúp hạn chế rủi ro "mất trắng" điểm của thí sinh, đồng thời phân hóa sâu ở hai câu cuối với các bài toán thuần túy về mặt Số học và Quy luật dãy số toán học nâng cao.

PHẦN 2: CHI TIẾT KIẾN THỨC CẦN THIẾT THEO TỪNG MỨC ĐIỂM

CÂU 1: NHẢY LÒ CÒ (2.5 điểm - Mức độ 1★)

• Bản chất bài toán: Tính toán vị trí và số bước nhảy theo quy luật dịch chuyển định sẵn.
• Kiến thức cần đạt tương ứng mức điểm:
  • Mức điểm 1.0 – 1.5 (Subtask nhỏ): Thí sinh làm chủ cú pháp lập trình cơ bản: các câu lệnh rẽ nhánh (if-else), vòng lặp cơ bản (for, while) để tiến hành mô phỏng từng bước dịch chuyển một cách tuần tự. Biết cấu trúc vào/ra tệp văn bản (CAU1.INP, CAU1.OUT).
  • Mức điểm tối đa 2.5 (Toàn bộ test): Đòi hỏi tư duy tối ưu hóa bằng công thức toán học (giải phương trình/bất phương trình bậc nhất hoặc biểu thức chia lấy dư) thay vì chạy vòng lặp mô phỏng để tránh lỗi quá thời gian (Time Limit Exceeded - TLE). Ngoài ra, học sinh cần có thói quen sử dụng kiểu dữ liệu số nguyên 64-bit (long long trong C++ hoặc số nguyên lớn mặc định trong Python) để không bị tràn số khi dữ liệu lớn.

CÂU 2: PHẦN THƯỞNG (2.5 điểm - Mức độ 2★)

• Bản chất bài toán: Lựa chọn tập hợp phần thưởng tối ưu từ mảng phần tử ban đầu sao cho tổng giá trị thu được lớn nhất dưới các ràng buộc bài toán.
• Kiến thức cần đạt tương ứng mức điểm:
  • Mức điểm 1.0 – 1.5 (Subtask nhỏ): Thí sinh biết áp dụng các vòng lặp lồng nhau với độ phức tạp $O(N^2)$ để thực hiện việc tìm kiếm hoặc tự viết lại các thuật toán sắp xếp mảng cơ bản (như Bubble Sort, Selection Sort, Insertion Sort) áp dụng thành công cho các bộ dữ liệu nhỏ.
  • Mức điểm tối đa 2.5 (Toàn bộ test): Đòi hỏi thí sinh hiểu rõ bản chất và áp dụng nhuần nhuyễn chiến lược Tham lam (Greedy Algorithm). Cần nắm vững việc gọi các hàm sắp xếp mảng tối ưu có sẵn của ngôn ngữ lập trình (std::sort trong C++ với thư viện <algorithm> hoặc hàm sorted() trong Python) để đưa độ phức tạp về $O(N \log N)$, đáp ứng hoàn hảo giới hạn thời gian chạy 1 giây của hệ thống chấm tự động.

CÂU 3: SỐ CHÍNH PHƯƠNG (2.0 điểm - Mức độ 3★)

• Bản chất bài toán: Duyệt mảng dữ liệu, đếm ước số, hoặc kiểm tra tính chất số chính phương của các số nguyên dương lớn trong mảng.
• Kiến thức cần đạt tương ứng mức điểm:
  • Mức điểm 1.0 (Subtask nhỏ): Thí sinh chỉ cần biết kỹ thuật duyệt tuyến tính thô sơ từ $1$ đến $N$ để đếm ước số của một số nguyên với độ phức tạp $O(N)$. Kỹ thuật này chỉ vượt qua các cấu trúc dữ liệu kiểm thử kích thước nhỏ.
  • Mức điểm tối đa 2.0 (Toàn bộ test): Thí sinh bắt buộc phải sở hữu nền tảng vững vàng về Toán số học cơ bản. Cụ thể: biết cách tối ưu thuật toán kiểm tra số chính phương bằng hàm căn bậc hai (sqrt) kết hợp ép kiểu nguyên, hoặc nâng cấp vòng lặp đếm ước số với độ phức tạp giảm xuống còn $O(\sqrt{N})$. Thành thạo trong việc quản lý và xử lý chính xác kiểu dữ liệu số nguyên lớn để loại bỏ các lỗi sai sót giá trị biên.

CÂU 4: THU HOẠCH CÀ RỐT (1.5 điểm - Mức độ 4★)

• Bản chất bài toán: Tính tổng số lượng cà rốt thu hoạch tăng dần theo quy luật và áp dụng phép chia lấy dư cho một hằng số lớn ($10^9+7$).
• Kiến thức cần đạt tương ứng mức điểm:
  • Mức điểm 0.5 – 0.75 (Subtask nhỏ): Sử dụng các vòng lặp cộng dồn tuyến tính $O(N)$ đơn giản để quét qua quá trình thu hoạch của thỏ, ăn điểm ở những cấu trúc dữ liệu ban đầu không bị ràng buộc chặt chẽ.
  • Mức điểm tối đa 1.5 (Toàn bộ test): Đòi hỏi tư duy phân tích toán học chuyên sâu. Học sinh phải nhìn ra bản chất cốt lõi của việc tính tổng thu hoạch chính là tính tổng của một Cấp số cộng (Arithmetic Progression). Thí sinh cần lập và áp dụng công thức tính nhanh tổng cấp số cộng:
    $$S_i = \frac{(2x_i + m_i \cdot k_i) \times (m_i + 1)}{2}$$
    để đưa thuật toán về độ phức tạp tối ưu nhất. Đặc biệt, thí sinh phải làm chủ kỹ nghệ Đồng dư thức (Modular Arithmetic): Do kết quả cực lớn cần chia lấy dư cho $10^9+7$, nếu lập trình bằng C++ phải biết cách nhân với nghịch đảo mô-đun của 2 (giá trị cụ thể là số $500000004$) thay cho phép chia đại số thông thường, nhằm triệt tiêu hoàn toàn lỗi sai số và tràn bộ nhớ.

CÂU 5: DÃY SỐ ZIGZAC CHU KỲ (1.5 điểm - Mức độ 5★)

• Bản chất bài toán: Tính toán tổng các phần tử nằm trong khoảng vị trí từ $l$ đến $r$ trên một dãy số dài vô hạn tuần hoàn, trong đó các số biến thiên zigzag theo quy luật tăng/giảm đan xen qua từng phân đoạn có độ dài chu kỳ $k$.
• Kiến thức cần đạt tương ứng mức điểm:
  • Mức điểm 0.75 (Giải quyết 50% số điểm): Dành cho thí sinh vượt qua được các test case có cấu trúc đặc biệt (ví dụ: chu kỳ $k=1$ hoặc độ dài chu kỳ đúng bằng tổng số phần tử $k=n$). Học sinh có thể khai thác mảng tĩnh hoặc thiết lập vòng lặp chạy trực tiếp từ biên $l$ đến $r$ để cộng dồn từng phần tử với độ phức tạp thuật toán là $O(r - l + 1)$.
  • Mức điểm tối đa 1.5 (Toàn bộ test - Phân hóa ngôi vị): Thí sinh đạt mức này phải sở hữu năng lực toán học và thuật toán xuất sắc. Cần áp dụng kỹ thuật tư duy Mảng cộng dồn tiền tố (Prefix Sum) để chuyển đổi bài toán từ tính khoảng ngẫu nhiên $(l, r)$ về hiệu của hai tổng tiền tố:
    $$Sum(l, r) = PrefixSum(r) - PrefixSum(l - 1)$$
    Mục tiêu tối thượng là xây dựng được hàm tính $PrefixSum(x)$ đạt độ phức tạp thời gian tuyệt đối là $O(1)$ cho mỗi truy vấn. Để làm được điều này, học sinh cần vận dụng kỹ năng cô đọng toán học chu kỳ:
  • Xác định chính xác số lượng nhóm chu kỳ đầy đủ đứng trước vị trí vị trí $x$: num_groups = x // k.
  • Sử dụng công thức toán để tính nhanh tổng của toàn bộ các nhóm chu kỳ đầy đủ này.
  • Phân tích trạng thái chẵn lẻ của nhóm chu kỳ cuối cùng (nhóm chưa đầy đủ thứ num_groups + 1) để tính nốt phần dư từ vị trí đầu nhóm đến vị trí $x$ theo đúng quy luật zigzag (tăng dần đối với chu kỳ lẻ, giảm dần đối với chu kỳ chẵn).

Tài liệu này là cẩm nang phân tích cấu trúc hữu ích dành cho các thầy cô giáo bộ môn và các bạn học sinh trong lộ trình ôn luyện chuyên sâu cấu trúc đề thi Chuyên Tin học tỉnh Khánh Hòa.