HSG THPT Thanh Hóa 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Năm học 2024 - 2025
Môn thi: Tin học - THPT
Thời gian làm bài: 150 phút, không kể thời gian phát đề
(Đề thi có 4 trang, gồm 5 câu)

---

Tổng quan bài thi

Câu	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả ra
Câu 1	Chia hết	CAU1.*	CAU1.INP	CAU1.OUT
Câu 2	Dãy con	CAU2.*	CAU2.INP	CAU2.OUT
Câu 3	Mật mã	CAU3.*	CAU3.INP	CAU3.OUT
Câu 4	Sàn thi đấu	CAU4.*	CAU4.INP	CAU4.OUT
Câu 5	Ngăn xếp	CAU5.*	CAU5.INP	CAU5.OUT

Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Trong các tệp dữ liệu vào/ra, nếu dữ liệu trên cùng một dòng thì được cách nhau bởi ít nhất 1 dấu cách. Dấu (*) trong tên tệp chương trình biểu thị đuôi tệp tùy thuộc vào ngôn ngữ lập trình sử dụng là CPP hoặc PY.

Ghi chú

Bản chụp đề gốc khá mờ ở Câu 4 và Câu 5. Các chi tiết đã được đối chiếu với ví dụ của đề; riêng giới hạn N ở Câu 5 đọc được là 2.10⁵.

Câu 1. Chia hết (6 điểm)

Cho 3 số nguyên dương n, a, b.

Yêu cầu: Đếm số các số nguyên dương nhỏ hơn hoặc bằng n mà chia hết cho cả a và b.

Dữ liệu: Vào từ tệp văn bản CAU1.INP gồm một dòng duy nhất chứa ba số nguyên dương n, a, b (n, a, b ≤ 10¹⁸).

Kết quả: Ghi ra tệp văn bản CAU1.OUT một số duy nhất là kết quả tìm được.

Ví dụ:

CAU1.INP	CAU1.OUT
20 2 5	2

Câu 2. Dãy con (5 điểm)

Cho dãy A gồm n số nguyên a₁, a₂, …, a_n khác nhau đôi một.

Yêu cầu: Chia dãy A thành ít nhất các dãy con (có thể không liên tiếp) sao cho:

• Mỗi phần tử của dãy A thuộc một và chỉ một dãy con.
• Mỗi dãy con có thể có một phần tử hoặc nếu nhiều hơn một thì khi giữ nguyên trật tự như ở dãy ban đầu sẽ cho ta một dãy số tăng dần.
• Nếu hai số a_i, a_j bất kì (1 ≤ i < j ≤ n) thuộc cùng một dãy con thì mọi số a_k (k = 1..n) mà a_i < a_k < a_j cũng thuộc dãy con đó.

Dữ liệu: Vào từ tệp văn bản CAU2.INP gồm:

• Dòng đầu chứa số nguyên dương n (n ≤ 10⁵);
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹ với mọi i = 1..n).

Kết quả: Ghi ra tệp văn bản CAU2.OUT một số nguyên duy nhất là số dãy con ít nhất tìm được.

Ví dụ:

CAU2.INP	CAU2.OUT	Mô tả
5 2 4 1 5 3	3	Các dãy con lần lượt là: Dãy 1: 1 Dãy 2: 4, 5 Dãy 3: 2, 3

Ràng buộc:

• Có 40% số điểm có n ≤ 10³ và a_i ≤ n với mọi i = 1..n;
• Có 40% số điểm tiếp theo có n ≤ 10⁵ và a_i ≤ n với mọi i = 1..n;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

Câu 3. Mật mã (4 điểm)

Một tài liệu sau khi mã hóa thành một xâu kí tự S có độ dài m bao gồm các chữ cái tiếng Anh sẽ được gửi đi kèm theo với mật mã là một xâu kí tự T có độ dài n cũng gồm các chữ cái tiếng Anh.

Do đường truyền không ổn định nên khi gửi tài liệu, có thể một số kí tự của xâu S bị thay bằng kí tự *. Quá trình giải mã, người ta xét tất cả các xâu con liên tiếp độ dài n của S, gọi là: P₀, P₁, …, P_m-n.

Yêu cầu: Tính số các xâu P_i (i = 0..m − n) có thể là hoán vị của xâu T, nếu trong xâu P_i có chứa các kí tự * thì được phép thay mỗi kí tự * đó thành chữ cái tiếng Anh bất kì.

Dữ liệu: Vào từ tệp văn bản CAU3.INP gồm:

• Dòng đầu chứa hai số nguyên dương n, m (n ≤ 3.10³, m ≤ 3.10⁶);
• Dòng thứ hai chứa xâu kí tự T;
• Dòng thứ ba chứa xâu kí tự S.

Kết quả: Ghi ra tệp văn bản CAU3.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT
3 12 aab abcnbaabfkjd	2
3 4 abc a**c	2

Ràng buộc:

• Có 40% số điểm có: độ dài xâu S không quá 1000 và xâu S không chứa kí tự *;
• Có 40% số điểm tiếp theo có: xâu S không chứa kí tự *;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

Câu 4. Sàn thi đấu (3 điểm)

Sàn một nhà thi đấu là một hình chữ nhật kích thước m × n được chia thành lưới ô vuông đơn vị, các hàng được đánh số từ 1 tới m từ trên xuống và các cột được đánh số từ 1 tới n từ trái qua phải, ô nằm trên giao của hàng i và cột j được gọi là ô (i, j). Khi mới được xây dựng, tất cả các ô là ô trống và được coi là có độ cao bằng 0.

Trong quá trình sử dụng, nhà thi đấu đã tổ chức k sự kiện thể thao đánh số từ 1 tới k, ở sự kiện thứ p (p = 1..k) người ta trải thêm các tấm nệm vào tất cả các ô thuộc hình chữ nhật có góc trái trên là (x_p, y_p) và góc phải dưới là (u_p, v_p) và làm tăng độ cao của những ô này lên 1 đơn vị. Tức là bao gồm tất cả các ô (i, j) có x_p ≤ i ≤ u_p và y_p ≤ j ≤ v_p.

Sắp tới có cuộc thi trượt Patin tại nhà thi đấu. Vì các tấm nệm mềm không thích hợp cho môn thể thao này, Ban tổ chức muốn chọn một hình vuông có các cạnh song song với các cạnh sàn nhà và toàn bộ các ô bên trong hình vuông đó đều cao bằng nhau để đặt lên đó một tấm phủ cứng làm sân trượt Patin.

Yêu cầu: Tìm cạnh hình vuông lớn nhất mà Ban tổ chức có thể sử dụng như mô tả trên.

Dữ liệu: Vào từ tệp văn bản CAU4.INP gồm:

• Dòng đầu chứa 3 số nguyên dương m, n, k (m, n ≤ 2000, k ≤ 10⁵);
• Dòng thứ p trong k dòng tiếp theo ghi 4 số nguyên dương x_p, y_p, u_p, v_p (x_p ≤ u_p ≤ m, y_p ≤ v_p ≤ n với mọi p = 1..k).

Kết quả: Ghi ra tệp văn bản CAU4.OUT gồm một số nguyên duy nhất là cạnh hình vuông lớn nhất tìm được.

Ví dụ:

CAU4.INP	CAU4.OUT	Mô tả
6 6 4 2 2 3 6 2 2 6 3 2 4 4 5 4 2 6 4	3	Độ cao của sàn thi đấu thể hiện ở bảng dưới, các ô in đậm là hình vuông được chọn. 0 0 0 0 0 0 0 2 2 2 2 1 0 2 2 2 2 1 0 2 2 2 1 0 0 2 2 1 0 0 0 2 2 1 0 0

Ràng buộc:

• Có 40% số điểm có m, n, k ≤ 200;
• Có 30% số điểm tiếp theo có m, n ≤ 200;
• Có 30% số điểm còn lại không còn ràng buộc gì thêm.

Câu 5. Ngăn xếp (2 điểm)

Hà có N cuốn sách mới, đánh số từ 1 đến N, em sẽ xếp N cuốn sách này vào các ngăn xếp. Là một người rất nguyên tắc nên mỗi cuốn sách khi xếp vào (và lấy ra) đều sẽ được Hà thực hiện theo thứ tự xác định, cuốn thứ i có thứ tự xếp vào là a_i (i = 1..N). Mỗi lần lấy sách ra đọc, Hà cũng sẽ lấy cả N cuốn ra và cuốn thứ i có thứ tự lấy ra là b_i (i = 1..N).

Với hai cuốn sách thứ i, j khác nhau bất kì (i, j = 1..N) khi được xếp vào chung một ngăn xếp, nếu thứ tự xếp vào của cuốn i bé hơn thứ tự xếp vào của cuốn j thì thứ tự lấy ra của cuốn i phải lớn hơn thứ tự lấy ra của cuốn j (hoặc ngược lại). Tức là nếu a_i < a_j và b_i > b_j (hoặc a_i > a_j và b_i < b_j) thì hai cuốn i, j mới có thể xếp chung một ngăn xếp.

Yêu cầu: Tính số ngăn xếp ít nhất để Hà có thể xếp vào và lấy ra được N cuốn sách như mô tả trên.

Dữ liệu: Vào từ tệp văn bản CAU5.INP gồm:

• Dòng đầu chứa số nguyên dương T là số test (T ≤ 3);
• Tiếp theo là T test, mỗi test gồm:
  • Dòng đầu chứa số nguyên dương N (N ≤ 2.10⁵);
  • Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N (a_i ≤ N và khác nhau đôi một với mọi i = 1..N).
  • Dòng thứ ba chứa N số nguyên dương b₁, b₂, …, b_N (b_i ≤ N và khác nhau đôi một với mọi i = 1..N).

Kết quả: Ghi ra tệp văn bản CAU5.OUT gồm T dòng là kết quả của T test, mỗi test ghi ra một số nguyên là số ngăn xếp ít nhất tìm được.

Ví dụ:

CAU5.INP	CAU5.OUT
1 5 3 5 2 4 1 3 2 5 1 4	2

Ràng buộc:

• Có 30% số điểm có: T = 3 và số ngăn xếp ít nhất không quá 2;
• Có 30% số điểm tiếp theo có: T = 2 và N ≤ 10;
• Có 40% số điểm còn lại có: T = 1 và N > 10.

---

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