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 (1<N<100).
Cá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è
Một 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

những con đờng và các số viết trên mỗi cạnh cho biết số khách lớn nhất mà dịch vụ xe buýt
chạy trên tuyến đờng đó có thể chở đợc. Bây giờ, nếu ông G muốn đa khách du lịch từ thành
phố 1 đến thành phố 7 thì lộ trình ông ta nên đi là 1-2- 4-7 và số hành khách tối đa trên mỗi
chuyến đi là 25.
Dữ liệu: Vào từ file văn bản TOURIST.INP:
Dòng đầu tiên chứa ba số nguyên N, U, V.
Các dòng tiếp theo mỗi dòng chứa 3 số nguyên X, Y, Z với ý nghĩa có đờng đi giữa X
và Y với lợng khách tối đa cho phép là Z (Z<100).
Kt qu: ghi ra File TOURIST.OUT gồm:
Dòng đầu tiên ghi lợng khách tối đa có thể chở đợc trên mỗi chuyến đi từ U đến V.
Trong các dòng tiếp, mỗi dòng ghi tên một thành phố trong hành trình từ U kết thúc tại
V.
Ví dụ:
TOURIST.INP TOURIST.OUT
7 1 7
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
25
1
2
4
7