Tài liệu Đề thi tin học trẻ không chuyên cấp THPT tỉnh Quảng Bình năm 2009

HỘI THI TIN HỌC TRẺ TỈNH QUẢNG BÌNH LẦN THỨ X​ ĐỀ THI CHÍNH THỨC - BẢNG C - THPT​ Ngày thi 15/07/2009. Thời gian làm bài 150 phút​ ​
Lưu ý:
+ Đề thi này có 02 trang.
+ Học sinh tạo một thư mục có tên là số báo danh của thí sinh và lưu bài thi vào thư mục này.
+ Thí sinh không được sử dụng tài liệu khi làm bài.
+Cán bộ coi thi không giải thích gì thêm.
​ Sử dụng ngôn ngữ lập trình Turbo 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 Tên file chương trình: GNENXAU.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 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í dụ: Với xâu ký tự: ‘aaaabbb’ sẽ được nén lại thành xâu ‘4a3b’.
Với xâu ký tự ‘aaab’ sẽ được nén lại thành xâu ‘3ab’.
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 GNENXAU.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 GNENXAU.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ụ:
GNENXAU.INP​ GNENXAU.OUT​ 3a5bc
aaabbbbbc
​
Câu 2: (3,5 điểm) Thuê vị trí đặt biển quảng cáo. Tên file chương trình: QC.PAS
Trung tâm hoạt động Thanh thiếu nhi Bắc Trung Bộ đóng ở một vị trí khá đẹp. Nhiều công ty muốn thuê vị trí để đặt biển quảng cáo. Tại thời điểm hiện tại, chỉ còn duy nhất một chỗ có thể đặt được biển quảng cáo. Giám đốc Trung tâm không đưa ra cụ thể giá thuê mà để khách tự đăng kí. Ông phát cho mỗi khách hàng một phiếu. Khách hàng thứ i phải đăng kí thời điểm bắt đầu thuê (bi), thời gian thuê (ti) và số tiền (mi) mà họ phải trả trong toàn bộ thời gian đó.
Đến nay, Giám đốc Trung tâm đã nhận được N phiếu đăng kí thuê (được đánh số từ 1 đến N). Tuy nhiên, ông ta chưa biết nên chọn những khách hàng nào để có được lợi nhuận lớn nhất. Nhân dịp Hội thi Tin học trẻ Quảng Bình lần thứ X, Giám đốc Trung tâm muốn nhờ các thí sinh chọn giúp. Ông hứa sẽ trao thưởng cho thí sinh nào có phương án lựa chọn tốt nhất.
Yêu cầu: Hãy giúp Giám đốc Trung tâm xác định cần hợp đồng với những khách hàng nào để số tiền thu được là lớn nhất. Dĩ nhiên, khoảng thời gian thuê của những khách hàng được chọn để làm hợp đồng không được giao nhau (kể cả điểm mút).
Dữ liệu vào: Cho trong file văn bản QC.INP có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương N là số phiếu đăng kí thuê. (1 ≤ N ≤ 1000)
Trong N dòng tiếp theo: Mỗi dòng ghi 3 số nguyên dương bi ti mi lần lượt là thời điểm bắt đầu thuê, thời gian thuê, số tiền phải trả của khách hàng thứ i (i=1 N). Các số được ghi cách nhau ít nhất một dấu cách. (1 ≤ bi ti mi ≤ 32767)
Dữ liệu ra: Ghi ra file văn bản QC.OUT theo cấu trúc như sau:
Dòng 1: Ghi hai số nguyên dương h và p lần lượt là số lượng hợp đồng phải kí và tổng số tiền thu được từ những hợp đồng này. (Biết rằng: 1 ≤ p ≤ 2100000000)
Dòng 2: Ghi chỉ số các khách hàng mà Giám đốc Trung tâm đồng ý cho thuê để thu được số tiền trên.
Ví dụ:
QC.INP​ QC.OUT​ 3
20 40 50
60 20 40
61 30 30
2 80
1 3
​
Câu 3: (3,5 điểm) Xóa số Tên file chương trình: XOASO.PAS
Cho một số nguyên dương N gồm có M chữ số. (1 M 200).

Yêu cầu: Xóa đi K chữ số trong N để thu được số N’ sao cho N’ có giá trị nhỏ nhất. (K M).

Dữ liệu vào: Cho trong file văn bản XOASO.INP có cấu trúc như sau:
Dòng 1: Ghi số hai số nguyên dương N K. Hai số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản XOASO.OUT theo cấu trúc như sau:
Dòng 1: Ghi số N’ tìm được. (Vẫn giữ các chữ số 0 ở đầu số nếu có)
Ví dụ:
XOASO.INP​ XOASO.OUT​ XOASO.INP​ XOASO.OUT​ 123952 2
1232
95002 2
002
​
====== HẾT ======​