HSG lớp 12 Quảng Trị 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG TRỊ ĐỀ THI CHÍNH THỨC
(Đề thi gồm có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI VĂN HÓA LỚP 12 THPT Khóa ngày 19 tháng 9 năm 2023
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 về bài thi

	Tên tệp chương trình	Tên tệp INPUT	Tên tệp OUTPUT	Điểm
Câu 1	MATKHAU.*	MATKHAU.INP	MATKHAU.OUT	5
Câu 2	CHIAHET.*	CHIAHET.INP	CHIAHET.OUT	5
Câu 3	GIAXAU.*	GIAXAU.INP	GIAXAU.OUT	5
Câu 4	ROBOCON.*	ROBOCON.INP	ROBOCON.OUT	5

• Dấu * là CPP hoặc PAS hoặc PY;
• Thời gian thực hiện mỗi test của mỗi bài không quá 1 giây;
• Thí sinh tạo trên ổ đĩa D thư mục có tên là số báo danh của mình, làm bài và lưu vào thư mục vừa tạo. Ví dụ thí sinh có SBD là 15 sẽ tạo thư mục D:\15 và lưu bài làm vào thư mục này.

Câu 1. (5,0 điểm) Mật khẩu an toàn

Một xâu ký tự được coi là một mật khẩu “an toàn” nếu thỏa mãn:

• Có độ dài ít nhất bằng 6;
• Chứa ít nhất một chữ cái tiếng Anh in hoa (‘A’ .. ‘Z’);
• Chứa ít nhất một chữ cái tiếng Anh in thường (‘a’ .. ‘z’);
• Chứa ít nhất một chữ số thập phân (‘0’ .. ‘9’).

Yêu cầu: Cho một xâu S, hãy xác định số lượng xâu con của S là mật khẩu “an toàn”.

Dữ liệu vào: Từ tệp văn bản MATKHAU.INP, gồm một dòng chứa xâu ký tự S.

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

Ví dụ:

MATKHAU.INP	MATKHAU.OUT
12Aabcde	5
Ab12Ab12Ab	15

Ràng buộc:

• Có 50% số tests tương ứng với 50% số điểm: xâu S có độ dài không quá 500;
• Có 30% số tests tương ứng với 30% số điểm: xâu S có độ dài không quá 2 × 10⁴;
• Có 20% số tests tương ứng với 20% số điểm: xâu S có độ dài không quá 2 × 10⁶.

Câu 2. (5,0 điểm) Đếm số chia hết

Cho số nguyên dương K và m số nguyên dương a₁, a₂, …, a_m.

Yêu cầu: Hãy cho biết có bao nhiêu số nguyên dương chia hết cho ít nhất một số a_i (1 ≤ i ≤ m) và không lớn hơn K.

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

• Dòng đầu tiên chứa số nguyên K và m (1 ≤ K ≤ 10⁹; 1 ≤ m ≤ 15);
• Dòng tiếp theo chứa các số nguyên a_i (1 ≤ a_i ≤ 10⁹);
• Các số cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra tệp văn bản CHIAHET.OUT một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

CHIAHET.INP	CHIAHET.OUT
10 2 2 3	7
100 3 2 3 7	72

Ràng buộc:

• Có 30% số tests tương ứng với 30% số điểm: 1 ≤ K ≤ 10⁶, 1 ≤ m ≤ 2;
• Có 30% số tests tương ứng với 30% số điểm: 1 ≤ K ≤ 10⁶; 3 ≤ m ≤ 15;
• Có 40% số tests tương ứng với 40% số điểm: các trường hợp còn lại.

Câu 3. (5,0 điểm) Giá trị của xâu

Giá trị của một xâu chỉ gồm các chữ cái in thường trong bảng chữ cái tiếng Anh được tính bằng tổng các giá trị i² × v(s_i) với 1 ≤ i ≤ |s|. Trong đó: |s| là độ dài xâu s, s_i là ký tự thứ i của xâu s, v(s_i) là vị trí của ký tự s_i trong bảng chữ cái.

Ví dụ: Giá trị của xâu s = “abca” sẽ được tính như sau:

• Với i = 1, ta có 1² × v(s₁) = 1² × 1 = 1.
• Với i = 2, ta có 2² × v(s₂) = 2² × 2 = 8.
• Với i = 3, ta có 3² × v(s₃) = 3² × 3 = 27.
• Với i = 4, ta có 4² × v(s₄) = 4² × 1 = 16.

Vậy giá trị của xâu s bằng 1 + 8 + 27 + 16 = 52.

Yêu cầu: Cho xâu t chỉ gồm các chữ cái in thường trong bảng chữ cái tiếng Anh, hãy tính tổng giá trị của tất cả các xâu con của xâu t.

Dữ liệu vào: Từ tệp văn bản GIAXAU.INP gồm một dòng duy nhất chứa xâu t có độ dài không quá 2 × 10⁵.

Kết quả: Ghi ra tệp văn bản GIAXAU.OUT là tổng giá trị các xâu con của t. Vì kết quả có thể rất lớn nên chỉ cần in ra kết quả sau khi đã chia lấy dư cho 10⁹ + 7.

Ví dụ:

GIAXAU.INP	GIAXAU.OUT	Giải thích
abc	65	- Các xâu con “a”, “b”, “c” có giá trị lần lượt là 1, 2, 3. - Các xâu con “ab”, “bc” có giá trị lần lượt là 9, 14. - Xâu “abc” có giá trị là 36. Vậy tổng giá trị các xâu con là 65.

Ràng buộc:

• Có 40% số tests tương ứng với 40% số điểm: độ dài xâu t không vượt quá 500;
• Có 30% số tests tương ứng với 30% số điểm: độ dài xâu t không vượt quá 5000;
• Có 30% số test tương ứng với 30% số điểm: độ dài xâu t không vượt quá 2 × 10⁵.

Câu 4. (5,0 điểm) Robocon

Nhằm tăng cường các hoạt động giáo dục STEM, nhà trường tổ chức một trò chơi Robocon dành cho các nhóm học sinh đam mê công nghệ. Ban tổ chức trò chơi đặt ra luật chơi như sau: Có một lưới ô vuông kích thước m × n, các hàng được đánh số từ 1 đến m từ trên xuống dưới và các cột được đánh số từ 1 đến n từ trái qua phải; ô nằm ở giao của hàng i và cột j ký hiệu là (i, j). Để thắng trong trò chơi, đội chơi sẽ phải điều khiển con robot của mình di chuyển qua các ô trên lưới, xuất phát từ ô (1, 1) và đích đến là ô (m, n). Mỗi bước đi nó chỉ có thể di chuyển đến ô chung cạnh ở bên phải hoặc bên dưới, cụ thể là từ ô (i, j) robot có thể di chuyển đến ô (i, j + 1) hoặc ô (i + 1, j). Để tăng độ khó của trò chơi, Ban tổ chức bố trí trên một số ô các vật cản buộc robot không đi vào các ô này.

Nam cùng các bạn trong nhóm tham gia trò chơi và muốn thắng trong trò chơi này, vì vậy Nam cần phải tính toán để xác định các hành trình có thể đưa robot về đích.

Yêu cầu: Hãy lập trình xác định số các hành trình khác nhau của robot để giúp nhóm của Nam thắng cuộc. Hai hành trình được xem là khác nhau nếu như có ít nhất một ô có trên hành trình này nhưng không có trên hành trình kia.

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

• Dòng đầu tiên chứa ba số nguyên dương m, n, k với m, n lần lượt là số hàng và số cột của lưới; k là số lượng ô có vật cản (1 ≤ m, n ≤ 10⁵; 0 ≤ k ≤ 2000);
• Trong k dòng tiếp theo, dòng thứ i chứa hai số nguyên h_i, c_i thể hiện ô (h_i, c_i) chứa vật cản (1 ≤ h_i ≤ m; 1 ≤ c_i ≤ n);
• Các số cùng dòng cách nhau ít nhất một dấu cách.

Dữ liệu đảm bảo rằng các ô (1, 1) và (m, n) không chứa vật cản.

Kết quả: Ghi ra tệp văn bản ROBOCON.OUT gồm một dòng chứa số nguyên duy nhất là số lượng các hành trình theo yêu cầu của bài toán. Vì số này có thể rất lớn nên chỉ in ra phần dư của nó khi chia cho 10⁹ + 7.

Ví dụ:

ROBOCON.INP	ROBOCON.OUT
3 3 2 1 2 3 1	2

Giải thích:

• Các ô chứa dấu “X” chỉ vị trí đặt vật cản.
• Các hành trình có thể di chuyển theo hướng mũi tên.

Ràng buộc:

• Có 40% số tests tương ứng với 40% số điểm: 1 ≤ m, n, k ≤ 1000;
• Có 20% số tests tương ứng với 20% số điểm: k = 0; 10⁴ ≤ m, n ≤ 10⁵;
• Có 20% số tests tương ứng với 20% số điểm: k = 1; 10⁴ ≤ m, n ≤ 10⁵;
• Có 20% số tests tương ứng với 20% số điểm: 1 ≤ k ≤ 2000; 10⁴ ≤ m, n ≤ 10⁵.