Hợp tác xã nông nghiệp
Đề bài
Mô tả
Một hợp tác xã nông nghiệp gồm hộ gia đình, đánh số từ đến , đang lên kế hoạch sản xuất cho năm tới để tối đa lợi nhuận. Đây là bài toán năm nào hợp tác xã cũng phải giải, vì có nhiều yếu tố ảnh hưởng đến sản lượng như khí hậu, loại cây trồng, vận chuyển và lưu kho.
Trong một năm có ba vụ: vụ xuân, vụ hè thu và vụ đông, lần lượt đánh số từ đến . Trong mỗi vụ, hợp tác xã có thể giao cho mỗi hộ trồng nhiều nhất một loại cây. Theo số liệu các năm trước, có loại cây có thể trồng, đánh số từ đến . Trong vụ thứ , nếu hộ thứ được giao trồng loại cây thứ thì hộ đó làm ra một đơn vị nông sản mang lại lợi nhuận . Hộ không được giao cây thì không canh tác trong vụ đó.
Khí hậu địa phương cũng đặt ra một số ràng buộc về vận chuyển và lưu kho. Trong vụ hè thu, người mua đến tận ruộng để mua nông sản nên không tốn chi phí vận chuyển và lưu kho. Còn ở vụ xuân và vụ đông, toàn bộ nông sản được gom lại và chuyển về kho vào cuối vụ.
- Trước khi chuyển về kho, các đơn vị nông sản được gom thành nhóm theo loại cây. Cuối vụ thứ (), chi phí chuyển nhóm của loại cây thứ là , trong đó là số đơn vị nông sản loại cây thứ gom được và là khối lượng của một đơn vị nông sản loại đó trồng trong vụ thứ .
- Do sức chứa của kho, tổng số đơn vị nông sản của mọi loại cây bị giới hạn:
- Ở vụ xuân, .
- Ở vụ đông, .
Ràng buộc cuối cùng đến từ chính người nông dân. Một hộ có thể được giao canh tác ở nhiều vụ, nhưng không hộ nào đồng ý canh tác ở hai vụ liên tiếp. Vì vụ hè thu có lợi thế rõ rệt, các hộ nói rằng nếu đã làm vụ hè thu thì họ chỉ làm vụ đó và hài lòng với sản lượng thu được.
Số hộ ngày càng tăng khiến việc lập kế hoạch ngày càng phức tạp, nên hợp tác xã nhờ bạn tính toán để có cái nhìn rõ hơn trước khi triển khai. Với mỗi từ đến , hãy giúp hợp tác xã tìm lợi nhuận lớn nhất cùng một cách phân công tối ưu khi tổng số đơn vị nông sản làm ra trong cả ba vụ đúng bằng (tức là , với là số đơn vị loại cây làm ra trong vụ hè thu). Lợi nhuận của một cách phân công là tổng lợi nhuận của mọi đơn vị nông sản trừ đi tổng chi phí chuyển về kho của vụ xuân và vụ đông.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên (): số hộ trong hợp tác xã, số loại cây có thể trồng, sức chứa của kho trong vụ xuân và sức chứa của kho trong vụ đông.
Tiếp theo là nhóm, mỗi nhóm dòng. Nhóm thứ mô tả lợi nhuận trong vụ thứ :
- Dòng thứ của nhóm chứa số nguyên (): lợi nhuận nếu hộ thứ trồng loại cây thứ trong vụ thứ .
Dòng tiếp theo chứa số nguyên (): khối lượng một đơn vị nông sản loại cây thứ trồng trong vụ xuân.
Dòng cuối cùng chứa số nguyên (): khối lượng một đơn vị nông sản loại cây thứ trồng trong vụ đông.
Dữ liệu ra
In ra nhóm dòng; nhóm thứ mô tả cách phân công tối ưu khi tổng số đơn vị nông sản làm ra trong năm là :
- Nếu không có cách nào làm ra đúng đơn vị nông sản mà vẫn thỏa mọi yêu cầu, in ra impossible.
- Ngược lại:
- Dòng đầu tiên in ra số nguyên (): lợi nhuận lớn nhất.
- Dòng thứ trong dòng tiếp theo in ra ba số nguyên (): loại cây giao cho hộ thứ trong vụ xuân, vụ hè thu và vụ đông; nghĩa là hộ thứ không được giao cây nào trong vụ thứ .
Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 2 1 5 10 10 15 2 1 3 2 6 9 24 17 18 22 23 17 |
3 0 0 0 0 1 0 5 0 1 0 0 1 0 -4 0 1 0 2 0 1 impossible |
Với : hộ trồng cây vụ hè thu, lợi nhuận . Với : cả hai hộ trồng cây vụ hè thu, lợi nhuận . Với : hộ làm vụ hè thu (), hộ trồng cây vụ xuân () và cây vụ đông (), tổng . Với : cả hai hộ phải làm cả vụ xuân lẫn vụ đông, nhưng kho vụ đông chỉ chứa đơn vị. |
| 3 2 1 2 4 1 1 1 2 7 9 9 1 9 6 6 5 8 8 5 1 2 3 1 1 1 |
9 0 1 0 0 0 0 0 0 0 18 0 1 0 0 2 0 0 0 0 24 0 1 0 0 2 0 0 1 0 25 0 1 0 0 2 0 2 0 2 impossible impossible |
Ví dụ bổ sung (không có trong đề gốc). Với : hộ và hộ làm vụ hè thu (), hộ trồng cây vụ xuân () và cây vụ đông (), tổng . Không thể làm ra hay đơn vị vì vụ xuân chỉ chứa đơn vị và hộ làm vụ hè thu không làm thêm vụ nào khác. |
Bình luận