LANDK - Mua đất
Giới hạn- Thời gian: 0.6s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Mua đất
Sau nhiều năm, Lisa đã tích cóp được số tiền và muốn mua 1 mảnh đất ở khu đất phía ngoại ô thành phố. Để đơn giản, ta coi khu đất này là một hình vuông kích thước n * n, đã được chia thành các ô vuông nhỏ kích thước 1 * 1. Do mỗi ô đất có địa thế khác nhau, nên giá trị của chúng cũng rất khác nhau. Giá trị của một mảnh đất, được tính là tổng của tất cả các ô đất trong đó.
Ban đầu, Lisa có k đồng. Được bạn bè hỗ trợ, Lisa vay được thêm k đồng nữa. Chính vì vậy, cô mới đặt ra 1 yêu cầu mua đất rất oái oăm như sau: Mảnh đất phải có dạng hình chữ nhật
Các cạnh của mảnh đất song song với các cạnh của khu đất n * n
Giá của mảnh đất này ít nhất là k, và không vượt quá 2k (Lisa không muốn vay quá nhiều)
Bạn hãy viết chương trình giúp Lisa mua được mảnh đất ưng ý
Input
Dòng đầu tiên ghi 2 số nguyên dương k và n: số tiền ban đầu của Lisa và kích thước của khu đất (1 <= k <= 10^9, 1 <= n <= 2000).
N dòng sau, mỗi dòng gồm n số nguyên dương mô tả giá của các ô đất. a_ij (1 <= a_ij <= 2.10^9) là giá của ô đất nằm ở vị trí (i,j) (các ô được đánh số từ 1 -> n theo chiều từ trái qua phải và từ trên xuống dưới). Các số được cách nhau bởi khoảng trắng
Output
Nếu không tồn tại mảnh đất thỏa mãn yêu cầu của Lisa, in “NIE” (không có dấu ngoặc kép)
Ngược lại, in ra 4 số nguyên dương là tọa độ ô trái trên và ô phải dưới của mảnh đất chọn được (lưu ý ghi theo thứ tự cột trước, hàng sau). Nếu có nhiều kết quả, bạn chỉ cần in ra 1 kết quả tùy ý
Ví dụ
Input 4 3 1 1 1 1 9 1 1 1 1 Output NIE Input 8 4 1 2 1 3 25 1 2 1 4 20 3 3 3 30 12 2 Output 2 1 4 2
- Người up: paulmcvn
- Nguồn bài: POI 2007, cảm ơn bạn Nguyễn Vương Linh