Đề thi HSG QG Tin học 2

(Đề 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
Xóa 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 ta 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 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 không?
Dữ liệu: Vào từ file văn bản ONEARC.INP:
Dòng đầu tiên ghi hai số nguyên 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 và 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. Xóa 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 Σ 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 Σ 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ể xóa đượ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 xóa, đường gấp khúc này chỉ qua các ô trống hay nằm ngoài bảng. Các ô bị xóa trở thành ô trống. Mỗi lần xóa 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ể xóa 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ể xóa sớm nhất ở bước thứ 2, sau khi đã xóa các ô chứa ‘A’. Như vậy, để xóa trống 2 ô (2, 1) và (1, 2) cần thực hiện tối thiểu 3 bước xóa.
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