Đề thi chọn học sinh giỏi quốc gia Lớp 12 THPT năm 2006 môn Tin học (Bảng B - Đề 2)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 	 KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA
	 LỚP 12 THPT NĂM 2006
§Ò Thi ChÝnh thøc
Môn: TIN HỌC - Bảng B
Thời gian: 180 phút (Không kể thời gian giao đề)
Ngày thi thứ hai: 24/02/2006
(Đề thi gồm 2 trang)
TỔNG QUAN BÀI THI 
Tên bài
Tên chương trình
File dữ liệu vào
File kết quả
BÀI 3
Kênh xung yếu
CIRARC.PAS
CIRARC.INP
CIRARC.OUT
BÀI 4
Biến đổi bảng
CHANGE.PAS
CHANGE.INP
CHANGE.OUT
Hãy lập trình giải các bài toán sau:
Bài 3. Kênh xung yếu 
Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép truyền tin một chiều từ máy này đến máy kia. Ta gọi một mạch vòng của mạng đã cho là một dãy các máy tính và các kênh nối chúng có dạng:
	u1, e1, u2, ...,ui, ei, ui+1, ..., uk-1, ek-1, uk, ek, u1 
trong đó u1, u2, ..., uk là các máy tính khác nhau trong mạng, ei – kênh truyền tin từ máy ui đến máy ui+1 (i = 1, 2, ..., k-1), ek là kênh truyền tin từ máy uk đến máy u1. Một kênh truyền tin trong mạng được gọi là kênh xung yếu nếu như bất cứ mạch vòng nào của mạng cũng đều chứa nó.
Yêu cầu: Hãy xác định tất cả các kênh xung yếu của mạng đã cho.
Dữ liệu: Vào từ file văn bản CIRARC.INP:
Dòng đầu tiên chứa 2 số nguyên dương n và m.
Dòng thứ i trong số m dòng tiếp theo mô tả kênh nối thứ i bao gồm hai số nguyên dương ui, vi cho biết kênh nối thứ i cho phép truyền tin từ máy ui đến máy vi.
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản CIRARC.OUT:
Dòng đầu tiên ghi số nguyên k là số lượng kênh xung yếu trong mạng đã cho. Ghi k = -1 nếu mạng không chứa kênh xung yếu.
Nếu k>0 thì mỗi dòng trong số k dòng tiếp theo ghi thông tin về một kênh xung yếu tìm được theo qui cách mô tả giống như trong file dữ liệu vào.
Ví dụ:
CIRARC.INP
CIRARC.OUT
CIRARC.INP
CIRARC.OUT
2 2
1 2
2 1
2
1 2
2 1
3 3
1 2
2 3
1 3
-1
Hạn chế: Trong tất cả các test: n ≤ 1000, m £ 20000. Có 50% số lượng test với n ≤ 200.
Bài 4. Biến đổi bảng
Cho một bảng hình chữ nhật kích thước m×n ô vuông kích thước đơn vị. Các dòng được đánh số từ 1 đến m, từ trên xuống dưới. Các cột được đánh số từ 1 đến n, từ trái qua phải. Mỗi ô của bảng hoặc được để trống hoặc chứa một ký tự lấy từ tập S gồm các chữ số từ 0 đến 9 và các chữ cái la tinh in hoa từ A đến Z. Hai ô chứa cùng một ký tự được gọi là giống nhau. Mỗi ký tự của tập S xuất hiện ở không quá 4 ô trong bảng. Hai ô giống nhau có thể xoá được nếu chúng có cạnh chung hoặc có thể nối các tâm (giao điểm của hai đường chéo) của chúng với nhau bằng một đường gấp khúc gồm không quá 3 đoạn thẳng độ dài nguyên, mỗi đoạn song song với cạnh của bảng và ngoại trừ hai ô cần xoá, đường gấp khúc chỉ qua các ô trống hay nằm ngoài bảng. Các ô bị xoá trở thành ô trống. Mỗi lần xoá một cặp ô của bảng được gọi là một bước. Hình bên nêu ví dụ với trường hợp m = 4 và n = 6. Bước đầu tiên có thể xoá hai ô chứa ký tự ‘A’, tiếp theo, lần lượt xoá các cặp ô chứa ‘B’, chứa ‘C’ và cặp ô chứa ‘D’. Ở ví dụ này, sau khi thực hiện 4 bước xoá có thể, trong bảng còn lại 4 ô không thể xoá được.
Yêu cầu: Cho m, n và m xâu độ dài n mô tả các dòng của bảng. Hãy xác định số lượng ô lớn nhất có thể xoá được.
Dữ liệu: Vào từ file văn bản CHANGE.INP:
Dòng đầu tiên chứa 2 số nguyên m, n được ghi cách nhau bởi dấu cách.
Dòng thứ i+1 chứa xâu n ký tự mô tả dòng thứ i của bảng (i = 1, 2, ..., m). Các ô trống được thể hiện bằng dấu chấm (‘.’).
Kết quả: Đưa ra file văn bản CHANGE.OUT một số nguyên là số lượng ô lớn nhất có thể xoá được.
Ví dụ:
CHANGE.INP
CHANGE.OUT
CHANGE.INP
CHANGE.OUT
4 5
ABD...
C.12..
..21C.
A.B.D.
8
4 6
ABCDUV
BADCVU
ABCDUV
BADCVU
24
Hạn chế: Trong tất cả các test: 0 < m ≤ 10, 0 < n ≤ 10. Có 60% số lượng test có m ≤ 5, n ≤ 6 và số lượng các ô khác trống không quá .
-------------- 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.