|
|
Từ tập các bài có trên SPOJ (divb)
2866. Help the PM!
Mã bài: HELPPM
|
Giúp ngài thủ tướng!
Nãm 2050, lúc này Lê Ðôn Khuê ðã trở thành Thủ tướng Việt Nam. Ông nhận ðược một ðề nghị cho phép khai thác K m3 gỗ ở một khu rừng ðể xuất khẩu. Khu rừng này có dạng hình chữ nhật MxN km2. Ðể tiện quản lý thì người ta chia khu vực thành MxN vùng (M hàng, N cột) và lượng gỗ tại mỗi khu vực (tính theo m3) ðã ðược biết. Các hàng ðược ðánh số 1 ðến M từ trên xuống dưới. Các cột ðược ðánh số từ 1 ðến N từ trái sang phải. Tọa ðộ của vùng nằm tại hàng i, cột j là (i, j).
Ngài Thủ tướng quyết ðịnh cho phép khai thác và vùng khai thác ðể dễ quản lý nên là một vùng hình chữ nhật. Ngài Thủ tướng muốn tìm một phương án khai thác gỗ sao cho diện tích khai thác là nhỏ nhất và vẫn ðủ lượng gỗ cần thiết ðể xuất khẩu.
Do lâu ngày không lập trình nên ngài Thủ tướng cần ðến sự giúp ðỡ của các bạn. Các bạn hãy giúp ngài Thủ tướng nào.
|
|
Dữ liệu
- Dòng thứ nhất ghi ba số M, N, K (1 ≤ M, N ≤ 500, 1 ≤ K ≤ 109).
- Dòng thứ i trong M dòng tiếp theo ghi N số nguyên không âm, trong ðó số thứ j cho biết lượng gỗ tại khu vực (i, j). Biết lượng gỗ tại mỗi khu vực không vượt quá 104 m3.
Kết quả
Nếu không tồn tại vùng khai thác gỗ nào cho ðủ gỗ xuất khẩu, in ra -1. Ngược lại in ra:
- Dòng thứ nhất ghi diện tích nhỏ nhất có thể của vùng khai thác gỗ.
- Dòng tiếp theo ghi bốn số là chỉ số của góc trái trên và góc phải dưới của vùng khai thác gỗ. Nếu có nhiều vùng cùng thỏa mãn thì in ra tọa ðộ của một vùng bất kỳ.
Ví dụ
Dữ liệu
3 3 19
5 4 0
4 7 0
0 0 2
Kết quả
4
1 1 2 2
| Được gửi lên bởi: | Lê Ðôn Khuê |
| Ngày: | 2008-07-18 |
| Thời gian chạy: | 5s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK C++ 4.3.2 CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | VNOI Marathon '08 - Round 6/DivB
Problem Setter: Lê Ðôn Khuê |
|
|
|
|
