Chọn đội tuyển HSG quốc gia Hưng Yên 2026-2027

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH HƯNG YÊN ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT Năm học 2026 - 2027
Môn thi: Tin học
Thời gian làm bài: 180 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Câu	Bài	Tên tệp chương trình	Tên tệp dữ liệu	Tên tệp kết quả	Điểm
1	Chia bút thưởng	CHIABUT.*	CHIABUT.INP	CHIABUT.OUT	7
2	Dán băng rôn	BANGRON.*	BANGRON.INP	BANGRON.OUT	7
3	Mê cung một chiều	MECUNG.*	MECUNG.INP	MECUNG.OUT	6

Dấu * được thay thế bởi PAS hoặc CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal hoặc C++ hoặc Python.

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

Câu 1. Chia bút thưởng

Nhà trường có n thùng bút để làm phần thưởng, thùng thứ i chứa aᵢ chiếc bút. Ban tổ chức chọn một số nguyên d và chia bút thành các gói, mỗi gói gồm đúng d chiếc. Bút của các thùng khác nhau không được trộn vào cùng một gói (mỗi thùng do một lớp đóng riêng), nên từ thùng thứ i chỉ đóng được ⌊aᵢ / d⌋ gói. Sau khi đóng gói, còn lại (aᵢ mod d) chiếc bút không đủ để tạo thành một gói; gọi đó là lượng bút lẻ của thùng thứ i.

Quy định của nhà trường buộc mỗi gói phải có không ít hơn L chiếc và không nhiều hơn R chiếc, tức L ≤ d ≤ R.

Hãy chọn d để tổng lượng bút lẻ của cả n thùng là nhỏ nhất. In ra tổng lượng bút lẻ nhỏ nhất đó và giá trị d nhỏ nhất đạt được nó.

Dữ liệu

• Dòng 1: ba số nguyên n, L, R (1 ≤ n ≤ 2×10⁵; 1 ≤ L ≤ R ≤ 10⁶).
• Dòng 2: n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶).

Kết quả

Một dòng gồm hai số nguyên cách nhau bởi dấu cách: tổng lượng bút lẻ nhỏ nhất, và giá trị d nhỏ nhất đạt được tổng đó.

Giới hạn

• Giới hạn thời gian: 1 s; giới hạn bộ nhớ: 256 MB.

Subtask	Điểm	Ràng buộc bổ sung
1	15%	n ≤ 100; R ≤ 100; aᵢ ≤ 100
2	20%	n ≤ 2×10³; R ≤ 2×10³
3	20%	R − L ≤ 100
4	20%	n ≤ 2×10⁵; R ≤ 10⁵; aᵢ ≤ 10⁵
5	25%	Không có ràng buộc bổ sung

Ví dụ

CHIABUT.INP	CHIABUT.OUT	Giải thích
5 2 5 7 10 13 4 9	3 2	d = 2 lẻ 1+0+1+0+1 = 3 chiếc; d = 3 lẻ 4, d = 4 lẻ 7; d = 5 lẻ 13. Nhỏ nhất là 3, đạt tại d = 2.
5 1 3 7 10 13 4 9	0 1	d = 1 mọi thùng chia hết nên không lẻ chiếc nào.
3 4 6 5 5 5	0 5	d = 4 lẻ 3 chiếc; d = 5 cả ba thùng chia hết; d = 6 lớn hơn mọi aᵢ nên lẻ trọn 15 chiếc.

Câu 2. Dán băng rôn

Để chuẩn bị cho lễ khai giảng, nhà trường cần dán một khẩu hiệu gồm n chữ cái tiếng Anh in thường, tạo thành xâu S, các vị trí đánh số từ 1 đến n. Khẩu hiệu được cắt thành các băng rôn: mỗi băng rôn là một đoạn gồm các chữ cái liên tiếp của S, hai băng rôn bất kỳ không chồng lên nhau, và ghép tất cả các băng rôn lại theo đúng thứ tự thì được lại xâu S.

Một băng rôn được gọi là hợp lệ nếu đồng thời thoả mãn hai điều kiện:

• Độ dài của nó nằm trong đoạn [L, R];
• Có nhiều nhất một chữ cái xuất hiện với số lần lẻ.

Mỗi băng rôn hợp lệ được gán một dấu cho biết chữ cái nào xuất hiện số lần lẻ:

• Nếu có đúng một chữ cái xuất hiện với số lần lẻ thì dấu là chữ cái đó;
• Nếu mọi chữ cái đều xuất hiện với số lần chẵn thì dấu là RỖNG.

Như vậy dấu nhận một trong 27 giá trị. Dấu của mỗi băng rôn được ghi ở mặt sau để thợ biết băng rôn nào treo ở đâu.

Hai băng rôn cạnh nhau mang cùng một dấu thì rất dễ bị treo lẫn, vì vậy nhà trường quy định: một cách cắt được gọi là chấp nhận được nếu mọi băng rôn đều hợp lệ và không có hai băng rôn cạnh nhau nào mang cùng một dấu. Lưu ý rằng RỖNG cũng là một giá trị dấu bình thường: hai băng rôn cạnh nhau cùng mang dấu RỖNG là không được phép.

Hãy tìm số băng rôn ít nhất trong tất cả các cách cắt chấp nhận được, hoặc cho biết không tồn tại cách cắt chấp nhận được nào.

Dữ liệu

• Dòng 1: ba số nguyên n, L, R (1 ≤ L ≤ R ≤ n ≤ 2×10⁵).
• Dòng 2: xâu S gồm n chữ cái tiếng Anh in thường.

Kết quả

Một số nguyên duy nhất: số băng rôn ít nhất, hoặc -1 nếu không có cách cắt chấp nhận được nào.

Giới hạn

• Giới hạn thời gian: 2 s; giới hạn bộ nhớ: 256 MB.

Subtask	Điểm	Ràng buộc bổ sung
1	25%	n ≤ 300
2	25%	n ≤ 3×10³
3	25%	R − L ≤ 20
4	25%	Không có ràng buộc bổ sung

Ví dụ

BANGRON.INP	BANGRON.OUT	Giải thích
7 2 4 aabcbaa	3	Cách cắt aa | bcb | aa có các dấu lần lượt là RỖNG, c, RỖNG. Chú ý rằng lấy băng rôn đầu dài nhất có thể là aab (dấu b) sẽ khiến phần còn lại cbaa không cắt được nữa.
8 2 4 abbaabba	3	Băng rôn abb hợp lệ vì chỉ có chữ a xuất hiện lẻ lần, nên dấu của nó là a. Cách cắt abb | aa | bba có các dấu a, RỖNG, a. Cách cắt thành 2 băng rôn duy nhất là abba | abba, cả hai đều mang dấu RỖNG nên bị loại.
4 2 2 aabb	-1	Cách cắt duy nhất là aa | bb, cả hai băng rôn đều mang dấu RỖNG.

Câu 3. Mê cung một chiều

Khu trải nghiệm của trường là một mê cung gồm n phòng, đánh số từ 1 đến n. Tại mỗi phòng i có đúng một cửa ra và có thể có nhiều cửa vào. Qua cửa ra này, ta đi đến phòng f(i) và mất w(i) giây. Có thể xảy ra f(i) = i, nghĩa là qua cửa rồi ta lại trở về chính phòng i. Trong mỗi phòng i có đặt một phần thưởng trị giá a(i).

Một người đứng ở phòng x và liên tục đi qua cửa của phòng mình đang đứng. Vì mỗi phòng chỉ có một cửa ra nên hành trình của người đó là hoàn toàn xác định. Mỗi lần đi qua một cửa được tính là một bước, bất kể cửa đó mất bao nhiêu giây; cửa dẫn ngược lại chính phòng đang đứng cũng tính là một bước.

Ban tổ chức cần xử lí q thao tác, mỗi thao tác thuộc một trong năm loại sau:

Loại	Cú pháp	Ý nghĩa
1	1 u v	Hai người đứng ở phòng u và phòng v, cùng xuất phát và mỗi lần cùng đi một bước. Hãy cho biết số bước ít nhất t ≥ 0 để sau đó hai người ở CÙNG một phòng; nếu điều đó không bao giờ xảy ra thì trả lời -1.
2	2 u k	Xuất phát từ phòng u và đi đúng k bước. Hãy cho biết phòng dừng lại và tổng thời gian đã đi.
3	3 u k	Xét k phòng đầu tiên trong hành trình xuất phát từ u, tức các phòng sau 0, 1, …, k − 1 bước (một phòng đi qua nhiều lần vẫn tính nhiều lần). Hãy cho biết giá trị phần thưởng lớn nhất trong các phòng đó.
4	4 v k	Hãy đếm số phòng x sao cho xuất phát từ x, sau không quá k bước thì tới được phòng v (phòng v được tính, ứng với 0 bước).
5	5 x c	Thay phần thưởng của phòng x bằng giá trị c. Thao tác này không in ra kết quả.

Hãy xử lí lần lượt q thao tác theo đúng thứ tự đã cho.

Dữ liệu

• Dòng 1: hai số nguyên n và q (1 ≤ n, q ≤ 2×10⁵).
• Dòng 2: n số nguyên f(1), f(2), …, f(n) (1 ≤ f(i) ≤ n).
• Dòng 3: n số nguyên w(1), w(2), …, w(n) (1 ≤ w(i) ≤ 10⁹).
• Dòng 4: n số nguyên a(1), a(2), …, a(n) (0 ≤ a(i) ≤ 10⁹).
• q dòng tiếp theo, mỗi dòng mô tả một thao tác theo đúng cú pháp trong bảng trên, với 1 ≤ u, v, x ≤ n; 1 ≤ k ≤ 10⁹; 0 ≤ c ≤ 10⁹.

Kết quả

• Ứng với mỗi thao tác loại 1, 3, 4 ghi ra một dòng chứa một số nguyên là kết quả của thao tác đó.
• Ứng với mỗi thao tác loại 2 ghi ra một dòng chứa hai số nguyên cách nhau bởi dấu cách: phòng dừng lại và tổng thời gian đã đi.
• Thao tác loại 5 không ghi ra kết quả.

Giới hạn

• Giới hạn thời gian: 2 s; giới hạn bộ nhớ: 256 MB.

Subtask	Điểm	Ràng buộc bổ sung
1	25%	n ≤ 300; q ≤ 300; k ≤ 300
2	20%	n ≤ 3×10³; q ≤ 3×10³; k ≤ 3×10³
3	20%	Dãy f là một hoán vị của 1, 2, …, n
4	15%	Mọi chu trình trong mê cung đều có độ dài 1
5	20%	Không có ràng buộc bổ sung

Ví dụ

MECUNG.INP	MECUNG.OUT	Giải thích
5 6 2 3 2 3 1 5 1 2 4 3 7 2 9 4 1 1 5 4 2 5 3 3 1 3 4 2 1 5 3 0 3 1 3	2 3 9 9 3 7	Mê cung có chu trình 2 → 3 → 2; phòng 1 dẫn vào phòng 2; phòng 5 dẫn vào phòng 1; phòng 4 dẫn vào phòng 3. Thao tác 1: hai người ở phòng 5 và phòng 4 đi theo (5, 4) → (1, 3) → (2, 2), gặp nhau sau 2 bước. Thao tác 2: 5 → 1 → 2 → 3, tổng thời gian 3 + 5 + 1 = 9. Thao tác 3: ba phòng đầu là 1, 2, 3 với phần thưởng 7, 2, 9; lớn nhất là 9. Thao tác 4: các phòng tới được phòng 2 trong không quá 1 bước là 2, 1 và 3. Thao tác 5: phần thưởng phòng 3 đổi thành 0. Thao tác 6: vẫn ba phòng 1, 2, 3 nhưng phần thưởng nay là 7, 2, 0; lớn nhất là 7.

---

(Thí sinh không được sử dụng tài liệu; Giám thị không giải thích gì thêm.)