HSG lớp 12 Nghệ An 2025-2026 (Bảng A)

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12 Năm học 2025 - 2026
Môn thi: Tin học - Bảng A (Phần lập trình)
Thời gian: 100 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Thời gian	Bộ nhớ
MÃ HÀNG HÓA	MAHANG.*	MAHANG.INP	MAHANG.OUT	1 giây	1024MB
NHIÊN LIỆU	NHIENLIEU.*	NHIENLIEU.INP	NHIENLIEU.OUT	1 giây	1024MB
HOA ĐẸP	HOADEP.*	HOADEP.INP	HOADEP.OUT	1 giây	1024MB

Phần mở rộng .* được thay thế bằng Cpp, Py ứng với các ngôn ngữ lập trình C++, Python.

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

Câu 1. MÃ HÀNG HÓA (5.0 điểm)

Công ty X chuyên sản xuất các sản phẩm theo dây chuyền. Các sản phẩm khi đưa lên băng chuyền để hoàn thiện các công đoạn cuối sẽ được gắn một mã hàng để quản lí. Mã hàng của mỗi sản phẩm là một số tự nhiên chính là thứ tự của sản phẩm đó khi đưa lên băng chuyền. Do chưa kịp bảo dưỡng nên có hai công đoạn trên băng chuyền này không đảm bảo kỹ thuật. Trong đó, công đoạn thứ nhất cứ thực hiện trên a sản phẩm lại có một sản phẩm bị lỗi, công đoạn thứ 2 cứ thực hiện trên b sản phẩm lại có một sản phẩm bị lỗi. Vì vậy những sản phẩm có mã hàng chia hết cho a hoặc chia hết cho b đều bị lỗi nên hệ thống tự động loại ra các sản phẩm đó. Trong quá trình làm việc nhân viên trực ca muốn biết mã hàng của sản phẩm hoàn chỉnh đảm bảo chất lượng thứ N là bao nhiêu để theo dõi, giám sát.

Yêu cầu: Em hãy viết chương trình tìm mã hàng của sản phẩm hoàn thiện thứ N giúp nhân viên trực ca.

Dữ liệu vào: Từ tệp MAHANG.INP gồm một dòng chứa số 3 số nguyên dương a, b, N ngăn cách nhau bởi dấu cách (2 ≤ a, b ≤ 10⁹, 2 ≤ N ≤ 10¹⁸).

Kết quả: Ghi ra tệp MAHANG.OUT gồm một số nguyên duy nhất chứa mã số của sản phẩm thứ N cần tìm.

Ví dụ:

MAHANG.INP	MAHANG.OUT	Giải thích
2 5 10	23	Các sản phẩm hoàn chỉnh có mã số lần lượt là: 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, … Vậy mã sản phẩm thứ 10 có mã số 23

Giới hạn:

• Có 70% số test thoả mãn 2 ≤ N ≤ 10⁶;
• Có 30% số test thoả mãn 10⁶ < N ≤ 10¹⁸.

Câu 2. NHIÊN LIỆU (4.0 điểm)

Một công ty vận tải là khách hàng thường xuyên của công ty kinh doanh nhiên liệu. Công ty kinh doanh nhiên liệu đã công bố giá bán nhiên liệu của N ngày sắp tới là dãy giá trị a₁, a₂, …, a_N. Vì là khách hàng quen nên công ty vận tải được công ty kinh doanh nhiên liệu cho chính sách ưu đãi đặc biệt, như sau: Giá bán nhiên liệu ngày thứ i không lớn hơn giá bán các ngày trước đó. Như vậy nếu giá bán công bố ngày thứ i là aᵢ mà lớn hơn giá đã mua ở ngày thứ i−1 thì công ty vận tải sẽ được mua nhiên liệu ở ngày thứ i với giá đã mua ở ngày thứ i−1.

Để ước tính chi phí hoạt động, công ty vận tải đã đưa ra q truy vấn có dạng L, R, x có nghĩa là: Trong đoạn các ngày từ ngày thứ L đến ngày thứ R có bao nhiêu ngày được mua nhiên liệu với giá ưu đãi bằng x.

Em hãy lập trình giúp công ty vận tải trả lời q truy vấn này.

Yêu cầu: Hãy cho biết trong đoạn các ngày từ ngày thứ L đến ngày thứ R có bao nhiêu ngày mua nhiên liệu với giá ưu đãi bằng x?

Dữ liệu vào: Từ tệp NHIENLIEU.INP gồm các dòng:

• Dòng 1: số nguyên N (1 ≤ N ≤ 2*10⁵).
• Dòng 2: N số nguyên a₁, a₂, …, a_N (1 ≤ aᵢ ≤ 10⁶).
• Dòng 3: số nguyên q (1 ≤ q ≤ 2*10⁵).
• q dòng tiếp theo: ba số nguyên L, R, x (1 ≤ L, R ≤ N).

Kết quả: Ghi ra tệp NHIENLIEU.OUT gồm q dòng, mỗi dòng là kết quả của một truy vấn.

Ví dụ:

NHIENLIEU.INP	NHIENLIEU.OUT	Giải thích
8 12 15 10 11 9 20 8 8 3 3 7 8 5 8 12 2 5 10	1 0 2	• Dãy giá ban đầu: a = [12, 15, 10, 11, 9, 20, 8, 8] • Các truy vấn: ○ (3,7,8) → Từ ngày thứ 3 đến ngày thứ 7 có 1 ngày thứ 7 mua với giá ưu đãi bằng 8. ○ (5,8,12) → Từ ngày thứ 5 đến ngày thứ 8 không có ngày nào mua với giá ưu đãi bằng 12. ○ (2,5,10) → Từ ngày thứ 2 đến ngày thứ 5 có 2 ngày thứ 3 và ngày thứ 4 mua với giá ưu đãi bằng 10.

Giới hạn:

• Có 70% số test thoả mãn 1 ≤ N, q ≤ 10³;
• Có 30% số test thoả mãn 10³ < N, q ≤ 10⁶.

Câu 3. HOA ĐẸP (3.0 điểm)

Nhà Tuấn có một hàng N chậu hoa đơn sắc. Hàng ngày ngắm nhìn hoa, Tuấn thấy rằng nếu đặt các chậu hoa cùng màu về nằm cùng một phía (nửa trái hoặc nửa phải) của hàng thì sẽ rất đẹp. Tuấn muốn biết có bao nhiêu cách đưa hai chậu hoa bất kì về nằm cùng một phía để trở thành hàng đẹp.

Dãy màu các chậu hoa được biểu diễn thành một xâu S có độ dài chẵn N, mỗi màu là một kí tự latin thường hoặc in hoa, lần lượt được đánh chỉ số từ 1 đến N. Như vậy xâu S được gọi là xâu đẹp nếu tất cả các kí tự giống nhau của xâu S đều cùng nằm về nửa trái hoặc nửa phải. Ví dụ xâu “abcd”, “AbaB” là các xâu đẹp, còn “aaaa” hay “Bbba” thì không.

Hãy viết chương trình giúp Tuấn giải quyết bài toán trên.

Yêu cầu: Bạn phải thực hiện Q truy vấn, mỗi truy vấn gồm hai số nguyên dương x, y (1 ≤ x, y ≤ N). Đưa ra số lượng xâu T thỏa mãn:

• T là một hoán vị của S;
• T là một xâu đẹp;
• Kí tự Sₓ và Sᵧ phải nằm cùng về một phía (có thể trái hoặc phải) trong xâu T.

Dữ liệu vào: Từ tệp HOADEP.INP gồm nhiều dòng:

• Dòng đầu gồm xâu S có độ dài N (N ≤ 10⁵);
• Dòng thứ hai gồm một số nguyên dương Q (Q ≤ 10⁵);
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x, y (x, y ≤ N).

Kết quả: Ghi ra tệp HOADEP.OUT gồm Q dòng, mỗi dòng trả lời cho mỗi truy vấn chia lấy dư cho (10⁹+7).

Ví dụ:

HOADEP.INP	HOADEP.OUT	Giải thích
Abdb 2 1 3 1 2	4 0	Truy vấn 1, các xâu thỏa mãn là: Adbb, dAbb, bbAd, bbdA.

Giới hạn:

• 20% số test thỏa mãn Q = 1, 0 < N ≤ 10³;
• 80% số test thỏa mãn 1 < Q ≤ 10⁵, 0 < N ≤ 10⁵;