HSG lớp 12 Quảng Trị 2025-2026

SỞ GDĐT QUẢNG TRỊ ĐỀ CHÍNH THỨC
(Đề thi gồm có 04 trang và 04 câu)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 Năm học 2025 - 2026 - Khóa ngày 15 tháng 12 năm 2025
Môn thi: Tin học
Thời gian: 150 phút (không kể thời gian giao đề)

---

Tổng quan về đề thi

Câu	Tên bài	Tên tệp	Tên tệp dữ liệu vào	Tên tệp kết quả	Điểm
Câu 1	Trò chơi điện tử	GAME.*	GAME.INP	GAME.OUT	5.0
Câu 2	Thẻ bài	MAGIC.*	MAGIC.INP	MAGIC.OUT	5.0
Câu 3	Phần tử thiếu	MISS.*	MISS.INP	MISS.OUT	5.0
Câu 4	Bước nhảy không gian	JUMP.*	JUMP.INP	JUMP.OUT	5.0

• Dấu * là CPP hoặc PY hoặc PAS tùy theo ngôn ngữ lập trình được lựa chọn;
• Thời gian thực hiện của chương trình đối với mỗi bộ test bất kỳ không quá 01 giây.

Câu 1. Trò chơi điện tử (5,0 điểm)

Trong trò chơi điện tử có tên Zentric, nhân vật được điều khiển di chuyển trên một ô lưới (giả sử số ô không hạn chế).

Khởi đầu trò chơi, nhân vật được đặt tại một ô bất kỳ. Tại mỗi bước, nhân vật có thể di chuyển đến ô liền kề là một trong số các ô: bên trái, bên phải, phía trên, phía dưới của ô hiện tại.

Để hướng dẫn nhân vật di chuyển, cần một chuỗi lệnh S gồm các ký tự ‘L’ (Left – sang trái), ‘R’ (Right – sang phải), ‘U’ (Up – lên trên) và ‘D’ (Down – xuống dưới).

Cho trước chuỗi lệnh S, để hoàn thành màn chơi, bạn cần chỉnh sửa lại chuỗi lệnh S sao cho có thể hướng dẫn nhân vật di chuyển qua các ô, mỗi ô được phép đi qua không quá một lần và phải trở về đúng ô xuất phát. Việc chỉnh sửa lại chuỗi lệnh S có thể được thực hiện bằng cách:

• Xoá đi một số ký tự (có thể không xoá ký tự nào) trong chuỗi lệnh S;
• Thay đổi vị trí các ký tự trong chuỗi lệnh S theo ý muốn.

Yêu cầu: Hãy xác định độ dài lớn nhất của chuỗi lệnh S sau khi thực hiện việc chỉnh sửa.

Dữ liệu vào: Đọc từ tệp văn bản GAME.INP có cấu trúc như sau:

• Dòng 1: Chứa chuỗi lệnh S (độ dài không vượt quá 10⁶).

Kết quả: Ghi ra tệp văn bản GAME.OUT theo cấu trúc:

• Dòng 1: Ghi một số nguyên t là kết quả của bài toán. Trường hợp không thể chỉnh sửa chuỗi lệnh S để hoàn thành màn chơi thì ghi −1.

Ví dụ:

GAME.INP	GAME.OUT	Giải thích
LURD	4	Không phải xoá ký tự nào
LDLDURURL	8	Phải xoá đi 01 ký tự ‘L’
LLLLU	-1	Không có phương án chỉnh sửa chuỗi để hoàn thành màn chơi

Ràng buộc:

• Có 60% số test tương ứng với 60% số điểm: độ dài xâu không quá 255 kí tự;
• Có 40% số test tương ứng với 40% số điểm: không có ràng buộc gì thêm.

Câu 2. Thẻ bài (5,0 điểm)

Alice và Peter là đôi bạn thân có cùng đam mê mãnh liệt với việc sưu tầm các thẻ bài Magic: The Gathering.

Hiện tại, Alice đang sở hữu N thẻ bài với các giá trị tương ứng là: A₁, A₂, …, A_N. Tương tự, Peter cũng sở hữu N thẻ bài với các giá trị tương ứng là: B₁, B₂, …, B_N.

Alice rất muốn biết tập hợp x thẻ bài đầu tiên của mình có giống tập hợp y thẻ bài đầu tiên của Peter không. Hai tập hợp được coi là giống nhau nếu mọi loại thẻ bài của Alice cũng trùng với Peter và ngược lại.

Yêu cầu: Bạn hãy giúp Alice trả lời câu hỏi của mình.

Dữ liệu vào: Đọc từ tệp văn bản MAGIC.INP có cấu trúc như sau:

• Dòng 1: Chứa số nguyên dương N (1 ≤ N ≤ 2.10⁵), là số lượng thẻ bài của mỗi bạn;
• Dòng 2: Chứa N số nguyên dương: A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ 10⁹, 1 ≤ i ≤ N), là danh sách giá trị các thẻ bài của Alice;
• Dòng 3: Chứa N số nguyên dương: B₁, B₂, …, B_N (1 ≤ Bᵢ ≤ 10⁹, 1 ≤ i ≤ N), là danh sách giá trị các thẻ bài của Peter;
• Dòng 4: Chứa số nguyên dương Q (1 ≤ Q ≤ 2.10⁵), là số lượng các truy vấn;
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương: x, y (1 ≤ x, y ≤ N) tương ứng với việc xét tập hợp x thẻ bài đầu tiên của Alice với tập hợp y thẻ bài đầu tiên của Peter.

Lưu ý: Các giá trị trên một dòng được ghi cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản MAGIC.OUT theo cấu trúc:

Gồm Q dòng tương ứng với Q truy vấn, mỗi dòng ghi ra “Yes” nếu tập hợp các loại thẻ bài của hai bạn giống hệt nhau, ngược lại ghi ra “No”.

Ví dụ:

MAGIC.INP	MAGIC.OUT
5 1 2 3 4 5 1 3 2 3 5 3 3 3 3 4 5 5	Yes Yes No

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm: 1 ≤ N, Q ≤ 200; x = y; các giá trị Aᵢ đôi một khác nhau; các giá trị Bᵢ đôi một khác nhau;
• Có 25% số test tương ứng với 25% số điểm: 1 ≤ N, Q ≤ 2000;
• Có 25% số test tương ứng với 25% số điểm: không có ràng buộc gì thêm.

Câu 3. Phần tử thiếu (5,0 điểm)

Alice là một học sinh có đam mê làm việc với các con số. Cậu sưu tầm và lưu lại danh sách các số nguyên dương mà mình thích và gọi đó là những số nguyên dương “đẹp”.

Hiện tại, Alice đang sở hữu một danh sách A gồm N số nguyên dương đẹp: A₁, A₂, …, A_N, các giá trị đôi một khác nhau và được sắp xếp tăng dần (A₁ < A₂ < … < A_N). Các số nguyên dương không xuất hiện trong danh sách A được gọi là các “phần tử thiếu”.

Alice cần trả lời Q truy vấn độc lập, mỗi truy vấn cho một số nguyên dương k. Hãy xác định giá trị phần tử thiếu thứ k khi liệt kê các phần tử thiếu của danh sách A theo thứ tự tăng dần.

Yêu cầu: Bạn hãy giúp Alice trả lời Q truy vấn trên.

Dữ liệu vào: Đọc từ tệp văn bản MISS.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên dương N và Q (1 ≤ N, Q ≤ 10⁵), lần lượt là số lượng phần tử trong danh sách và số lượng các truy vấn; các giá trị được ghi cách nhau một dấu cách.
• Dòng 2: Chứa N số nguyên dương A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ 10¹⁸); các giá trị được ghi cách nhau một dấu cách. Dữ liệu đảm bảo danh sách A được sắp xếp tăng nghiêm ngặt.
• Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương kᵢ (1 ≤ kᵢ ≤ 10¹⁸, 1 ≤ i ≤ Q), tương ứng với câu hỏi tìm phần tử thiếu thứ kᵢ.

Kết quả: Ghi ra tệp văn bản MISS.OUT theo cấu trúc:

Gồm Q dòng: Dòng thứ i ghi một số nguyên t là giá trị phần tử thiếu thứ kᵢ (1 ≤ i ≤ Q) trong danh sách A.

Ví dụ:

MISS.INP	MISS.OUT	Giải thích
5 3 1 3 9 12 17 2 9 19	4 13 24	- Phần tử thiếu thứ 2 là 4 - Phần tử thiếu thứ 9 là 13 - Phần tử thiếu thứ 19 là 24

Ràng buộc:

• Có 40% số test tương ứng với 40% số điểm: 1 ≤ N, Q ≤ 2 × 10³;
• Có 30% số test tương ứng với 30% số điểm: 1 ≤ Aᵢ ≤ 10⁶ (1 ≤ i ≤ N);
• Có 30% số test tương ứng với 30% số điểm: không có ràng buộc gì thêm.

Câu 4. Bước nhảy không gian (5,0 điểm)

Giả sử đến năm 2045, giữa những vùng không gian vũ trụ, công nghệ dịch chuyển tức thời đã đạt đến một tầm cao mới. Những con tàu thám hiểm giờ đây có thể thực hiện những bước nhảy không gian chỉ trong nháy mắt, miễn là tuyến đường chúng chọn không quá nguy hiểm.

Bạn được giao nhiệm vụ điều khiển một con tàu thám hiểm di chuyển trong không gian được biểu thị bởi một bản đồ dạng lưới hình chữ nhật có kích thước N × M. Các hàng được đánh số thứ tự từ 1 đến N, các cột được đánh số thứ tự từ 1 đến M.

Ô (i, j) là ô ở hàng thứ i (1 ≤ i ≤ N) từ trên xuống dưới và cột thứ j (1 ≤ j ≤ M) từ trái sang phải trên bản đồ. Mỗi ô (i, j) biểu thị một vùng không gian, trong đó:

• Chứa giá trị 0 thì đó là vùng an toàn.
• Chứa giá trị 1 thì đó là vùng không an toàn.

Tàu thám hiểm của bạn bắt đầu xuất phát tại ô (1, 1) và cần di chuyển đến đích là ô (N, M). Cơ chế di chuyển của con tàu tuân theo 2 quy định như sau:

• Hướng di chuyển hợp lệ: Từ vị trí ở ô (x, y) hiện tại, con tàu có thể thực hiện một bước nhảy đến vị trí mới ở ô (u, v) theo hai hướng: hướng xuống dưới (u > x, v = y) hoặc hướng sang phải (u = x, v > y).
• Bước nhảy hợp lệ: Trong một bước nhảy của con tàu từ ô (x, y) đến ô (u, v) thì tổng số vùng không an toàn nằm trên đường đi (bao gồm cả ô (x, y)) không vượt quá giới hạn D, lúc này bước nhảy là hợp lệ. Nếu vượt quá giới hạn này thì con tàu sẽ bị xé vụn.

Yêu cầu: Hãy đếm số cách khác nhau để tàu có thể đi chuyển từ ô (1, 1) đến ô (N, M) theo cơ chế trên. Hai cách đi được xem là khác nhau nếu như có ít nhất một ô xuất hiện ở cách đi này nhưng không xuất hiện ở cách đi kia. Vì kết quả có thể rất lớn, hãy lấy phần dư của nó khi chia cho 10⁹ + 7.

Dữ liệu vào: Đọc từ tệp văn bản JUMP.INP có cấu trúc như sau:

• Dòng 1: Chứa ba số nguyên N, M, D (1 ≤ N × M ≤ 10⁶, D ≥ 0), tương ứng lần lượt là số hàng, số cột của bản đồ và giới hạn D; các giá trị được ghi cách nhau một dấu cách.
• N dòng tiếp theo, mỗi dòng chứa một xâu gồm M kí tự ‘0’ hoặc ‘1’ mô tả bản đồ lưới.

Kết quả: Ghi ra tệp văn bản JUMP.OUT theo cấu trúc:

• Dòng 1: Ghi số nguyên t là kết quả của bài toán.

Ví dụ:

JUMP.INP	JUMP.OUT	Giải thích
2 3 1 101 010	4	Các cách di chuyển từ ô (1,1) đến ô (2,3): - Cách 1: (1,1) → (2,1) → (2,2) → (2,3) - Cách 2: (1,1) → (2,1) → (2,3) - Cách 3: (1,1) → (1,2) → (2,2) → (2,3) - Cách 4: (1,1) → (1,2) → (1,3) → (2,3)

Ràng buộc:

• Có 40% số test tương ứng với 40% số điểm: 1 ≤ N × M ≤ 5 × 10³;
• Có 30% số test tương ứng với 30% số điểm: D = 0;
• Có 30% số test tương ứng với 30% số điểm: không có ràng buộc gì thêm.

---

Hết