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)

SỞ GD&ĐT NGHỆ AN Đề thi chớnh thức (Đề 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 đặt 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ừ file 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 tiếp theo ghi 2 số nguyên x, y là điểm đầu và điểm cuối của đoạn thẳng thứ I trong N đoạn thẳng đã cho (-32000 <= x < y <= 32000) Kết quả: Ghi ra file văn bản DOAN_TH.OUT: Nếu không tìm được ghi số 0, trong trường hợp ngược lại dòng đầu tiên ghi số K là số đoạn thẳng tìm được, dòng thứ hai ghi K số nguyên dương là chỉ số của các đoạn thẳng phủ đoạn thẳng [a,b]. Cả hai file dữ liệu vào ra, các số trên một dòng ghi cách nhau một dấu cách. Ví dụ: DOAN_TH.INP DOAN_TH.OUT 7 -10 15 -2 1 -11 0 -1 3 -1 8 7 16 0 7 6 20 3 2 4 7 ----------------- Hết ----------------- Họ và tên :…..............…………………………………………… SBD:………........ Chú ý: - Chương trình giải các bài 1, bài 2, bài 3 ghi lên đĩa với tên file lần lượt là BAI1.pas, BAI2.pas, BAI3.pas. - Giám thị không phải giải thích gì thêm.