HSG11QB2024_V2_06032025
Điểm: 10
Cho một bảng hình vuông gồm ~N~ hàng, ~N~ cột. Các hàng của bảng được đánh số từ 1 đến ~N~ từ trên xuống dưới, các cột của bảng đượ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)~ và trên ô đó chứa một số nguyên dương là ~A_{i,j}~ (~1 \leq i, j \leq N~).
Yêu cầu: Hãy chọn một hình vuông kích thước ~K \times K~ của bảng sao cho tổng giá trị các ô được chọn là lớn nhất.
Dữ liệu vào:
Cho trong file SUM.INP có cấu trúc như sau:
- Dòng thứ nhất: Ghi hai số nguyên dương ~N, K~ (~N \leq 10^3, 1 \leq K < N~).
- Dòng thứ ~i~ trong số ~N~ dòng tiếp theo: Ghi ~N~ số nguyên dương, số thứ ~j~ là ~A_{i,j}~ (~A_{i,j} \leq 10^3~).
- Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra:
Ghi ra file SUM.OUT với cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương ~S~ là tổng tìm được.
Ví dụ:
Input: SUM.INP
4 3
1 9 1 1
9 9 9 9
9 9 9 9
14 9 9 1
Output: SUM.OUT
86
Điểm: 10
Gia đình anh B có một khu vườn trồng ~N~ cây ăn quả được đánh số từ 1 đến ~N~, các cây được trồng không hoàn toàn thẳng hàng. Cây thứ ~i~ được trồng ở tọa độ là ~(x_i, y_i)~. Để tránh thú hoang phá hoại anh B cần làm một hàng rào bao quanh khu vườn với việc tận dụng một số cây đang trồng trong vườn làm trụ. Hàng rào được làm sao cho tất cả các cây còn lại trong khu vườn phải nằm phía trong hoặc trên hàng rào. Hình ảnh của hàng rào là một đa giác gồm ~K~ đỉnh, mỗi đỉnh là một trụ.
Yêu cầu: Hãy giúp anh B tìm một phương án rào khu vườn sao cho số lượng cây được sử dụng làm trụ là ít nhất.
Dữ liệu vào
Cho trong file TREE.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương ~N~ là số lượng cây (~3 \leq N \leq 2000~).
- Dòng thứ ~i~ trong ~N~ dòng tiếp theo: Mỗi dòng là một cặp số nguyên ~x_i, y_i~ là hoành độ và tung độ của một cây trong vườn (~-32000 \leq x_i, y_i \leq 32000~). Hai số ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra:
Ghi ra file văn bản TREE.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên ~K~ là số lượng cây dùng làm trụ tìm được ít nhất.
Ví dụ:
Input: TREE.INP
5
0 4
4 0
-2 2
-1 1
0 -4
Output: TREE.OUT
4
Điểm: 10
Tại một tỉnh X có ~N~ trường học, đánh số từ 1 đến ~N~. Mỗi trường học được trang cấp một máy tính. Hai trường trao đổi thông tin được với nhau nếu có ít nhất một kênh truyền tín hiệu để kết nối hai máy tính của hai trường học (có thể kết nối thông qua một số trường khác, đường truyền đảm bảo hai chiều). Để kết nối một kênh truyền tín hiệu trực tiếp giữa hai máy tính của trường ~i~ và trường ~j~ thì phải mất một khoản chi phí là ~A_{i,j}~. Hiện nay, tỉnh X đã kết nối được ~M~ kênh truyền tín hiệu trực tiếp giữa ~M~ cặp máy tính của các trường học trong tỉnh.
Yêu cầu: Hãy kiểm tra xem với ~M~ kênh truyền tín hiệu đã có thì hai trường học bất kỳ có thể trao đổi thông tin được với nhau hay không? Nếu không, hãy kết nối thêm một số kênh truyền tín hiệu trực tiếp giữa các máy tính sao cho đảm bảo được việc trao đổi thông tin giữa tất cả các trường học và tổng chi phí dùng để kết nối thêm là nhỏ nhất.
Dữ liệu vào:
Cho trong file NETWORK.INP có cấu trúc như sau:
- Dòng 1: Ghi 2 số nguyên dương ~N, M~ (~2 \leq N \leq 100; 0 < M \leq 250~).
- $M$ dòng tiếp theo: Mỗi dòng ghi 2 số nguyên dương là số hiệu của hai trường có kênh truyền tín hiệu trực tiếp.
- Dòng thứ ~i~ trong ~N~ dòng tiếp theo: Ghi ~N~ số nguyên dương ~A_{i1}, A_{i2}, \dots, A_{iN}~ lần lượt là chi phí để xây dựng kênh truyền tín hiệu trực tiếp từ máy tính của trường ~i~ đến các máy tính của các trường từ 1 đến ~N~ (~0 < A_{i,j} \leq 32000~ với ~i \neq j~; ~A_{i,j} = 0~ với ~i = j~).
- Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra:
Ghi ra file văn bản NETWORK.OUT theo cấu trúc như sau:
- Dòng 1: Nếu không cần kết nối thêm kênh truyền tín hiệu trực tiếp thì ghi số 0. Ngược lại thì ghi số nguyên dương ~T~, là tổng chi phí dùng để nối thêm các các kênh truyền tín hiệu.
Ví dụ:
Input: NETWORK.INP
5 4
1 2
2 3
3 1
4 5
0 4 5 5 8
4 0 7 6 7
5 7 0 3 10
5 6 3 0 9
8 7 10 9 0
Output: NETWORK.OUT
3