Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học (Lần 1) - Năm học 2011-2012 - Sở GD&ĐT Ninh Bình (Đề 2)

ĐỀ THI CHÍNH THỨC
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT
NĂM HỌC 2011 - 2012
Môn: Tin học – Ngày thứ hai
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
(Đề thi gồm 03 bài trong 02 trang)
Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian chạy
1- Cặp điểm gần nhất
NEAREST.PAS
NEAREST.INP
NEAREST.OUT
2 giây/test
2- Vòng tròn chung
ROUND.PAS
ROUND.INP
ROUND.OUT
2 giây/test
3- Du lịch
TOURIST.PAS
TOURIST.INP
TOURIST.OUT
2 giây/test
Lưu ý: - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. 
	- Các file dữ liệu trong bài nếu có 2 giá trị trên một dòng, 2 giá trị luôn cách nhau bằng 1 khoảng trắng.
	- Mỗi bài có 60% số test kích thước nhỏ. 
Bài 1: Cặp điểm gần nhất (6 điểm).
Trên trục số, cho n điểm A1, A2,... An có tọa độ lần lượt: x1, x2,... xn. Các điểm không nhất thiết phân biệt.
Yêu cầu: Hãy xác định các cặp điểm Ai, Aj (0 < i < j < n + 1) sao cho khoảng cách Ai, Aj ngắn nhất.
Dữ liệu vào: File văn bản NEAREST.INP gồm 2 dòng:
Dòng 1: Số nguyên n, 2 £ n £ 106
Dòng 2: n số: x1, x2,... xn. Các tọa độ có giá trị tuyệt đối không quá 109.
Dữ liệu ra: File văn bản NEAREST.OUT. Ghi ra hai giá trị trên một dòng: khoảng cách ngắn nhất tìm được và số lượng cặp điểm có khoảng cách bằng khoảng cách ngắn nhất.
Ví dụ:
NEAREST.INP
NEAREST.OUT
Giải thích
4
5 2 1 3
1 2
Khoảng cách: 1
2 cặp điểm có khoảng cách 1: (2,1) và (2,3)
Bài 2: Vòng tròn chung (7 điểm)
Cho hai dãy số nguyên a1, a2, ..., am và b1, b2, ..., bn. Các số này được xếp lần lượt quanh hai vòng tròn A và B theo chiều kim đồng hồ: các số ai quanh vòng tròn A và các số bj quanh vòng tròn B. Vòng tròn C với các số quanh nó: c1, c2, ..., cp được gọi là vòng tròn con của A (hoặc của B) nếu tồn tại một cách xoá bớt các số của A (hoặc của B) để được vòng tròn C. 
Yêu cầu: Hãy tìm vòng tròn C là vòng tròn con của cả A và B với số phần tử p lớn nhất có thể.
Dữ liệu vào: File văn bản ROUND.INP
Dòng 1 chứa hai số nguyên m, n (2 £ m, n £ 100).
Dòng 2 chứa m số a1,a2, ..., am
Dòng 3 chứa n số b1,b2, ..., bn
Các số ai, bj là các số nguyên có giá trị tuyệt đối không quá 109.
Dữ liệu ra: File văn bản ROUND.OUT gồm một dòng duy nhất ghi số nguyên p lớn nhất tìm được.
Ví dụ:
ROUND.INP
ROUND.OUT
Giải thích
5 4
1 2 3 4 5
3 2 4 1
3
Vòng tròn chung: 2 4 1 
hoặc 3 4 1.
Bài 3: Du lịch (7 điểm). 
Sơn là một học sinh trung học ở tỉnh Ninh Bình. Sơn thấp và nhỏ người nên các bạn học cùng trường hay trêu chọc và đặt biệt danh Sơn "còi". Tuy "còi" nhưng Sơn lại là một học sinh học rất giỏi. Trong kỳ thi chọn học sinh giỏi cấp tỉnh, Sơn đạt thành tích cao và vinh dự được chọn vào đội tuyển tham dự kỳ thi học sinh giỏi cấp quốc gia. Đây là thành tích rất đáng tự hào, bố của Sơn quyết định thưởng cho con trai mình một chuyến du lịch về thủ đô Hà Nội trước khi Sơn bước vào đợt tập huấn đội tuyển học sinh giỏi cấp quốc gia. 
Vốn là một cậu bé ham học nhưng cũng rất ham mê du lịch, Sơn xin phép bố chỉ đến thăm chùa Một Cột để vừa tiết kiệm thời gian, dành thời gian cho việc học, đồng thời thỏa mãn được sở thích du lịch, sở thích tìm hiểu về lịch sử, đất nước mình. Xuất phát từ bến xe Giáp Bát thuộc thành phố Hà Nội, Sơn muốn chọn một lộ trình đi đến chùa Một Cột và quay về bến xe Giáp Bát sao cho tổng chi phí thời gian là nhỏ nhất và để ngắm cảnh được nhiều hơn trên đường đi, lộ trình sẽ không có đoạn đường nào đi qua quá một lần. 
Thành phố Hà Nội có n điểm dừng xe, trong đó có 2 điểm là Giáp Bát và chùa Một Cột. Các điểm dừng xe được đánh chỉ số từ 1 đến n, trong đó Giáp Bát là điểm dừng có chỉ số s và chùa Một Cột là điểm dừng có chỉ số d.
Yêu cầu: Hãy giúp Sơn xác định xem có tồn tại lộ trình thỏa mãn yêu cầu hay không và tổng chi phí thời gian đi hết lộ trình là bao nhiêu.
Dữ liệu vào:
Dòng đầu tiên ghi bốn số n, m, s, d ( 2 £ n £100).
Mỗi dòng thứ i trong số m dòng tiếp theo ghi 3 số: ai, bi, ti, trong đó ai, bi là chỉ số của 2 điểm dừng, và ti (0 < ti £ 200) là thời gian đi từ ai, bi và ngược lại. Hai điểm dừng không chỉ rõ thời gian là hai điểm dừng giữa chúng không có đường đi.
Dữ liệu ra: Ghi ra file văn bản TOURIST.OUT một số nguyên duy nhất là tổng thời gian lộ trình thỏa mãn yêu cầu. Nếu không có lộ trình thỏa mãn yêu cầu, ghi ra số -1.
Ví dụ:
TOURIST.INP
TOURIST.OUT
Giải thích
5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3
24
Lộ trình:
1 2 3 5 4 1
---------------------Hết---------------------
Hä vµ tªn thÝ sinh...................................... Sè b¸o danh:.........................................................
Ch÷ kÝ cña gi¸m thÞ 1................................ Ch÷ kÝ cña gi¸m thÞ 2............................................