HSG lớp 12 Bình Định 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH ĐỀ CHÍNH THỨC
(Đề thi có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12 Khóa ngày: 22 - 10 - 2023
Môn thi: Tin học
Thời gian: 180 phút (không kể thời gian phát đề)

---

Tổng quan về đề thi

Tên bài	File chương trình	File dữ liệu vào	File kết quả	Biểu điểm
Bài 1. Nén số	COMPRESS.*	COMPRESS.INP	COMPRESS.OUT	6,0
Bài 2. Xâu con	DEPART.*	DEPART.INP	DEPART.OUT	7,0
Bài 3. Thu thập tài liệu	DOCUMENT.*	DOCUMENT.INP	DOCUMENT.OUT	7,0

Chú ý:

• Học sinh đặt tên file chương trình theo đúng quy định của từng bài, phần mở rộng * là PAS hay CPP tuỳ theo ngôn ngữ và môi trường lập trình Free Pascal hay C++.
• Không ghi bất kỳ thông tin cá nhân nào vào file bài làm (họ tên, số báo danh, ngày sinh, trường, các ký hiệu khác thường, …)
• File input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến file input và output.
• Không sử dụng các lệnh dừng chương trình làm ảnh hưởng đến thời gian xử lý khi chương trình được thực thi. Thời gian xử lý mỗi test không quá 01 giây.

Bài 1. Nén số

Phép nén của một số nguyên dương K là gán số đó thành số nguyên dương nhỏ nhất mà K không chia hết. Ví dụ phép nén số của 120 là 7, vì 7 là số nguyên dương nhỏ nhất mà 120 không chia hết. Độ nén của một số là số lượng phép nén để số đó thành số 2. Ví dụ số 120 ta có: 120 → 7 → 2 vậy độ nén của 120 là 2.

Yêu cầu: Cho hai số nguyên dương A, B (2 < A < B < 10¹⁸). Tính tổng độ nén của các số lớn hơn hoặc bằng A và nhỏ hơn hoặc bằng B.

Dữ liệu: vào từ file COMPRESS.INP, gồm một dòng duy nhất chứa hai số A và B.

Kết quả: ghi ra file COMPRESS.OUT gồm số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

COMPRESS.INP	COMPRESS.OUT	Giải thích
3 7	8	Độ nén của 3 là 1; Độ nén của 4 là 2; Độ nén của 5 là 1; Độ nén của 6 là 3; Độ nén của 7 là 1. Tổng độ nén là: 8

Ràng buộc: 60% số test tương ứng 60% số điểm của bài có B < 10⁶.

Bài 2. Xâu con

Cho tập S gồm n xâu S₁, S₂, …, S_n (|S_i| ≤ 100) và một xâu X (|X| ≤ 10⁵). Đếm số lượng cách tách X thành các xâu con liên tiếp sao cho các xâu con này đều thuộc tập S.

Dữ liệu: vào từ file DEPART.INP

• Dòng đầu chứa số nguyên dương n (n ≤ 10⁴).
• n dòng tiếp, dòng thứ i chứa xâu S_i.
• Dòng cuối cùng chứa xâu X.

Kết quả: Ghi ra DEPART.OUT số cách tìm được. Lấy số dư trong phép chia 1000000007.

Ví dụ:

DEPART.INP	DEPART.OUT
3 a b ab abab	4

Ràng buộc:

• 30% số test |X| ≤ 20, n ≤ 10
• 30% số test 20 < |X| < 10000, n ≤ 100

Bài 3. Thu thập tài liệu

James là một điệp viên đang nằm vùng tại cơ sở Drhead. Tại đây có n căn phòng bí mật đánh số thứ tự 1, 2, …, n. Để vào phòng thứ i cần có chìa khóa phòng đó hoặc phá cánh cửa với chi phí là c_i. Đồng thời, khi thiết kế các căn phòng, người ta tạo ra rất nhiều chìa khóa giấu tại một số phòng khác. James đã có được m thông tin về việc giấu chìa khóa. Thông tin thứ i gồm hai số nguyên dương u_i và v_i xác định có một chìa khóa mở phòng v_i được giấu trong phòng u_i. Một lần James được giao nhiệm vụ cần lấy đủ k tập tài liệu, tài liệu thứ i được đặt ở phòng p_i (1 ≤ p_i ≤ n với mọi i thuộc [1, k]).

Yêu cầu: Hãy xác định số tiền nhỏ nhất phải bỏ ra để James có thể lấy đủ k tập tài liệu.

Dữ liệu: vào từ file DOCUMENT.INP:

• Dòng đầu tiên chứa 3 số nguyên dương n, k, m (n ≤ 10⁵; m ≤ 2.10⁵; k ≤ 12);
• Dòng thứ hai chứa k số nguyên dương p₁, p₂, …, p_k (p_i ≤ n với mọi i thuộc [1, k]);
• Dòng thứ ba chứa n số nguyên dương c₁, c₂, …, c_n (c_i ≤ 10⁶ với mọi i thuộc [1, n]);
• m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương u_i, v_i xác định một chìa khóa mở phòng v_i được giấu trong phòng u_i (1 ≤ u_i, v_i ≤ n).

Kết quả: in ra file DOCUMENT.OUT một số nguyên dương duy nhất là số tiền ít nhất mà James phải bỏ ra để lấy đủ k tập tài liệu.

Ví dụ:

DOCUMENT.INP (ví dụ 1)	DOCUMENT.OUT	DOCUMENT.INP (ví dụ 2)	DOCUMENT.OUT
3 2 1 1 3 7 4 8 2 3	11	3 2 2 1 3 7 4 8 2 3 1 2	7

Giải thích: Trong cả 2 ví dụ, cần vào phòng 1 lấy tài liệu số 1, cần vào phòng 3 lấy tài liệu số 2. Cách thực hiện:

• Ví dụ 1: Phá cửa phòng 1 và phòng 2, sau đó lấy chìa khóa mở phòng 3.
• Ví dụ 2: Phá cửa phòng 1 lấy chìa khóa mở phòng 2, vào phòng 2 lấy chìa khóa mở phòng 3.

Ràng buộc:

• Subtask 1: Có 20% số test m = 0; n ≤ 15;
• Subtask 2: Có 20% số test khác n ≤ 15, m ≤ 50;
• Subtask 3: Có 30% số test khác m, n ≤ 2000;
• Subtask 4: Có 30% số test còn lại không có ràng buộc bổ sung.