đề thi gvg tinh 2011-2015-LTrinh

SỞ GD&ĐT NGHỆ AN




(Đề thi gồm 02 trang)
 HỘI THI GIÁO VIÊN DẠY GIỎI BẬC THPT
CHU KỲ 2011 – 2015

Môn thi: TIN HỌC (Phần lập trình)
Thời gian làm bài 120 phút ( không kể thời gian giao đề)




Bài 1 (5,5 điểm). trạm tiếp nước ngọt
Tại một khu công nghiệp có N chung cư (1<=N<=100) và được gắn số hiệu lần lượt theo thứ tự từ 1, 2, ..., N. Hàng ngày, công ty cấp thoát nước vận chuyển cấp cho mỗi chung cư một xe nước.
Yêu cầu: Tìm cho công ty cấp thoát nước một địa điểm đtrạm tiếp nước cho N chung cư này thoả mãn các yêu cầu sau:
Tại một chung cư nào đó. Khi vận chuyển nước từ trạm đến một chung cư nào đó thì không được đi qua một chung cư trung gian nào.
Tổng chi phí vận chuyển là nhỏ nhất.
Dữ liệu: Vào cho từ văn bản NUOC.INP có cấu trúc như sau:
Dòng đầu tiên ghi số N
Các dòng tiếp theo ghi 3 số nguyên dương X, Y, CXY có nghĩa là chi phí vận chuyển một xe nước từ chung cư có số hiệu X đến chung cư có số hiệu Y là CXY (1<= X, Y<= N, 0 < CXY <= 32000) (các số trên một dòng ghi cách nhau một dấu cách)
Kết quả: Ghi ra file văn bản NUOC.OUT như sau:
Dòng đầu tiên ghi số hiệu của chung cư đặt trạm tiếp nước (nếu có nhiều địa điểm đặt trạm, thì chọn chung cư có số hiệu nhỏ nhất)
Dòng thứ hai ghi tổng chi phí vận chuyển nước đến N chung cư của khu công nghiệp này.
Ví dụ:
NUOC.INP
NUOC.OUT

5
1 2 12
1 3 10
1 4 7
1 5 5
2 3 11
2 4 8
2 5 7
3 4 3
3 5 9
4 5 7
4
25


Bài 2 (5,5 điểm). Ghép xâu
Cho 2 xâu ký tự S1, S2. Có thể ghép một số lần liên tiếp xâu S1 để được xâu S2 hay không?
Dữ liệu: Vào từ file văn bản XAU.INP
Dòng đầu tiên ghi xâu S1,
Dòng thứ hai ghi xâu S2.
Kết quả: Ghi vào file văn bản XAU.OUT
Trong trường hợp ghép được, ghi số K là số lần ghép liên tiếp xâu S1 để được xâu S2, trường hợp ngược lại ghi số 0.
Ví dụ
XAU.INP
XAU.OUT

XAU.INP
XAU.OUT

ACM
ACMACMACM

3

MNP
MNPMNPMNPC

0


Bài 3 (2,5 điểm). phủ đoạn thẳng
Cho đoạn thẳng [a, b] và N đoạn thẳng [a1,b1], [a2,b2], …, [aN,bN] trên trục số (1<= N<=100). Đoạn thẳng [a, b] được gọi là bị phủ bởi N đoạn thẳng [a1,b1], [a2,b2], …, [aN,bN] nếu [a,b]
Yêu cầu: Hãy tìm trong N đoạn thẳng [a1,b1], [a2,b2], …, [aN,bN] ít nhất K đoạn thẳng, sao cho K đoạn thẳng này phủ đoạn thẳng [a,b].
Dữ liệu: Vào từ file văn bản DOAN_TH.INP:
Dòng đầu tiên ghi 3 số nguyên dương N, a, b là số đoạn thẳng và điểm đầu và điểm cuối của đoạn thẳng [a,b] (-32000 <= a< b <= 32000).
Dòng thứ I trong N dòng