Đề thi chọn học sinh giỏi cấp tỉnh - Môn Tin học 11

 1/3 
 SỞ GD&ĐT QUẢNG BÌNH KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH 
 ĐỀ THI CHÍNH THỨC NĂM HỌC 2017 - 2018 
 LỚP 11 – THPT 
 Môn thi: TIN HỌC 
SỐ BÁO DANH: ....................... (Khóa thi ngày 22 tháng 03 năm 2018) 
 Thời gian làm bài: 180 phút (không kể thời gian giao đề) 
Đề thi gồm 3 trang 
Sử dụng ngôn ngữ lập trình Pascal để lập trình giải các bài toán sau: 
Câu 1(3.0 điểm): Giải nén xâu UNZIP.PAS 
Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. 
Trong việc nén dữ liệu dạng văn bản, ta sử dụng một phương pháp đơn giản được mô 
tả thông qua ví dụ sau: với xâu ký tự: ‘aaaabbb’ sẽ được nén lại thành xâu ‘4a3b’. 
 Cho một xâu ký tự St1 gồm các ký tự thuộc tập 'a'..'z'. Gọi St là xâu nén của 
xâu St1 theo phương pháp được mô tả như trên. Xâu St gồm N (1 N 255) ký tự 
thuộc tập các ký tự: 'a'..'z', '0'..'9' 
Yêu cầu: Hãy giải nén xâu St để được xâu gốc St1. 
Dữ liệu vào: Cho trong file văn bản UNZIP.INP có cấu trúc như sau: 
- Dòng 1: Ghi xâu ký tự St. 
Dữ liệu ra: Ghi ra file văn bản UNZIP.OUT theo cấu trúc như sau: 
- Dòng 1: Ghi xâu St1 là xâu sau khi đã được giải nén. 
Ví dụ: 
UNZIP.INP UNZIP.OUT 
12a5bk2c aaaaaaaaaaaabbbbbkcc 
Câu 2 (3.0 điểm): Đường chạy địa hình ROUTE.PAS 
 Trong Đại hội thể thao Quốc tế, người ta dự định sẽ tổ chức một môn chạy bộ 
địa hình. Đường chạy địa hình là một đường khép kín, điểm bắt đầu cũng là điểm kết 
thúc. Đường chạy có độ dài N (mét), mỗi mét có một độ cao h (cm) so với mực nước 
biển. 
Yêu cầu: Hãy đếm số lượng đường bằng, số lượng đường dốc lên và số lượng đường 
dốc xuống của đường chạy địa hình, tính từ điểm xuất phát. 
Dữ liệu vào: Cho trong file văn bản ROUTE.INP có cấu trúc như sau: 
- Dòng 1: Ghi số nguyên dương N, là chiều dài của đường chạy địa hình. 
- Dòng 2: Ghi N số nguyên dương hi là độ cao của mét thứ i trên đường chạy địa 
hình. Các số được ghi cách nhau ít nhất một dấu cách (3 ≤ N ≤ 30000; 
1 ≤ hi ≤ 30000). 
Dữ liệu ra: Ghi ra file văn bản ROUTE.OUT theo cấu trúc như sau: 
- Dòng 1: Ghi ba số nguyên dương x y z, trong đó x là số lượng đoạn đường 
bằng, y là số lượng đoạn đường dốc lên, z là số lượng đoạn đường dốc xuống của 
đường chạy địa hình. Các số được ghi cách nhau ít nhất một dấu cách. 
 2/3 
Ví dụ: 
ROUTE.INP ROUTE.OUT 
6 2 1 2 
20 23 60 50 50 20 
Câu 3 (2.0 điểm): Chuổi kết nối CONNECT.PAS 
Cho một tập gồm M bộ ba các số nguyên dương và hai số nguyên dương A, B. 
Một chuỗi kết nối hai số A, B là dãy các bộ ba có dạng: A0 W0 A1, A1 W1 A2, A2 W2 A3, 
 , Ak-2 Wk-2 Ak-1, A k-1Wk-1 Ak . Thỏa mãn các điều kiện sau: 
1. A0=A 
2. Ak =B 
3. Với mỗi i, 0<i<k, hoặc Ai, Wi Ai+1 hoặc là Ai+1, Wi, Ai phải là các số bộ ba đã cho. 
Nếu tồn tại một chuỗi kết nối như vậy thì giá trị của chuỗi được tính bằng cách 
cộng các số Wi xuất hiện trong chuỗi. 
Yêu cầu: Tìm chuỗi kết nối hai số A, B có giá trị bé nhất. 
Dữ liệu vào: Ghi trong tệp văn bản CONNECT.INP có cấu trúc như sau: 
- Dòng 1: Ghi số M (M ≤ 4x106) và hai số A, B (1 ≤ A, B ≤ 32000). 
- M dòng tiếp theo: Mỗi dòng ghi bộ ba Xi Yi Zi (1 ≤ Xi,Yi,Zi ≤ 32000) các số 
nguyên dương. 
Dữ liệu ra: Ghi ra file văn bản CONNECT.OUT theo cấu trúc như sau: 
- Dòng 1: Ghi chữ YES hoặc NO cho biết có tồn tại chuỗi kết nối hai số A, B 
hay không. 
- Dòng 2: Nếu dòng đầu ghi YES thì dòng này chứa giá trị của chuỗi kết nối hai 
số A, B có giá trị bé nhất. Nếu dòng đầu ghi NO thì dòng này không tồn tại. 
Ví dụ: 
CONNECT.INP CONNECT.OUT 
9 1 11 
1 2 5 
5 2 6 
1 3 8 
8 1 11 
1 1 6 
10 1 6 
11 3 6 
11 4 8 
10 1 11 
YES 
3 
 3/3 
Câu 4 (2.0 điểm): Dãy chia hết SIGN.PAS 
Xét một dãy số nguyên A gồm N phần tử a1, a2, ..., aN. Viết dãy số đó theo thứ tự 
từ trái sang phải, sau đó đặt giữa mỗi cặp số cạnh nhau dấu cộng '+' hoặc trừ '-', khi 
đó ta thu được một biểu thức số học. Ta nói dãy số là chia hết cho K nếu tồn tại một 
cách đặt dấu để thu được biểu thức số học chia hết cho K. 
Yêu cầu: Hãy xác định dãy số đã cho có chia hết cho K hay không. 
Dữ liệu vào: Cho trong file văn bản SIGN.INP có cấu trúc như sau: 
- Dòng 1: Ghi hai số nguyên N và K (2 ≤ N ≤ 104, 2 ≤ K ≤ 1000). 
- Dòng 2: Ghi N số nguyên ai . Các số được ghi cách nhau ít nhất một dấu cách 
(0 < i < N, 0 < ai <10
4). 
Dữ liệu ra: Ghi ra file văn bản SIGN.OUT theo cấu trúc như sau: 
- Dòng 1: Ghi số 0 nếu không có cách đặt dấu phù hợp, ngược lại ghi số 1 tiếp 
đó ghi liền (không dùng dấu cách) một cách đặt dấu phù hợp tương ứng với các số 
hạng trong dãy chia hết cho K. 
Ví dụ: 
SIGN.INP SIGN.OUT SIGN.INP SIGN.OUT 
4 7 
1 2 3 5 
1-++ 4 6 
1 2 3 5 
0 
(Chú ý: Các chương trình thực hiện không quá 1 giây đối với tất cả các bộ dữ liệu vào) 
==HẾT==