Đề thi chọn HSG cho đội tuyển quốc gia môn Pascal (CT)

Sở Gd&Đt Nghệ an
Kỳ thi chọn đội tuyển dự thi hsg quốc gia lớp 12
Năm học 2006 - 2007


Môn thi: tin học
Thời gian 180 phút( Không kể thời gian giao đề)
Ngày thi: 07/11/2006
(Đề thi này có 2 trang)

BÀI 1: QUẢNG CÁO
Trong một siêu thị, các quảng cáo về các mặt hàng mới được phát liên tục qua loa phóng thanh. Để sắp xếp được một lịch quảng cáo tối ưu, ban lãnh đạo siêu thị đã tiến hành điều tra khách hàng và biết được hàng ngày mỗi khách hàng đến và rời siêu thị vào những thời điểm nào. Siêu thị muốn tiến hành quảng cáo sao cho mỗi khách hàng khi đến siêu thị nghe được không dưới 2 quảng cáo trong thời gian khách hàng đó ở trong siêu thị. Đồng thời hai quảng cáo bất kỳ không được phát đồng thời và số lượng quảng cáo trong một ngày là nhỏ nhất. Các quảng cáo được bắt đầu phát và kết thúc vào thời điểm là các số nguyên. Khi một khách hàng đến siêu thị hoặc rời siêu thị vào đúng thời điểm bắt đầu phát quảng cáo thì có thể xem như khách hàng đó nghe được quảng cáo đó.
Yêu cầu: Tìm một lịch phát quảng cáo thoả mãn tất cả các yêu cầu trên.
Dữ liệu vào: Cho trong tệp văn bản QC.INP có cấu trúc:
Dòng đầu chứa số nguyên dương N ( 3000 là số lượng khách hàng đến siêu thị trong vòng một ngày.
N dòng tiếp theo, mỗi dòng chứa cặp số nguyên dương A và B là thời điểm đến và rời khỏi siêu thị của một khách hàng.(A, B trong phạm vi longint).
Kết quả: Ghi ra tệp văn bản QC.OUTnhư sau:
Dòng đầu ghi số lượng quảng cáo sẽ phát trong ngày.
Các dòng tiếp theo ghi thời điểm lần lượt phát các quảng cáo theo thứ tự tăng.
(Chỉ cần đưa ra một đáp án).
Ví dụ:
QC.INP
 QC.OUT

5
1 10 10 12 1 10 1 10 23 24
5 5 10 12 23 24



BÀI 2: TRẠM CỨU HOẢ
Một mạng giao thông có N nút đánh số từ 1 đến N, giữa một số cặp nút có đường đi hai chiều và mạng liên thông. Hiện nay toàn bộ hệ thống đường rất xấu. Cần chọn một nút đặt trạm cứu hoả và một số đoạn đường để nâng cấp sao cho với hệ thống chỉ gồm những đoạn đường được nâng cấp, từ trạm cứu hoả đến mỗi nút có đúng một đường đi và khoảng cách từ nút xa trạm nhất đến trạm là nhỏ nhất có thể được.
Dữ liệu vào: Được cho bởi file văn bản CH.INP trong đó:
Dòng thứ nhất ghi số nguyên dương N(N(200).
Trong một số dòng tiếp theo, mỗi dòng ghi ba số nguyên dương U, V, W với ý nghĩa có đường hai chiều nối nút U với nút V dài W(W(10000).
Kết quả: Ghi ra file văn bản CH.OUT như sau:
Dòng thứ nhất ghi tên nút đặt trạm cứu hoả.
Dòng thứ hai ghi khoảng cách từ nút xa nhất đến trạm.
Tiếp theo là một số dòng, mỗi dòng ghi hai nút đầu mút của một đoạn đường cần nâng cấp.
Ví dụ:
CH.INP
CH.OUT

5
1 2 50
1 3 30
1 4 100
1 5 10
2 3 5
2 4 20
3 4 50
4 5 10
4
25
1 5
2 3
2 4
4 5




BÀI 3: NHỮNG DẤU NGOẶC
Chúng ta gọi một xâu S là dãy ngoặc đúng nếu nó chỉ gồm các kí tự ‘{‘, }’, ‘[‘, ‘]’, ‘(‘, ‘)’ và thõa mãn một trong ba điều kiện sau:
1. S là xâu rỗng.
2. S có thể biểu diễn dưới dạng S = S1+S2+ ... +SN (N>1), với Si(1( i (N)là các dãy ngoặc đúng không rỗng, còn dấu ‘+’ là các kí hiệu nối các dãy (concat).
3. S có thể biểu diễn dưới dạng S = ‘{’+C +‘}’ hoặc S = ‘[’+C+‘]’ hoặc S = ‘(’+C+‘)’, ở đây C là dãy ngoặc đúng.
Cho trước một xâu S chỉ gồm các kí tự ‘{‘, }’, ‘[‘, ‘]’, ‘(‘, ‘)’.
Yêu cầu: Xác định số ít nhất các kí tự cần phải đặt thêm vào S để nó trở thành dãy ngoặc đúng.
Dữ liệu: Vào từ file văn bản NGOAC.INP có cấu trúc:
Dòng duy nhất của File, ghi một xâu S chỉ gồm