SỞ GD&ĐT QUẢNG BÌNH KÌ THI CHỌN HSG TỈNH NĂM HỌC 2014-2015
Khóa thi ngày 17 - 3 - 2015
ĐỀ CHÍNH THỨC Môn: Tin học
LỚP 12 THPT
Họ và tên: ………………………….. Thời gian: 180 phút (không kể thời gian giao đề)
Số báo danh: ………..…………….... Đề gồm có 02 trang

ĐỀ RA
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:
Bài 1: (3.0 điểm) Chuẩn hóa xâu XAU.PAS
Một xâu được gọi là xâu chuẩn nếu thỏa mãn các yêu cầu sau:
Không có ký tự cách trống ở đầu xâu.
Không có ký tự cách trống ở cuối xâu.
Không có hai ký tự cách trống liền nhau.
Để quản lý học sinh trong trường bằng máy vi tính, nhà trường yêu cầu các giáo viên chủ nhiệm nộp cho văn phòng file dữ liệu chứa danh sách họ tên học sinh trong lớp mình phụ trách. Sau khi tập hợp danh sách các lớp, văn phòng nhà trường phát hiện họ tên của rất nhiều học sinh chưa được chuẩn hóa. Bạn hãy giúp văn phòng nhà trường chuẩn hóa các xâu họ tên trong file dữ liệu.
Dữ liệu vào: Cho trong file văn bản XAU.INP với cấu trúc.
- Dòng 1: Ghi số nguyên dương N, là số lượng học sinh trong trường. (1<=N<=1500)
- N dòng tiếp theo: Mỗi dòng chứa một xâu họ tên học sinh với độ dài không quá 50 ký tự, các ký tự được lấy trong tập ‘a’...‘z’; ‘A’...‘Z’ và dấu cách trống.
Dữ liệu ra: Ghi trong file văn bản XAU.OUT với cấu trúc.
- Ghi trên N dòng: Mỗi dòng ghi một xâu họ tên đã chuẩn hóa theo đúng thứ tự vào.
Ví dụ:
XAU.INP
XAU.OUT

3
Nguyen Van An
Hoang Tuan Anh
Tran Van Truong
Nguyen Tuan Anh
Hoang Tuan Anh
Tran Van Truong


Bài 2: (3.5 điểm) Sắp xếp dãy số SAPXEP.PAS
Dãy số A được gọi là dãy tăng nếu A1< A2< A3<..... AN
Cho dãy số nguyên A1, A2, A3,.....,AN đôi một khác nhau.
Yêu cầu: Hãy sắp xếp dãy số thành một dãy tăng.
Dữ liệu vào: Cho trong file văn bản SAPXEP.INP với cấu trúc.
- Dòng 1: Ghi số nguyên dương N, là số lượng phần tử của dãy số. (1<=N<=60000)
- Dòng 2: Ghi N số nguyên Ai là giá trị của các phần tử của dãy, các số được ghi cách nhau ít nhất một dấu cách (0Dữ liệu ra: Ghi trong file văn bản SAPXEP.OUT với cấu trúc.
- Dòng 1: Ghi N số nguyên Ai sau khi đã được sắp xếp, các số được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
SAPXEP.INP
SAPXEP.OUT

5
7 6 8 4 9
4 6 7 8 9


Bài 3: (3.5 điểm): Phần thưởng PT.PAS
Trong buổi gặp mặt trước kỳ thi học sinh giỏi tỉnh năm 2015, để động viên đội tuyển học sinh giỏi của trường thầy hiệu trưởng sẽ trao cho đội tuyển học sinh giỏi các món quà được giấu trong các căn phòng của một tòa tháp (Đỉnh của tòa tháp chỉ có một phòng và cứ đi xuống một tầng thì số phòng lại tăng lên một, như hình vẽ), mỗi phòng chứa i món quà. Để nhận được các món quà thì cần một học sinh đi từ phòng ở đỉnh của tòa tháp lần lượt đi xuống một phòng ở tầng dưới của tòa tháp cho đến tầng dưới cùng. Mỗi lần đi xuống tầng dưới chỉ được vào một phòng kề với nó. Bạn hãy giúp cho đội tuyển học sinh giỏi của trường tìm ra phương án đi để nhận được nhiều món quà nhất.
Ví dụ: Với tòa tháp có độ cao bằng 4 và số lượng các món quà trong các phòng dưới đây thì bạn phải vào các phòng sau để tìm được số lượng món quà là lớn nhất.
Dữ liệu vào: Cho trong file văn bản PHANTHUONG.INP với cấu trúc.
- Dòng 1: Chứa số nguyên dương N là số tầng của tòa tháp (0- Dòng thứ i trong N dòng tiếp theo: Mỗi dòng ghi i số nguyên dương Ai là số món quà tròng mỗi phòng từ đỉnh của tòa tháp xuống (1Dữ liệu ra: Ghi ra