Máy kéo

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới $N \times N$ biểu diễn độ cao địa hình. Chi phí di chuyển của máy kéo từ ô này sang ô liền kề bằng hiệu tuyệt đối độ cao giữa hai ô.

Với chi phí tối đa $D$ , máy kéo chỉ có thể di chuyển qua các cạnh có hiệu độ cao $\leq D$ . Cần tìm chi phí tối thiểu $D$ để máy kéo có thể đi đến ít nhất $⌈ N^{2} / 2 ⌉$ ô (bắt đầu từ bất kỳ ô nào).

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): $N$ số nguyên cách nhau bởi dấu cách — độ cao của các ô trong hàng $i$

Dữ liệu ra

Một số nguyên duy nhất: chi phí tối thiểu $D$

Ràng buộc

$1 \leq N \leq 500$
$0 \leq h_{i j} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
5 0 0 0 3 3 0 0 0 0 3 0 9 9 3 3 9 9 9 3 3 9 9 9 9 3	3	Với D=3, vùng gồm các ô độ cao 0 và 3 (cách nhau ≤3) đã đủ ≥13 ô.

Bình luận

Không có bình luận tại thời điểm này.