Đề thi chọn HSG tỉnh môn Tin học Lớp 12 - Năm học 2007-2008 - Sở GD&ĐT Nghệ An

Sở GD&ĐT Nghệ An 	 Kì thi chọn Học Sinh Giỏi tỉnh 
 Đề chính thức
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 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ơn mới đi qua được. Ông G có một tấm bản đồ chỉ các thành phố và những con đường nối giữa chúng. Ngoài ra, ông ta cũng có thông tin về dịch vụ xe buýt giữa các thành phố. Hãy giúp ông G tìm lộ trình tốt nhất từ thành phố U đến thành phố V sao cho số khách trên mỗi chuyến đi là lớn nhất có thể được. 
 Trong ví dụ dưới đây: Bản đồ gồm 7 thành phố, mỗi cạnh nối giữa các thành phố biểu thị 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).
Kết 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.
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
Ví dụ:	
60
5
2
20
25
30
10
1
35
7
4
30
40
15
6
3
20
-----------------hết-----------------
Chú ý‎: 
- Các số trên cùng một dòng của các file vào, ra ghi cách nhau ít nhất một dấu trắng. 
- Chương trình của bài 1, bài 2, bài 3 phải ghi lên đĩa với tên tương ứng là BAI1.PAS, BAI2.PAS, BAI3.PAS
- Giám thị không giải thích gì thêm.
Họ và tên thí sinh :............................................................................Số báo danh :.....................