Chọn đội tuyển HSG quốc gia Đồng Tháp 2025-2026 (ngày 1)

SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG THÁP ĐỀ THI CHÍNH THỨC
(Đề thi gồm: 03 trang, 03 câu)

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HSG QUỐC GIA THPT Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi thứ nhất: 16/9/2025
Thời gian: 180 phút (không kể thời gian giao đề)

---

Tổng quan đề thi

	Tên bài	File chương trình	File dữ liệu vào	File kết quả
Bài 1	Hệ thống	STSYS.*	STSYS.INP	STSYS.OUT
Bài 2	Chuỗi DNA	DNASEQ.*	DNASEQ.INP	DNASEQ.OUT
Bài 3	Hội thảo tối ưu hóa	ORCONF.*	ORCONF.INP	ORCONF.OUT

Dấu * được thay thế bởi PY hoặc CPP của ngôn ngữ lập trình sử dụng tương ứng là Python hoặc C++.

Hãy lập trình giải các bài toán sau:

Câu 1 (7 điểm). Hệ thống

Alice đang xây dựng một hệ thống được đặc trưng bằng một dãy gồm n số nguyên dương (a₁, a₂, …, aₙ). Với hai chỉ số 1 ≤ L < R ≤ n, Alice định nghĩa độ ổn định đoạn [L, R] của hệ thống bằng tổng tất cả tích các cặp số trong đoạn, cụ thể: S(L, R) = ∑_(L≤i<j≤R) aᵢ × aⱼ.

Ví dụ, dãy (2, 1, 3, 5), ta có S(1, 2) = 2 × 1 = 2; S(2, 4) = 1 × 3 + 1 × 5 + 3 × 5 = 23.

Trong quá trình vận hành hệ thống, một số đặc trưng bị thay đổi và Alice cần phải tính độ ổn định của một số đoạn. Cụ thể, sẽ có q sự kiện lần lượt xảy ra, mỗi sự kiện thuộc một trong hai loại sau:

1. Loại 1 có dạng: 1 i x, trong đó 1 ≤ i ≤ n và 1 ≤ x ≤ 10⁶, có nghĩa là số thứ i của dãy bị thay đổi thành x.
2. Loại 2 có dạng: 2 L R, trong đó 1 ≤ L < R ≤ n, có nghĩa là cần tính độ ổn định đoạn [L, R] của hệ thống.

Yêu cầu: Cho dãy (a₁, a₂, …, aₙ) và q sự kiện, với mỗi sự kiện loại 2 hãy đưa ra độ ổn định của đoạn cần tính.

Dữ liệu: Vào từ file văn bản STSYS.INP:

• Dòng đầu tiên chứa hai số nguyên dương n, q (2 ≤ n, q ≤ 2 × 10⁵).
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁶).
• Tiếp theo là q dòng, mỗi dòng chứa ba số 1 i x hoặc 2 L R mô tả loại dạng sự kiện xảy ra.

Kết quả: Ghi ra file văn bản STSYS.OUT gồm một số dòng, mỗi dòng chứa một số là độ ổn định cần tính tương ứng với sự kiện loại 2 xảy ra. Vì giá trị này có thể rất lớn nên chỉ cần đưa ra giá trị S(L, R) % (10⁹ + 7), trong đó phép toán % là phép toán chia lấy dư.

Ràng buộc:

• Có 40% số test thỏa mãn: n, q ≤ 200.
• 30% số test khác thỏa mãn: aᵢ ≤ 10³ và cả q sự kiện đều là thao tác loại 2.
• 30% số test còn lại không có ràng buộc nào thêm.

Ví dụ:

STSYS.INP	STSYS.OUT
4 4 2 1 3 5 2 1 2 2 2 4 1 1 5 2 1 3	2 23 23

Câu 2 (7 điểm). Chuỗi DNA

Alice đang nghiên cứu về mã di truyền, cô cần tạo ra các chuỗi DNA được biểu diễn bằng xâu nhị phân. Có một số mẫu nhị phân ngắn, được gọi là “mảnh vỡ cấm” có tính chất không ổn định, nếu chúng xuất hiện trong chuỗi DNA như là một xâu con liên tiếp, chúng sẽ gây ra một phản ứng dây chuyền phá hủy chuỗi.

Alice đã xác định được k mảnh vỡ cấm p₁, p₂, …, pₖ. Để đảm bảo sự ổn định, Alice phải tạo ra các chuỗi DNA nhị phân có độ dài đúng bằng n mà tránh hoàn toàn tất cả k mảnh vỡ cấm.

Yêu cầu: Cho n và các xâu nhị phân p₁, p₂, …, pₖ, hãy giúp Alice đếm số lượng chuỗi DNA nhị phân tránh tất cả k mảnh vỡ cấm.

Dữ liệu: Vào từ file văn bản DNASEQ.INP:

• Dòng đầu chứa hai số nguyên n và k (n ≤ 200; k ≤ 10);
• Dòng thứ i (1 ≤ i ≤ k) trong k dòng tiếp theo chứa xâu nhị phân pᵢ (độ dài các xâu không vượt quá n).

Kết quả: Ghi ra file văn bản DNASEQ.OUT một số nguyên là giá trị e % 111539786, trong đó e là số chuỗi DNA nhị phân thỏa mãn và phép toán % là phép toán chia lấy dư.

Ràng buộc:

• Có 40% số test thỏa mãn: n ≤ 20.
• 30% số test khác thỏa mãn: k = 1.
• 30% số test còn lại không có ràng buộc nào thêm.

Ví dụ:

DNASEQ.INP	DNASEQ.OUT
2 1 0	2
2 2 00 10	2

Câu 3 (6 điểm). Hội thảo tối ưu hóa

Hội thảo quốc tế do Alice tổ chức về lĩnh vực tối ưu hóa có N người tham gia tại một hội trường lớn. Trong hội trường chỉ có M ghế, do đó tại mỗi thời điểm có không quá M người được ngồi. Với người i (1 ≤ i ≤ N) cho biết các thông tin sau:

• Người thứ i có mặt từ thời điểm sᵢ đến thời điểm fᵢ;
• Nếu người i ngồi ghế trong một đơn vị thời gian thì mức độ nhiệt tình đóng góp ý kiến trong đơn vị thời gian ngồi đó là aᵢ, còn nếu đứng thì mức độ nhiệt tình đóng góp ý kiến trong đơn vị thời gian đứng là bᵢ. Tuy nhiên, có thể có người lại thích đứng hơn thích ngồi dù còn thừa ghế (aᵢ < bᵢ).

Yêu cầu: Cho thông tin về N người tham dự hội thảo và số ghế M có trong hội trường, hỏi tổng mức độ nhiệt tình tham gia đóng góp ý kiến lớn nhất là bao nhiêu.

Dữ liệu: Vào từ file văn bản ORCONF.INP:

• Dòng đầu chứa hai số nguyên N và M (0 < N, M ≤ 10⁵) là số người tham gia và số ghế.
• N dòng tiếp theo mỗi dòng bốn số aᵢ, bᵢ, sᵢ và fᵢ (|aᵢ|, |bᵢ| < 10⁹; 0 < sᵢ < fᵢ < 10⁹).

Kết quả: Ghi ra file văn bản ORCONF.OUT gồm một dòng chứa một số là tổng mức độ nhiệt tình tham gia đóng góp ý kiến lớn nhất có thể.

Ràng buộc:

• Có 10% số test của bài có: N = 1;
• Có 20% số test khác của bài có: N ≤ 10;
• Có 30% số test khác của bài có: N ≤ 100;
• Có 40% số test còn lại của bài không có ràng buộc nào thêm.

Ví dụ:

ORCONF.INP	ORCONF.OUT	Giải thích
4 2 10 -10 2 3 -1 -3 1 4 6 -6 1 3 7 4 2 4	28	Người 1 ngồi ghế từ thời điểm 2 đến thời điểm 3 → 10 Người 2 ngồi ghế từ thời điểm 1 đến thời điểm 2, đứng từ thời điểm 2 đến thời điểm 3, ngồi ghế từ thời điểm 3 đến thời điểm 4 → -1+(-3)+(-1) = -5 Người 3 ngồi ghế từ thời điểm 1 đến thời điểm 3 → 6+6 = 12 Người 4 đứng từ thời điểm 2 đến thời điểm 3, ngồi ghế từ thời điểm 3 đến thời điểm 4 → 4+7 = 11 Như vậy, tổng mức độ nhiệt tình tham gia là: 10+(-5)+12+11 = 28

---

• Thí sinh KHÔNG được sử dụng tài liệu.
• Giám thị KHÔNG giải thích gì thêm.