Đề thi olympic năm 2002 khối 11

Bài 1: Bày tranh

Cho n bức tranh mã số từ 1 .. n. Người ta cần chọn ra 1 bức để treo ở cửa phòng tranh, số còn lại được treo thẳng hàng trong phòng tại m vị trí định sẵn mã số từ 1 đến m từ trái qua phải. Các tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có số hiệu nhỏ phải được treo ở bên trái tranh có số hiệu lớn. Biết các thông tin sau về mỗi bức tranh:
• Tranh thứ i treo tại cửa sẽ đạt giá trị thẩm mỹ c[i].
• Tranh thứ i treo tại vị trí j sẽ đạt giá trị thẩm mỹ v[i, j].
• n <= m+1; m <= 50.
• Các giá trị thẩm mỹ là những số tự nhiên không vượt quá 50.
Hãy xác định một phương án treo tranh để có tổng giá trị thẩm mỹ là lớn nhất.
Dữ liệu vào: cho trong tập tin văn bản TRANH.INP
Dòng thứ nhất: Hai giá trị n và m.
Dòng tiếp theo là n giá trị c[1], c[2], ... , c[n].
Tiếp đến là n dòng, dòng i gồm m giá trị v[i, 1], v[i, 2], ..., v[i, m]. Các số trên cùng dòng cách nhau bởi dấu cách.
Dữ liệu ra: cho trong tập tin văn bản TRANH.OUT
Dòng thứ nhất: giá trị thẩm mỹ lớn nhất tìm được.
Dòng thứ hai: mã số bức tranh treo ở cửa phòng tranh.
Từ dòng thứ ba: n - 1 số tự nhiên sắp tăng chặt biểu thị mã số các vị trí được chọn để treo tranh trong phòng. Các số trong cùng dòng cách nhau bởi dấu cách.
Thí dụ
TRANH.INP
3 4
1 20 1
1 10 1 3
2 1 2 2
1 3 0 10

TRANH.OUT
40
2
2 4

Bài 2: Chu vi
Cho N (0 < N < 200) hình chữ nhật có các cạnh song song với các trục hoành và tung của hệ trục tọa độ vuông góc. Mỗi hình chữ nhật có thể bị che khuất một phần hoặc dán chồng lên một hình chữ nhật khác. Ðộ dài đường biên các hình chữ nhật được gọi là chu vi các hình chữ nhật đó. Viết chương trình tính chu vi được tạo bởi các hình chữ nhật cho trước.
Ðỉnh của mỗi hình chữ nhật có tọa độ nguyên thuộc [0,1000].
Ví dụ: Xét 4 hình chữ nhật (Hình A) .Chu vi các hình chữ nhật trên là tổng các đoạn liền nét trong Hình B.
Dữ liệu vào:
Cho trong tập tin văn bản HCN.INP.
Dòng đầu là số nguyên N.
Dòng 2 ..N+1: dòng i chứa tọa độ đỉnh trái dưới và đỉnh phải trên của hình chữ nhật i-1. Tọa độ mỗi đỉnh được cho bởi hoành độ x, theo sau là tung độ y.
Dữ liệu ra:
Cho trong tập tin văn bản HCN.OUT, gồm một số nguyên không âm duy nhất là chu vi các hình chữ nhật cho trong tập tin dữ liệu.
Thí dụ:
HCN.INP
4
0 0 2 4
1 3 4 5
3 0 4 4
1 1 4 2



HCN.OUT
24


Bài 3: Trang trí.
Cho một bảng gồm m dòng, n cột. Trên mỗi ô của bảng có thể có một bóng đèn hoặc không có bóng đèn. Ở các ô có bóng đèn người ta trang trí bằng các đèn màu xanh hoặc đỏ sao cho tổng số đèn màu xanh và tổng số đèn màu đỏ trên mỗi dòng, mỗi cột chênh lệch nhau ít nhất.
Dữ liệu vào:
Cho trong tập tin văn bản XANHDO.INP
Dòng thứ nhất: Hai giá trị m và n (m, n < 200).
Mỗi dòng trong m dòng tiếp theo có n số 0 hoặc 1. Số 0 chỉ ô không có đèn, số 1 chỉ ô có đèn.
Dữ liệu ra:
Cho trong tập tin văn bản XANHDO.OUT., gồm m dòng. Mỗi dòng có n số nhận giá trị 0, 1 hoặc 2. Số 0 chỉ ô không có đèn; số 1 chỉ ô có bóng đèn màu xanh; số 2 chỉ ô có bóng đèn màu đỏ.
Thí dụ:
XANHDO.INP
5 6
1 0 0 1 0 1
0 1 1 0 1 0
1 1 1 1 0 1
0 1 0 1 1 0
1 0 1 1 1 1


XANHDO.OUT
1 0 0 2 0 1
0 2 1 0 1 0
2 1 2 1 0 2
0 1 0 1 2 0
1 0 1 2 2 1

Chú ý: Thời gian chạy mỗi test không quá 10 giây.