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

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 TRUNG HỌC PHỔ THÔNG Năm học 2025 - 2026
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

	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
Câu 1	Trò chơi nuôi cá	CA.*	CA.INP	CA.OUT	7
Câu 2	Gạch	GACH.*	GACH.INP	GACH.OUT	7
Câu 3	Di chuyển	CHUYEN.*	CHUYEN.INP	CHUYEN.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. Trò chơi nuôi cá

Có n thùng nước thả cá với dung tích chứa nước vô hạn. Lượng nước trong thùng thứ i tại thời điểm bắt đầu trò chơi là a_i. Các thùng đều bị rò nước, thùng thứ i rò mất b_i lít nước mỗi phút. Cá sẽ chết nếu thùng xuống dưới mực nước chết. Để đơn giản, ta coi mực nước chết bằng 0, nghĩa là thùng có thể bị rò nước xuống dưới mức 0. Mỗi phút người chơi có quyền bổ sung x lít nước cho một thùng duy nhất bất kỳ. (Ví dụ tại đầu phút thứ p, thùng thứ i đang còn chứa c_i lít và được bổ sung thêm x lít thì lượng nước còn lại trong thùng khi bắt đầu phút p + 1 là c_i − b_i + x (lít)).

Người chơi thắng nếu duy trì được tất cả cá sống k phút. Tìm giá trị x nhỏ nhất để người chơi có thể thắng được. Nếu không có giá trị nào phù hợp, in ra −1.

Dữ liệu

• Dòng 1: hai số nguyên n, k, 1 ≤ n, k ≤ 2×10⁵.
• Dòng 2: n số nguyên a₁, a₂, …, a_n - lượng nước ban đầu, 1 ≤ a_i ≤ 10¹², 1 ≤ i ≤ n.
• Dòng 3: n số nguyên b₁, b₂, …, b_n - mức rò của từng thùng, 1 ≤ b_i ≤ 10⁷, 1 ≤ i ≤ n.

Kết quả

In ra một số nguyên duy nhất - giá trị nhỏ nhất của x. Nếu không tồn tại, in ra −1.

Giới hạn

• Giới hạn thời gian: 3s; giới hạn bộ nhớ: 256 MB.
• 40% số điểm: 1 ≤ n ≤ 5, 1 ≤ k ≤ 10; 1 ≤ a_i, b_i ≤ 10, 1 ≤ i ≤ n.
• 10% số điểm: n = 1, 1 ≤ k ≤ 2×10⁵; 1 ≤ a_i ≤ 10¹², 1 ≤ b_i ≤ 10⁷, 1 ≤ i ≤ n.
• 50% số điểm: 1 ≤ n, k ≤ 2×10⁵; 1 ≤ a_i ≤ 10¹², 1 ≤ b_i ≤ 10⁷, 1 ≤ i ≤ n.

Ví dụ

CA.INP	CA.OUT	Giải thích
2 4 3 2 4 2	5	Với x = 5, thêm nước lần lượt cho thùng 1, 2, 1, ta có các giá trị qua từng phút lần lượt: Phút 1: [3 − 4 + 5, 2 − 2] = [4, 0] Phút 2: [4 − 4, 0 − 2 + 5] = [0, 3] Phút 3: [0 − 4 + 5, 3 − 2] = [1, 1] Phút 4: [1 − 4, 1 − 2 + 5] = [−3, 4] nhưng chỉ xét đầu phút nên vẫn hợp lệ. Không phần tử nào âm → x = 5 là nhỏ nhất.

Câu 2. Gạch

Có một hàng gạch gồm n viên đặt liên tiếp, mỗi viên được sơn một màu, biểu diễn bằng một chữ cái thường (‘a’..‘z’).

Bạn có thể thực hiện nhiều lần thao tác sau cho đến khi không còn viên gạch nào:

• Chọn một đoạn liên tiếp gồm các viên gạch có cùng màu.
• Phá hủy toàn bộ đoạn này.
• Sau đó, hai phần gạch còn lại (nếu có) sẽ được ghép lại thành một hàng liên tục.

Nhiệm vụ của bạn là xác định số thao tác ít nhất cần thực hiện để phá bỏ toàn bộ hàng gạch.

Dữ liệu

• Dòng 1: số nguyên n, 1 ≤ n ≤ 500.
• Dòng 2: Xâu ký tự độ dài n, chỉ gồm chữ cái thường, mô tả màu của các viên gạch.

Kết quả

In ra một số nguyên duy nhất: số thao tác ít nhất cần thực hiện.

Giới hạn

• Giới hạn thời gian: 3s; giới hạn bộ nhớ: 256 MB.
• 20% số điểm: 1 ≤ n ≤ 10.
• 30% số điểm: 1 ≤ n ≤ 20.
• 50% số điểm: 1 ≤ n ≤ 500.

Ví dụ

GACH.INP	GACH.OUT	Giải thích
5 abaca	3	Phá hủy ‘b’ (còn lại ‘aaca’) → phá hủy ‘c’ (còn lại ‘aaa’) → phá hủy ‘aaa’ (còn rỗng).

Câu 3. Di chuyển

Cho một bảng 2 chiều kích thước n × m. Mỗi ô được gán một màu, biểu diễn bằng số nguyên từ 1 đến k; dữ liệu đầu vào đảm bảo mỗi màu có ít nhất một ô có màu đó. Bạn có thể di chuyển theo các quy tắc sau:

• Trong 1 giây, bạn có thể đi từ ô hiện tại sang một trong 4 ô kề cạnh (trên, dưới, trái, phải), nếu ô đó tồn tại.
• Hoặc, trong 1 giây, bạn có thể đi từ ô hiện tại đến bất kỳ ô nào khác cùng màu.

Có q truy vấn, mỗi truy vấn ở trên 1 dòng gồm hai ô (a, b) và (c, d). Hãy tính thời gian tối thiểu để đi từ ô (a, b) đến ô (c, d).

Dữ liệu

• Dòng đầu tiên chứa 3 số nguyên n, m, k (1 ≤ n, m ≤ 10³; 1 ≤ k ≤ min(40, n × m)).
• n dòng tiếp theo, mỗi dòng gồm m số nguyên, biểu diễn màu của các ô.
• Dòng tiếp theo chứa số nguyên q (1 ≤ q ≤ 10⁵).
• Mỗi dòng trong q dòng tiếp theo chứa 4 số nguyên a, b, c, d (1 ≤ a, c ≤ n, 1 ≤ b, d ≤ m) mô tả một truy vấn.

Kết quả

Với mỗi truy vấn, in ra một số nguyên duy nhất - thời gian tối thiểu để đi từ (a, b) đến (c, d) - trên một dòng.

Giới hạn

• Giới hạn thời gian: 5s; giới hạn bộ nhớ: 256 MB.
• 20% số điểm: 1 ≤ n, m ≤ 5, 1 ≤ q ≤ 10⁵; đảm bảo tất cả các ô có màu khác nhau.
• 30% số điểm: 1 ≤ n, m ≤ 10, 1 ≤ q ≤ 10⁵; 1 ≤ k ≤ min(40, n × m).
• 50% số điểm còn lại: 1 ≤ n, m ≤ 10³, 1 ≤ q ≤ 10⁵, 1 ≤ k ≤ min(40, n × m).

Ví dụ

CHUYEN.INP	CHUYEN.OUT	Giải thích
3 4 5 1 2 1 3 4 4 5 5 1 2 1 3 2 1 1 3 4 2 2 2 2	2 0	Truy vấn 1: nên đi từ ô (1,1) đến ô (3,3) vì chúng có cùng màu, sau đó từ ô (3,3) đến ô (3,4) vì chúng kề cạnh nhau (tổng cộng 2 giây di chuyển). Truy vấn 2: đã bắt đầu ngay tại ô đích.