Đề thi chọn đội tuyển học sinh giỏi dự thi quốc gia môn Tin học - Năm học 2016-2017 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN ĐỘI TUYỂN 
HỌC SINH GIỎI DỰ THI QUỐC GIA
Năm học 2016 - 2017
MÔN: TIN HỌC
(Thời gian 180 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 03 trang
Tổng quan đề thi
Tên bài
Tên file chương trình
Tên file dữ liệu vào
Tên file dữ liệu ra 
Bài 1
Nối xích
CHAINE.***
CHAINE.INP
CHAINE.OUT
Bài 2
Địa điểm tối ưu
BESTPOS.***
BESTPOS.INP
BESTPOS.OUT
Bài 3
Xây dựng đồ thị
ADDEDGE.***
ADDEDGE.INP
ADDEDGE.OUT
Trong đó * là “pas” hoặc “cpp” tùy theo ngôn ngữ lập trình là Pascal hay C++.
Bài 1 (6 điểm): Nối xích 
Người ta có N đoạn dây xích, mỗi đoạn dây xích là một chuỗi các mắt xích được nối với nhau. Các đoạn dây xích này tách rời nhau. Mỗi đoạn dây xích có không quá M mắt xích.
Bằng cách cắt ra một mắt xích, sau đó hàn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian cắt và hàn mỗi mắt xích là 1 đơn vị thời gian và được xem là bằng nhau với mọi mắt xích.
Nhiệm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất (hay số mắt xích bị cắt ra và hàn lại là ít nhất).
Dữ liệu vào: Dữ liệu được cho trong file CHAINE.INP có cấu trúc như sau:
Dòng đầu tiên ghi số N là số đoạn mắt xích.
Những dòng tiếp theo ghi N số nguyên dương, số thứ i là số mắt xích có trong đoạn thứ i (1≤i≤N). Hai số cạnh nhau trên một dòng cách nhau ít nhất một dấu cách.
Dữ liệu ra: Chương trình của bạn cần đưa ra file CHAINE.OUT một số duy nhất là số đơn vị thời gian để bạn cần để nối N đoạn xích dã cho.
Ví dụ:
CHAINE.INP
CHAINE.OUT
3
4 7
6
2
4
5 7 2
9
2
Giải thích: 
Ví dụ 1 ta có thể cắt 2 mắt xích bất kì và nối hai đoạn một với nhau.
Ví dụ 2 ta cắt 2 mắt xích của đoạn xích thứ 3 sau đó mang nối các đoạn xích độ dài (5-7) và (5,7-9).
Ràng buộc: 
50% số test có N ≤103
50% số test có N ≤106
Bài 2 (7 điểm): Địa điểm tối ưu
Công ty máy tính Alpha có F đại lý ở F thành phố trong số P thành phố của đất nước (mỗi thành phố chỉ có tối đa một đại lý của công ty) (1≤P≤500). Các thành phố được đánh số lần lượt từ 1 đến P.
Hệ thống giao thông của đất nước gồm C (1≤C≤8000) đường đi hai chiều (đánh số từ 1 đến C) đảm bảo sự đi lại giữa hai thành phố bất kỳ. Tất nhiên mỗi một con đường cần tốn một khoảng thời gian để đi từ đầu nọ đến đầu kia (theo cả hai chiều).
Công ty cần chọn một thành phố làm tổng kho để sao cho thời gian trung bình từ tổng kho này đến các đại lý là nhỏ nhất. Hãy viết một chương trình để thực hiện điều này.
Dữ liệu vào: File BESTPOS.INP
Dòng đầu tiên ghi ba số nguyên cách nhau bởi khoảng trắng P, F và C.
Dòng tiếp theo chứa F số nguyên cách nhau bởi khoảng trắng là số hiệu của một thành phố có đại lý của công ty.
C dòng cuối cùng, mỗi dòng mô tả một con đường bao gồm ba số nguyên u, v và T cách nhau bởi khoảng trắng cho biết có một con đường nối thành phố u với thành phố v với thời gian đi (cả hai chiều) là T.
Dữ liệu ra: File BESTPOS.OUT một số nguyên duy nhất là số hiệu của thành phố được chọn làm tổng kho. Nếu có nhiều thành phố cùng thoả mãn thì chọn thành phố có số hiệu nhỏ nhất.
Ví dụ:
BESTPOS.INP
BESTPOS.OUT
13 6 15
11 13 10 12 8 1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7
10
BÀI 3 (7 điểm): Xây dựng đồ thị
Người ta khởi tạo một đồ thị có hướng gồm 109 đỉnh, các đỉnh được đánh số từ 1 đến 109. Ban đầu đồ thị không có cung nào. Người ta lần lượt thêm các cung vào đồ thị bởi m lệnh dạng Add(u,v): thêm một cung nối từ đỉnh u đến đỉnh v trên đồ thị.
Yêu cầu: Cho trước hai đỉnh s và t. Hãy cho biết số thứ tự của lệnh Add đầu tiên mà sau thời điểm thực hiện lệnh Add đó, ta có thể đi từ s đến t theo các cung của đồ thị.
Dữ liệu vào: File văn bản ADDEDGE.INP
Dòng 1 chứa ba số nguyên dương m, s, t ()
m dòng tiếp theo, mỗi dòng ghi hai số nguyên u, v tương ứng là một lệnh Add(u,v)
Dữ liệu ra: Ghi ra file văn bản ADDEDGE.OUT một số duy nhất là số thứ tự lệnh Add tìm được, trong trường hợp không thể đi từ s đến t cho dù thực hiện tất cả các lệnh Add thì ghi số 0.
Ví dụ:
ADDEDGE.INP
ADDEDGE.OUT
5 1 5
1 2 
3 5 
3 1 
2 3 
2 4
4
Ràng buộc:
50% số test có m ≤100, SỐ ĐỈNH ≤103
--------------------------Hết--------------------------
Thí sinh không được sử dụng tài liệu.
Giám thị không giải thích gì thêm.