Đề 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 A - Đề 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 A
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
Mạng máy tính
ONEARC.PAS
ONEARC.INP
ONEARC.OUT
BÀI 4
Xoá cặp ô
DEL.PAS
DEL.INP
DEL.OUT
Hãy lập trình giải các bài toán sau:
Bài 3. Mạng máy tính 
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. Giả sử s và t là hai máy tính trong mạng. Ta gọi đường truyền tin từ máy s đến máy t là một dãy các máy tính và các kênh nối chúng có dạng:
	s = u1, e1, u2, ...,ui, ei, ui+1, ..., uk-1, ek-1, uk= t, 
trong đó u1, u2, ..., uk là các máy tính trong mạng, ei – kênh truyền tin từ máy ui đến máy ui+1 (i = 1, 2, ..., k-1). 
Mạng máy tính được gọi là thông suốt nếu như đối với hai máy u, v bất kỳ ta luôn có đường truyền tin từ u đến v và đường truyền tin từ v đến u. Mạng máy tính được gọi là hầu như thông suốt nếu như đối với hai máy u, v bất kỳ, hoặc là có đường truyền tin từ u đến v hoặc là có đường truyền tin từ v đến u. 
Biết rằng mạng máy tính đã cho là hầu như thông suốt nhưng không là thông suốt. 
Yêu cầu: Hãy xác định xem có thể bổ sung đúng một kênh truyền tin để biến mạng đã cho trở thành thông suốt được hay không?
Dữ liệu: Vào từ file văn bản ONEARC.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, i=1,2,...,m.
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 ONEARC.OUT:
Dòng đầu tiên ghi ‘YES’ nếu câu trả lời là khẳng định, ghi ‘NO’ nếu câu trả lời là phủ định.
Nếu câu trả lời là khẳng định thì dòng thứ hai ghi hai số nguyên dương u, v cách nhau bởi dấu cách cho biết cần bổ sung kênh truyền tin từ máy u đến máy v để biến mạng thành thông suốt. 
Ví dụ:
ONEARC.INP
ONEARC.OUT
3 2
1 2
2 3
YES
3 1
Hạn chế: Trong tất cả các test: n £ 2000, m £ 30000.Có 50% số lượng test với n £ 200.
Bài 4. Xoá cặp ô	
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. Ô nằm ở vị trí dòng i và cột j của bảng được gọi là ô (i,j). 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. Mỗi ký tự của tập S xuất hiện ở không quá 4 ô trong bảng. Hai ô chứa cùng một ký tự được gọi là giống nhau. Hai ô giống nhau có thể xoá được nếu chúng có cạnh chung hoặc tâm (giao điểm của hai đường chéo) của 2 ô này có thể nối 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 này 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’ hoặc 2 ô chứa ký tự ‘B’ hay 2 ô chứa ký tự ‘D’. Hai ô chứa ký tự ‘C’ chỉ có thể xoá sớm nhất ở bước thứ 2, sau khi đã xoá các ô chứa ‘A’. Như vậy, để xoá trống 2 ô (2, 1) và (1,2) cần thực hiện tối thiểu 3 bước xoá.
Yêu cầu: Cho hai số m, n và m xâu độ dài n mô tả các dòng của bảng và hai ô khác trống (r1, c1), (r2, c2). Hãy xác định số bước ít nhất cần thực hiện để biến đổi các ô (r1, c1) và (r2, c2) trở thành ô trống.
Dữ liệu: Vào từ file văn bản DEL.INP:
Dòng đầu tiên chứa 6 số nguyên m, n, r1, c1, r2, c2, hai số liên tiếp đượ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 DEL.OUT số nguyên k là số bước ít nhất tìm được (qui ước: nếu không tồn tại cách biến đổi thoả mãn yêu cầu đặt ra thì k=-1). 
Ví dụ:
DEL.INP
DEL.OUT
DEL.INP
DEL.OUT
4 5 2 1 1 2
ABD...
C.12..
..21C.
A.B.D.
3
4 6 4 2 4 6
ABCDUV
BADCVU
ABCDUV
BADCVU
3
Hạn chế: Trong tất cả các test: 0 < m ≤ 10, 0 < n ≤ 20. Có 60% số lượng test có m ≤ 8, n ≤ 10 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.