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

Bài tập huấn luyện: Bày cỗ Trung thu

 

Rằm Trung thu năm nay, thầy My quyết định tổ chức một buổi phá cỗ trông trăng. Thầy mua về rất nhiều quả các loại rồi bảo 2 admin của IOICamp là beo_chay_so và hard7771988 bày cỗ.

Bàn cỗ là một hình chữ nhật kích thước M dòng và N cột được chia thành M x N ô vuông đơn vị. 2 admin của chúng ta cần bày K quả thuộc các loại khác nhau lên bàn, biết rằng mỗi ô được phép đặt không quá một quả và một số ô sẽ dành bày bánh trung thu nên không thể đặt quả ở đó.

beo_chay_so vốn tính tham ăn nên muốn nếm thử trước một vài quả, vì thế, beo_chay_so lấy cớ là các quả có kích thước và khối lượng không bằng nhau nên đặt lên bàn sẽ không cân!!! Cậy mình là đàn anh, beo_chay_so bắt hard phải xếp các quả sao cho trọng tâm của hệ K quả này cách tâm của bàn ít nhất. Biết rằng quả thứ i có khối lượng là Wi và có thể coi gần đúng như một chất điểm (nghĩa là không có kích thước) và khi xếp thì trọng tâm của quả này luôn nằm ở chính giữa ô vuông được xếp.

Đối với hard thì yêu cầu trên quả là khó, vì vậy hard nhờ các thành viên IOICamp viết chương trình tìm cách giải (beo_chay_so đã dọa hard là nếu kết quả quá yếu kém thì beo_chay_so sẽ cắn bớt vài miếng ở các quả để bàn cỗ “cân” trở lại).

InputTABLE.INP

  • Dòng thứ nhất ghi 3 số nguyên dương M, N và K.
  • Dòng thứ i trong số M dòng tiếp theo ghi N số 1 hoặc 0 ứng với ô tại dòng i, cột j của bàn có thể / không thể đặt được quả.
  • Trong một số dòng tiếp theo ghi K số nguyên dương, số thứ i là khối lượng Wi của quả thứ i.

Output:            TABLE.OUT

Ghi ra M dòng, dòng thứ i ghi N số nguyên Ci1, Ci2, …, CiN mà Cij bằng:

  • 0 nếu như ô tại dòng i và cột j không đặt quả.
  • Thứ tự của quả (đã cho trong file Input) đặt tại ô ở dòng i và cột j nếu như ô này có đặt quả.

Giới hạn:

  • 1 ≤ M, N ≤ 300
  • Số quả không vượt quá số ô được phép đặt quả.
  • 1 ≤ Wi ≤ 109
  • Thời gian: 2 s/test
  • Bộ nhớ: 4 MB

Ví dụ:

TABLE.INP TABLE.OUT
2 3 4

1 0 1

0 1 1

1 3 4

6

4 0 2

0 1 3

 

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: