Giúp giải bài toán cắt hình chữ nhật thành nhiều phần nhất mà không quá k lần cắt

Giúp em với em đang cần bài này gấp mà không biết làm sao, em cảm ơn

Bài toán: Chia quả

Vào ngày phụ nữ Việt Nam 20/10, Ngọc được tặng một miếng chocolate cực lớn có dạng hình chữ nhật kích thước MxN được chia thành lưới ô vuông đơn vị (M hàng và N cột). Tất nhiên, Ngọc rất hạnh phúc và muốn chia sẻ cùng bạn bè. Ngọc muốn cắt miếng chocolate ra làm nhiều mảnh để chia cho các bạn. Biết rằng Ngọc được sử dụng không quá k lần cắt thuộc một trong hai loại sau:

  • Cắt ngang miếng chocolate từ trái qua phải theo rãnh giữa hai hàng ô liên tiếp.
  • Cắt dọc miếng chocolate từ trên xuống dưới theo rãnh giữa hai cột ô liên tiếp.

Yêu cầu: Giúp Ngọc tìm cách cắt để chia miếng chocolate ra làm nhiều phần nhất.

Dữ liệu: Vào từ file văn bản CUT.INP gồm một dòng chứa ba số nguyên M, N, k <= 10^9 cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản CUT.OUT một số nguyên duy nhất là số phần chocolate rời nhau sau nhiều nhất khi cắt theo phương án tìm được.

Ví dụ

CUT.INP CUT.OUT
4 5 3 6

Người thảo luận để tìm ra cách giải hay cho một bài toán khó sẽ trở thành lập trình viên giỏi. Người hay hỏi bài tập thì không. Còn bạn thì sao?

1 Like
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?