VM 08 Bài 07 - Hình chữ nhật

View as PDF

Submit solution


Points: 0.24 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 6/DivBProblem Setter: Lê Ðôn Khuê
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~ ~m^{3}~ gỗ ở một khu rừng để xuất khẩu. Khu rừng này có dạng hình chữ nhật ~M \times N~ ~km^{2}~. Để tiện quản lý thì người ta chia khu vực thành ~M \times N~ vùng ~(M~ hàng, ~N~ cột) và lượng gỗ tại mỗi khu vực (tính theo ~m^{3})~ đã đượ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.

Input

  • Dòng thứ nhất ghi ba số ~M~, ~N~, ~K~ ~(1 \leq M~, ~N \leq 500~, ~1 \leq K \leq 10^{9})~.
  • 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á ~10^{4} m^{3}~.

Output

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ỳ.

Sample Input

3 3 19
5 4 0
4 7 0
0 0 2

Sample Output

4
1 1 2 2

Comments

Please read the guidelines before commenting.



  • 5
    cbl_kiet   commented on March 24, 2022, 11:27 a.m.

    bài này test hơi yếu thì phải, trong lúc xử lý để n = m cũng AC