Sở GD&ĐT Nghệ An Kì thi chọn Học Sinh Giỏi tỉnh
Năm học 2007 - 2008

Môn thi: tin học lớp 12 thpt
(Đề thi gồm có 2 trang)
Thời gian: 180 phút (không kể thời gian giao đề)

BÀI 1. đường hầm
Có N hòn đảo đánh số từ 1 đến N. Một số hòn đảo đã có đường hầm thông với nhau. Người ta muốn xây dựng thêm một số đường hầm sao cho có thể đi lại giữa 2 hòn đảo bất kỳ bằng đường hầm. Biết rằng đường hầm nối các đảo là đường đi 2 chiều, hãy lập trình tính số đường hầm ít nhất cần xây dựng thêm.
Dữ liệu: Vào từ file văn bản HAM.INP gồm:
Dòng đầu tiên là số N (1Các dòng tiếp theo mỗi dòng ghi hai số i và j cho biết có đường hầm nối giữa 2 hòn đảo i và j.
Kết quả: Ghi ra file văn bản HAM.OUT chỉ một số duy nhất cho biết số đường hầm ít nhất cần xây dựng thêm.
Ví dụ:
HAM.INP
HAM.OUT

9
1 3
1 5
1 6
2 7
4 8
8 9
2


Bài 2: Xây kè
bản đồ hình chữ nhật mô tả một số diện tích hồ nước thiên nhiên được chia lưới ô vuông sao cho mỗi ô của lưới chỉ được xem như có 2 trạng thái: hoặc là diện tích hồ, hoặc không phải. Người ta muốn xây kè đá xung quanh các hồ này. Mỗi cạnh của lưới được xây kè nếu nó là cạnh chung của 2 ô khác trạng thái (các cạnh thuộc biên bản đồ không được tính). Lập trình tính tổng chiều dài của kè (theo đơn vị cạnh ô lưới).
Dữ liệu : Vào từ file văn bản KE.INP gồm:
Dòng đầu ghi M (số dòng của lưới) và N (số cột của lưới).
Mỗi dòng trong số M dòng tiếp mô tả trạng thái của N ô lưới tương ứng của dòng gồm N số 0 (là đất) hoặc 1 (là hồ) theo đúng thứ tự các ô trong lưới.
Kết quả: Ghi ra file văn bản KE.OUT gồm một số ghi giá trị chiều dài kè.
Ví dụ: Bản đồ (các ô có mầu xám là diện tích hồ, các cạnh đậm là kè) có các file vào, ra tương ứng như sau:
KE.INP
KE.OUT

6 11
0 0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 0 1 0 0 0
0 0 0 1 0 0 1 1 1 1 0
0 1 0 0 0 1 1 0 1 1 0
0 1 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 1 1 1
43











































































Giới hạn: M, N không quá 200.
BàI 3 DU lịch
Ông G là một hướng dẫn viên du lịch. Công việc của ông ta là hướng dẫn tua du lịch từ thành phố U đến thành phố V. Các thành phố được đánh số từ 1 đến N (N<100). Có một số đoạn đường hai chiều giữa một số cặp thành phố và mỗi đoạn đường có dịch vụ xe buýt giới hạn lượng khách tối đa mà chỉ có các xe chở số khách không lớn hơ