Đề 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 - Đề 1) (Có đáp án)

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ứ nhất: 23/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 1
Chọn ô
SELECT.PAS
SELECT.INP
SELECT.OUT
BÀI 2
Quân tượng
BISHOP.PAS
BISHOP.INP
BISHOP.OUT
Hãy lập trình giải các bài toán sau:
Bài 1. Chọn ô
Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh số từ 1 đến 4, 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 trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghi một số nguyên aij , i =1, 2, 3, 4; j =1, 2, ..., n. Một cách chọn ô là việc xác định một tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. 
Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây 
1
2
3
1
-1
9
3
2
-4
5
-6
3
7
8
9
4
9
7
2
Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.
Yêu cầu: Hãy tìm cách chọn ô với trọng lượng lớn nhất.
Dữ liệu: Vào từ file văn bản SELECT.INP:
Dòng đầu tiên chứa số nguyên dương n là số cột của bảng.
Dòng thứ j trong số n dòng tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng. 
Kết quả: Ghi ra file văn bản SELECT.OUT trọng lượng của cách chọn tìm được.
Ví dụ: 
SELECT.INP
SELECT.OUT
SELECT.INP
SELECT.OUT
3
-1 -4 7 9
9 5 8 7
3 -6 9 2
32
3
5 5 5 5
5 5 5 5
5 5 5 5
30 
Hạn chế: Trong tất cả các test: n £ 10000, |aij|£ 30000. Có 50% số lượng test với n £ 1000.
Bài 2. Quân tượng
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân.
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.
Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.
Dữ liệu: Vào từ file văn bản BISHOP.INP:
Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t;
 Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra file văn bản BISHOP.OUT một số nguyên là số nước đi tìm được.
Ví dụ:
BISHOP.INP
BISHOP.OUT
8 3 7 2 1 4
5 4
3 4
4 7
3
Hạn chế: Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.
 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.