Chọn đội tuyển HSG quốc gia Sơn La 2025-2026

SỞ GD&ĐT TỈNH SƠN LA ĐỀ CHÍNH THỨC
(Ngày 1: 02 trang, ngày 2: 03 trang)

KỲ THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI QUỐC GIA Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi: 13/9/2025 và 14/9/2025
Thời gian làm bài: 180 phút mỗi ngày (không kể thời gian phát đề)

---

Ngày thi thứ nhất (13/9/2025)

Bài	Tên bài	File mã nguồn	Nhập	Xuất	Điểm
Bài 1	Số may mắn	LUCKYID.*	LUCKYID.INP	LUCKYID.OUT	7,0
Bài 2	Rút gọn tên	RENAME.*	RENAME.INP	RENAME.OUT	7,0
Bài 3	Những người nổi tiếng	FAMOS.*	FAMOS.INP	FAMOS.OUT	6,0

Phần mở rộng * là: .cpp, .c hay .py đối với ngôn ngữ lập trình C++, C hay Python tương ứng.

Bài 1. Số may mắn (7,0 điểm)

Tại một quốc gia nọ, người ta quan niệm số may mắn là những số chỉ có các chữ số thuộc tập “6, 8”. Ví dụ các số 6, 8, 66, 668, 888 là những số may mắn, còn các số 678, 80, 608 thì không phải số may mắn.

Yêu cầu: Với n cho trước, hãy đếm số lượng số may mắn có không quá n chữ số.

Dữ liệu: Nhập từ tệp văn bản LUCKYID.INP gồm một số nguyên dương n (1 ≤ n ≤ 10¹⁸).

Kết quả: Ghi ra tệp văn bản LUCKYID.OUT một số nguyên duy nhất là số lượng số may mắn có không quá n chữ số. Do số lượng này có thể rất lớn nên chỉ ghi ra phần dư khi chia cho 10⁹ + 7.

Ví dụ:

LUCKYID.INP	LUCKYID.OUT	Giải thích
2	6	Có 6 số may mắn là 6, 8, 66, 68, 86, 88.
5	62

Giới hạn:

• Subtask #1: 50% số điểm của bài có 1 ≤ n ≤ 60;
• Subtask #2: 30% số điểm tiếp theo có 61 ≤ n ≤ 10⁶;
• Subtask #3: 20% số điểm còn lại không có ràng buộc bổ sung.

Bài 2. Rút gọn tên (7,0 điểm)

Tại một thời điểm trong tương lai, người ta nhận thấy việc đặt tên “dư thừa dữ liệu” khiến cho việc lưu trữ rất tốn kém. Một tên được cho là “dư thừa dữ liệu” nếu có tiền tố của nó xuất hiện bên trong nó (mà không phải vị trí đầu tiên). Ví dụ “abcabd” là tên dư thừa dữ liệu còn “cba” thì không. Với mỗi tên là một chuỗi ký tự s, người ta tiến hành “rút gọn” để trở thành tên không dư thừa dữ liệu theo quy tắc sau:

Ta tìm tiền tố dài nhất của s xuất hiện trong s (không phải vị trí đầu tiên), nếu tìm thấy thì sẽ xóa toàn bộ tiền tố đó, quá trình này lặp lại cho tới khi không còn tiền tố nào của s xuất hiện trong s (trừ vị trí đầu tiên).

Ví dụ: “abaabcba” → “aabcba” → “abcba” → “bcba” → “cba”.

Yêu cầu: Bạn được cho một tên là một chuỗi kí tự s khác rỗng, chỉ gồm các kí tự la-tin in thường, hãy rút gọn s để được tên không dư thừa dữ liệu.

Dữ liệu: Nhập từ tệp văn bản RENAME.INP gồm một dòng duy nhất chứa chuỗi kí tự s, khác rỗng, chỉ gồm các kí tự la-tin thường, độ dài không quá 10⁶.

Kết quả: Ghi ra tệp văn bản RENAME.OUT một dòng duy nhất chứa chuỗi kết quả.

Ví dụ:

RENAME.INP	RENAME.OUT	Giải thích
abcabc	abc	abcabc → abc
abaabcba	cba	abaabcba → aabcba → abcba → bcba → cba

Giới hạn:

• Subtask 1: 50% số điểm của bài có |s| ≤ 500;
• Subtask 2: 30% số điểm khác có |s| ≤ 5000;
• Subtask 3: 20% số điểm còn lại không có ràng buộc bổ sung.

Bài 3. Những người nổi tiếng (6,0 điểm)

Tí có một bộ sưu tập poster của những nhân vật nổi tiếng, mỗi nhân vật nổi tiếng được Tí đặt biệt danh là một số nguyên dương. Bộ sưu tập này có n tấm poster, trong đó, nhân vật nổi tiếng trên tấm poster thứ i có biệt danh là a_i. Thật không may, không phải tất cả những nhân vật nổi tiếng Tí đều yêu thích. Cụ thể, Tí chỉ yêu thích đúng m nhân vật nổi tiếng, đó là những người mà Tí đặt biệt danh là các số nguyên từ 1 đến m, những người còn lại thì Tí không yêu thích.

Gọi P_min là số lượng poster của nhân vật có ít poster nhất trong m nhân vật Tí yêu thích, Tí có thể đổi những tấm poster của nhân vật mình không yêu thích lấy những tấm poster của nhân vật mình yêu thích để làm tăng giá trị P_min với số lần đổi tùy ý.

Yêu cầu: Hãy tính P_min lớn nhất và số lần đổi poster ít nhất để đạt được giá trị P_min này.

Dữ liệu: Nhập từ tệp văn bản FAMOS.INP có cấu trúc như sau:

• Dòng đầu chứa hai số nguyên dương n, m là số tấm poster trong bộ sưu tập của Tí và số nhân vật nổi tiếng Tí yêu thích (1 ≤ m ≤ n ≤ 10⁶);
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n là biệt danh của các nhân vật nổi tiếng trên n tấm poster trong bộ sưu tập của Tí (1 ≤ a_i ≤ 10⁹, ∀i = 1..n).

Kết quả: Ghi ra tệp văn bản FAMOS.OUT một dòng chứa hai số nguyên là số P_min và số lần đổi poster ít nhất để đạt giá trị P_min đó.

Ví dụ:

FAMOS.INP	FAMOS.OUT	Giải thích
5 2 1 2 100 2 2	2 1	Tí đổi tấm poster số 3 thành poster của nhân vật số 1.
8 3 7 1 1 3 3 1 2 5	2 1	Tí đổi tấm poster số 1 thành poster của nhân vật số 2. Pmin lớn nhất là 2 với số lần đổi ít nhất là 1.

Giới hạn:

• Subtask #1: 60% số điểm của bài có 1 ≤ m ≤ n ≤ 1000;
• Subtask #2: 40% số điểm còn lại không có ràng buộc bổ sung.

Ngày thi thứ hai (14/9/2025)

Bài	Tên bài	File mã nguồn	Nhập	Xuất	Điểm
Bài 4	Bể cá cảnh	AQUARIUM.*	AQUARIUM.INP	AQUARIUM.OUT	7,0
Bài 5	Ánh sáng và hoa	FLIGHT.*	FLIGHT.INP	FLIGHT.OUT	7,0
Bài 6	Tự động hóa	AUTOMAT.*	AUTOMAT.INP	AUTOMAT.OUT	6,0

Phần mở rộng * là: .cpp, .c hay .py đối với ngôn ngữ lập trình C++, C hay Python tương ứng.

Bài 4. Bể cá cảnh (7,0 điểm)

Tí có một khối san hô mà mặt đáy được chia thành m × n ô vuông đơn vị (m hàng, n cột). Trên ô vuông ở hàng i cột j có cột san hô với chiều cao là một số nguyên h_ij. Tí sử dụng khối san hô này để thiết kế bể cá cảnh.

Tí chọn một số nguyên dương H rồi cắt 4 tấm kính hình chữ nhật (2 tấm có kích thước m × H và 2 tấm có kích thước n × H) để ghép bốn xung quanh khối san hô tạo thành bể cá có chiều cao H. Với bể cá này, khi đổ nước vào, mực nước cao tối đa là H. Những ô có h_ij ≥ H, thể tích nước bên trên nó bằng 0, những ô có h_ij < H, thể tích nước bên trên nó tối đa là H − h_ij. Như vậy, tổng thể tích nước tối đa của bể là:

V(H) = tổng của max(H − h_ij, 0) với mọi i = 1..m, j = 1..n.

Yêu cầu: Cho trước số nguyên dương X, hãy tìm chiều cao tối thiểu H để V(H) ≥ X.

Dữ liệu: Nhập từ tệp văn bản AQUARIUM.INP có cấu trúc như sau:

• Dòng đầu chứa ba số nguyên m, n, X (1 ≤ m, n ≤ 10⁶, m × n ≤ 10⁶, 1 ≤ X ≤ 10¹⁸);
• Dòng thứ i trong m dòng tiếp theo chứa n số nguyên h_i1, h_i2, …, h_in (1 ≤ h_ij ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản AQUARIUM.OUT một số nguyên H nhỏ nhất mà V(H) ≥ X.

Ví dụ:

AQUARIUM.INP	AQUARIUM.OUT	Giải thích
2 3 10 1 4 6 2 1 3	5	Với H = 4 sẽ có V(4) = 9. Với H = 5 sẽ có V(5) = 14. Vậy số H nhỏ nhất là 5.

Giới hạn:

• Subtask #1: 50% số điểm của bài có 1 ≤ m, n ≤ 100, h_ij ≤ 1000, X ≤ 10⁶;
• Subtask #2: 30% số điểm tiếp theo có 1 ≤ m, n ≤ 1000, h_ij ≤ 10⁶, X ≤ 10⁹;
• Subtask #3: 20% số điểm còn lại không có ràng buộc bổ sung.

Bài 5. Ánh sáng và hoa (7,0 điểm)

Theo kế hoạch kỷ niệm 130 năm thành lập Tỉnh (1895-2025), Sơn La đang tiến hành trang trí đô thị bằng cách, dọc tuyến đường quốc lộ 6 lên Sơn La, công ty đô thị đề xuất n địa điểm trang trí, tại địa điểm thứ i sẽ trồng một bồn hoa với độ đẹp là b_i và lắp đèn chiếu sáng với độ sáng l_i. Các địa điểm được đánh số từ 1 đến n.

Để tuyến đường được lung linh rực rỡ, tập thể lãnh đạo tỉnh muốn lựa chọn một danh sách các địa điểm (trong danh sách n địa điểm đã được đề xuất) sao cho với danh sách này thì độ sáng của các đèn chiếu sáng tăng dần và tổng độ đẹp của các bồn hoa là lớn nhất. Cụ thể, nếu ta chọn danh sách k địa điểm 1 ≤ i₁ < i₂ < … < i_k ≤ n thì l(i₁) < l(i₂) < … < l(i_k) và b(i₁) + b(i₂) + … + b(i_k) đạt giá trị lớn nhất.

Yêu cầu: Hãy giúp lãnh đạo tỉnh lựa chọn được một danh sách địa điểm thỏa mãn điều kiện yêu cầu. Tính tổng độ đẹp của các bồn hoa trong danh sách được lựa chọn.

Dữ liệu: Nhập từ tệp văn bản FLIGHT.INP có cấu trúc như sau:

• Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 2 × 10⁵) là số vị trí được đề xuất;
• Dòng thứ hai chứa n số nguyên b₁, b₂, …, b_n (1 ≤ b_i ≤ 10⁹, ∀i = 1..n);
• Dòng thứ ba chứa n số nguyên l₁, l₂, …, l_n (1 ≤ l_i ≤ 10⁹, ∀i = 1..n).

Kết quả: Ghi ra tệp văn bản FLIGHT.OUT một dòng duy nhất chứa số nguyên là tổng độ đẹp của các bồn hoa trong danh sách được lựa chọn thỏa mãn điều kiện yêu cầu.

Ví dụ:

FLIGHT.INP	FLIGHT.OUT	Giải thích
5 1 1 1 1 2 1 3 2 5 4	4	Danh sách các vị trí tối ưu là 1, 2, 5 (hoặc 1, 3, 5). Tổng độ đẹp của các bồn hoa là 4 (lớn nhất).
3 3 1 1 3 1 2	3	Danh sách các vị trí tối ưu là 1. Tổng độ đẹp của các bồn hoa là 3 (nếu ta chọn danh sách địa điểm 2, 3 thì chỉ đạt được tổng độ đẹp các bồn hoa là 2).

Giới hạn:

• Subtask #1: 50% số điểm của bài có 1 ≤ n ≤ 2000;
• Subtask #2: 30% số điểm khác có 1 ≤ l_i ≤ 10⁶, ∀i = 1..n;
• Subtask #3: 20% số điểm còn lại không có ràng buộc bổ sung.

Bài 6. Tự động hóa (6,0 điểm)

Tí đang nghiên cứu phát triển một dây chuyền sản xuất điều khiển tự động bởi Robot. Dây chuyền gồm n máy xếp thành một hàng đánh số từ 1 đến n. Tại một thời điểm, mỗi máy có thể thực hiện một tác vụ độc lập trong K tác vụ và được ký hiệu bởi các số nguyên dương từ 0 đến K − 1, ta gọi đó là trạng thái của máy. Dãy trạng thái ban đầu của các máy là t₁, t₂, …, t_n (0 ≤ t_i < K, ∀i = 1..n).

Robot điều khiển dây chuyền thông qua các lệnh. Mỗi lệnh là một bộ bốn số nguyên l, r, x, y (1 ≤ l ≤ r ≤ n, 0 ≤ x, y < K) sẽ tác động lên các máy đang ở trạng thái x trong các máy có chỉ số từ l đến r, các máy này đồng loạt đổi sang trạng thái y, các máy khác không thay đổi. Robot đã điều khiển dây chuyền bằng q lệnh.

Yêu cầu: Cho biết trạng thái ban đầu của các máy và danh sách q lệnh của Robot, hãy xác định trạng thái cuối cùng của các máy sau q lệnh kể trên.

Dữ liệu: Nhập từ tệp văn bản AUTOMAT.INP có cấu trúc như sau:

• Dòng đầu chứa ba số nguyên dương n, K, q là số máy trong dây chuyền, số trạng thái và số lệnh điều khiển (1 ≤ n, q ≤ 2 × 10⁵; 2 ≤ K ≤ 20);
• Dòng thứ hai chứa n số nguyên t₁, t₂, …, t_n là trạng thái ban đầu của các máy theo đúng thứ tự (0 ≤ t_i < K, ∀i = 1..n);
• q dòng tiếp theo, mỗi dòng chứa bốn số nguyên l, r, x, y (1 ≤ l ≤ r ≤ n, 0 ≤ x, y < K) mô tả một lệnh điều khiển. Các lệnh điều khiển được thực thi theo đúng thứ tự.

Kết quả: Ghi ra tệp văn bản AUTOMAT.OUT một dòng chứa n số nguyên là dãy trạng thái cuối cùng của các máy sau khi thực thi q lệnh của Robot.

Ví dụ:

AUTOMAT.INP	AUTOMAT.OUT	Giải thích
5 5 3 0 1 2 3 4 1 3 1 2 2 4 2 3 2 5 4 0	0 3 3 3 0	Trạng thái các máy như sau: 0 1 2 3 4 (ban đầu) 0 2 2 3 4 (sau lệnh 1) 0 3 3 3 4 (sau lệnh 2) 0 3 3 3 0 (sau lệnh 3, trạng thái cuối cùng)
6 2 5 0 0 0 0 0 0 1 4 1 0 1 6 0 0 2 5 0 1 1 6 1 0 1 6 0 1	1 1 1 1 1 1	Trạng thái các máy như sau: 0 0 0 0 0 0 (ban đầu) 0 0 0 0 0 0 (sau lệnh 1) 0 0 0 0 0 0 (sau lệnh 2) 0 1 1 1 1 0 (sau lệnh 3) 0 0 0 0 0 0 (sau lệnh 4) 1 1 1 1 1 1 (sau lệnh 5, trạng thái cuối cùng)

Giới hạn:

• Subtask #1: 40% số điểm của bài có 1 ≤ n, q ≤ 5000;
• Subtask #2: 20% số điểm khác có K = 2;
• Subtask #3: 40% số điểm còn lại không có ràng buộc bổ sung.

---

Thí sinh không sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.