Đề thi HSG QG Tin học 3

(Đề 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


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 van 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 x 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ănbả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