Đề thi chọn đội tuyển dự thi HSG quốc gia môn Tin học (Đề 2) - Năm học 2006-2007 - Sở GD&ĐT Nghệ An

 Đề chính thức
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
Bản chính
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 các kí tự‘{‘, }’, ‘[‘, ‘]’, ‘(‘, ‘)’. Đụ̣ dài của xõu khụng quá 100 kí tự.
Kết quả: Ghi ra file văn bản NGOAC.OUT như sau: 
Dòng đõ̀u tiờn ghi mụ̣t sụ́ nguyờn khụng õm là sụ́ ít nhṍt các kí tự cõ̀n phải đăt thờm vào xõu S đờ̉ nó trở thành dãy ngoặc đúng.
Vớ dụ:
NGOAC.INP
NGOAC.OUT
NGOAC.INP
NGOAC.OUT
{(})
2
([{}])
0
------------Hết------------
Hạn chế kỹ thuật: 
- Tất cỏc File dữ liệu vào ra của cỏc bài, cỏc số ghi trờn một dũng cỏch nhau một ký tự trắng
- Chương trỡnh giải cỏc bài 1, bài 2, bài 3 lần lượt ghi lờn đĩa với tờn BAI1.pas; BAI2.pas; BAI3.pas.
- Giỏm thị khụng phải giải thớch gỡ thờm.