Đề thi chọn học sinh giỏi Quốc gia Lớp 12 THPT năm 2011 môn Tin học - Ngày 2 (Có đáp án)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 
ĐỀ THI CHÍNH THỨC 
KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA 
LỚP 12 THPT NĂM 2011 
Môn: TIN HỌC 
Thời gian: 180 phút (không kể thời gian giao đề) 
Ngày thi thứ hai: 12/01/2011 
(Đề thi có 03 trang, gồm 03 bài) 
TỔNG QUAN NGÀY THI THỨ HAI 
 Tên bài File chương trình File dữ liệu vào File kết quả 
Bài 4 Nối điểm đen trắng BWPOINTS.* BWPOINTS.INP BWPOINTS.OUT 
Bài 5 Trò chơi chẵn lẻ PARIGAME.* PARIGAME.INP PARIGAME.OUT 
Bài 6 Nâng cấp mạng UPGRANET.* UPGRANET.INP UPGRANET.OUT 
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. 
Hãy lập trình giải các bài toán sau: 
Bài 4. (6 điểm) Nối điểm đen trắng 
Trên trục số thực cho n điểm đen và n điểm trắng hoàn toàn phân biệt. Các điểm đen có toạ độ 
nguyên a1, a2, ..., an còn các điểm trắng có toạ độ nguyên b1, b2, ..., bn. Người ta muốn chọn ra k 
điểm đen và k điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho k đoạn thẳng tạo 
được đôi một khôn... 
 Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản PARIGAME.OUT gồm k dòng, mỗi dòng là kết quả tương ứng với 
một bộ dữ liệu theo thứ tự xuất hiện trong file dữ liệu vào: ghi thông báo ‘YES’ nếu người đi trước 
có cách chơi giành phần thắng và ‘NO’ trong trường hợp ngược lại. 
Ví dụ: 
PARIGAME.INP PARIGAME.OUT
2 
3 
1 2 2 
1 2 3 
2 3 1 
4 
2 2 2 2 
2 2 2 2 
2 2 2 2 
2 2 2 2 
YES 
NO 
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 50. 
Bài 6. (7 điểm) Nâng cấp mạng 
Một hệ thống gồm n máy tính đánh số từ 1 tới n được kết nối thành một mạng bởi m đoạn cáp 
mạng đánh số từ 1 tới m. Đoạn cáp mạng thứ i có thông lượng wi kết nối hai máy ui, vi cho phép 
truyền dữ liệu theo cả hai chiều giữa hai máy này. 
Một dãy các máy x1, x2, ..., xp, trong đó giữa hai máy xj và xj+1 (j = 1, 2, ..., p − 1) có đoạn cáp nối, 
được gọi là một đường truyền tin từ máy x1 tới máy xp. Thông lượng của đường truyền tin được 
xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường 
Trang 2/3 
truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kỳ và giữa hai 
máy có không quá một đoạn cáp mạng nối chúng. 
Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. 
Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng ∆ (∆ > 0) ta phải trả một chi phí 
đúng bằng ∆. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp 
i đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy ui tới máy vi. 
Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất. 
Dữ liệu: Vào từ file văn bản UPGRANET.INP 
• Dòng thứ nhất chứa hai số nguyên dương n, m (n, m ≤ 105); 
• Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương ui, vi, wi (wi ≤ 106), i = 1, 2, ..., m. 
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấ