//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Ban thưởng

Ceasar đại đế vừa ca khúc khải hoàn trở về sau trận chiến khốc liệt . Để thưởng công cho các tướng lĩnh , Caesar quyết định cấp đất cho họ . Thành Rome lúc bấy giờ được quy hoạch thành một hình chữ nhật kích thước N*M và được chia ra làm N*M ô vuông có diện tích bằng nhau . Trên bản đồ , mỗi ô vuông có một giá trị gọi là giá trị thuế . Giá trị này sẽ dương khi ô vuông này là đất thuộc về một tay chủ nô giàu có và giá trị sẽ âm nếu sống trên ô vuông này là tầng lớp dân nghèo . Caesar sẽ thưởng cho 1 vị tướng của mình một mảnh đất có dạng hình chữ nhật và mảnh đất này phải chứa trọn vẹn 1 số nguyên ô vuông . Giá trị thuế trên 1 mảnh đất sẽ tính bằng tổng giá trị thuế của các ô vuông thuộc mảnh đất . Caesar có K vị tướng và ông cần chọn ra K mảnh đất để ban thưởng sao cho 1 ô vuông chỉ thuộc không quá 1 vị tướng .Ngoài ra do ban đất sẽ làm Caesar kô thu được thuế ở các mảnh đất này nữa nên Caesar muốn tổng giá trị thuế của K mảnh đất này là nhỏ nhất . Bạn hãy lập trình giúp Caesar giải bài toán này.

Input: ROME.INP

  • Dòng đầu tiên chứa 3 số nguyên N, M, K.
  • N dòng tiếp, mỗi dòng ghi M số là tiền thuế của các ô.

Output: ROME.OUT

Gồm K dòng, dòng thứ i ghi tọa độ của góc trái trên và góc phải dưới của vị tướng thứ i.

Giới hạn:

  • 1 ≤ N, M ≤ 200
  • 1 ≤ K ≤ 15
  • Giá trị thuế có trị tuyệt đối không quá 1000.
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

ROME.INP ROME.OUT
3 3 2

-2 1 1

-3 2 1

3 -3 3

1 1 2 1

3 2 3 2

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: