Tóm tắt hướng dẫn chấm: Hướng dẫn chi tiết quy trình chấm thi bằng phần mềm Themis, cấu hình bộ test, phân bổ điểm và giải thuật tối ưu cho 4 bài toán lập trình (Nén xâu, Vận chuyển hàng hóa, Chai và dụng cụ mở, Chia phần) thuộc đề thi tuyển sinh lớp 10 Chuyên Tin THPT Chuyên Hạ Long 2026 - 2027.
I. HƯỚNG DẪN CHUNG
- Giám khảo nghiên cứu kỹ đề thi, hướng dẫn chấm, test và bộ mã nguồn.
- Chép bài làm thí sinh vào máy, đối chiếu tính trùng khớp giữa bài trên giấy và máy.
- Thực hiện chấm tự động bằng phần mềm Themis. Tiến hành kiểm tra lại các bài thi gặp lỗi biên dịch, bị 0 điểm hoặc không tìm thấy bài.
- Xuất kết quả trực tiếp từ phần mềm chấm, tuyệt đối không tự quy tròn điểm thành phần cũng như điểm tổng bài thi.
- Lưu toàn bộ dữ liệu chấm thi ra đĩa CD gửi về Hội đồng chấm.
II. ĐÁP ÁN VÀ HƯỚNG DẪN GIẢI
Phân bổ điểm: Subtask 1 (30%), Subtask 2 (30%), Subtask 3 (20%), Subtask 4 (20%). File dữ liệu: enco.INP / enco.OUT.
Hướng dẫn giải:
- Subtask 1 (30%): Do xâu ban đầu không có ký tự trùng nhau đứng cạnh, xâu sau nén giữ nguyên. In ra xâu ban đầu. Độ phức tạp \(O(n)\).
- Subtask 2 (30%): Duyệt qua xâu, nếu thấy 2 ký tự giống nhau liên tiếp thì nén thành "2" kèm ký tự đó; nếu độ dài 1 thì giữ nguyên. Độ phức tạp \(O(n)\).
- Subtask 3 & 4 (40%): Đếm số lượng ký tự giống nhau liên tiếp ở mỗi đoạn rồi thực hiện nén đoạn đó cho đến hết xâu. Độ phức tạp \(O(n)\).
Phân bổ điểm: Mỗi Subtask chiếm 20% số điểm dựa trên sự xuất hiện của các loại hàng nặng (H), trung bình (M) và nhẹ (L). File dữ liệu: carg.INP / carg.OUT.
Hướng dẫn giải:
- Subtask 1 (20%): Chỉ có 1 loại hàng. Hàng nặng đáp án là \(H\); Hàng trung bình đáp án là \(M\); Hàng nhẹ đáp án là \(\lfloor \frac{L}{2} \rfloor\). Độ phức tạp \(O(n)\).
- Subtask 2 (20%): Chỉ có hàng nặng và trung bình. Đáp án là \(H + M\). Độ phức tạp \(O(n)\).
- Subtask 3 (20%): Có hàng nặng và nhẹ. Đáp án là \(H + \lfloor \frac{L}{2} \rfloor\). Độ phức tạp \(O(n)\).
- Subtask 4 (20%): Có hàng trung bình và nhẹ. Ưu tiên ghép nhẹ với trung bình, số cặp là \(\min(M, L)\). Hàng nhẹ còn lại xếp 2 kiện/xe. Đáp án: \(M + \lfloor \frac{L - \min(M, L)}{2} \rfloor\). Độ phức tạp \(O(n)\).
- Subtask 5 (20%): Trường hợp tổng quát. Đáp án: \(H + M + \lfloor \frac{L - \min(M, L)}{2} \rfloor\). Độ phức tạp \(O(n)\).
Phân bổ điểm: 5 Subtask, mỗi subtask 20% số điểm. File dữ liệu: open.INP / open.OUT.
Hướng dẫn giải:
- Subtask 1 (20%): Tham lam chọn nhiều nhất có thể chai nắp bật (\(t_i=0\)) có niềm vui lớn nhất. Độ phức tạp \(O(n \log_2 n)\).
- Subtask 2 (20%): Sắp xếp chai cần mở (\(t_i=1\)) và dụng cụ mở (\(t_i=2\)) giảm dần theo giá trị. Độ phức tạp \(O(n \log_2 n)\).
- Subtask 3 (20%): Duyệt mọi tập con chọn \(m\) đồ vật trong \(n\) đồ vật. Độ phức tạp \(O(C_n^m \cdot m)\).
- Subtask 4 (20%): Giả sử lấy \(i\) chai nắp bật và \(j\) chai cần dụng cụ mở, số dụng cụ là \(k = \min(m - i - j, n_2)\). Độ phức tạp \(O(n^2)\).
- Subtask 5 (20%): Quy hoạch động / Tham lam. Sắp xếp các đồ vật giảm dần. Tính \(dp1[i]\) và \(dp2[i]\), kết quả là \(\max_{i=0 \dots m} (dp1[i] + dp2[m-i])\). Độ phức tạp \(O(n)\).
Phân bổ điểm: 5 Subtask, mỗi subtask 20% số điểm. Yêu cầu bộ trình chấm ngoài checkpart.exe. File dữ liệu: part.INP / part.OUT.
Hướng dẫn giải:
- Subtask 1 (20%): Chia đều từng giá trị xuất hiện chẵn lần cho hai người. Độ phức tạp \(O(n \log_2 n)\).
- Subtask 2 (20%): Thử mọi hoán vị bằng quay lui/mô phỏng. Độ phức tạp \(O(n! \cdot n)\).
- Subtask 3 (20%): Sử dụng Bitmask tìm tập gói kẹo mask thỏa mãn \(2 \cdot sum(mask) \ge S\) và \(2 \cdot (sum(mask) - a_{last}) < S\). Độ phức tạp \(O(n \cdot 2^n)\).
- Subtask 4 (20%): Xét cửa sổ trượt độ dài \(k = \lfloor \frac{n}{2} \rfloor\) trên vòng tròn. Chuyển trạng thái từ nhỏ sang đủ: \[ \sum_{i=0}^{n-1} w[i] = k \cdot S \] \[ \sum_{i=0}^{n-1} w[i] < n \cdot \frac{S}{2} \iff k < \frac{n}{2} \] Mô phỏng thử mọi phép quay vòng, độ phức tạp \(O(n^2)\).
- Subtask 5 (20%): Trượt cửa sổ trên vòng tròn tìm vị trí chuyển từ nhỏ sang đủ trong \(O(n)\).