trang chủ / đề bài / icpc25_reg_j

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 m hộ gia đình, đánh số từ 1 đến m, đ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ừ 1 đến 3. 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ó k loại cây có thể trồng, đánh số từ 1 đến k. Trong vụ thứ s, nếu hộ thứ i được giao trồng loại cây thứ j thì hộ đó làm ra một đơn vị nông sản mang lại lợi nhuận cs,i,j. 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ứ s (s≠2), chi phí chuyển nhóm của loại cây thứ j là xs,j2·ws,j, trong đó xs,j là số đơn vị nông sản loại cây thứ j gom được và ws,j là khối lượng của một đơn vị nông sản loại đó trồng trong vụ thứ s.
  • Do sức chứa của kho, tổng số đơn vị nông sản ∑j=1kxs,j của mọi loại cây bị giới hạn:
    • Ở vụ xuân, ∑j=1kx1,j≤a.
    • Ở vụ đông, ∑j=1kx3,j≤b.

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 p từ 1 đến 2·m, 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 p (tức là p=∑s=13∑j=1kxs,j, với x2,j là số đơn vị loại cây j 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 m,k,a,b (1≤m,k,a,b≤200): 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à 3 nhóm, mỗi nhóm m dòng. Nhóm thứ s mô tả lợi nhuận trong vụ thứ s:

  • Dòng thứ i của nhóm chứa k số nguyên cs,i,1,cs,i,2,…,cs,i,k (1≤cs,i,j≤109): lợi nhuận nếu hộ thứ i trồng loại cây thứ j trong vụ thứ s.

Dòng tiếp theo chứa k số nguyên w1,1,w1,2,…,w1,k (1≤w1,j≤109): khối lượng một đơn vị nông sản loại cây thứ j trồng trong vụ xuân.

Dòng cuối cùng chứa k số nguyên w3,1,w3,2,…,w3,k (1≤w3,j≤109): khối lượng một đơn vị nông sản loại cây thứ j trồng trong vụ đông.

Dữ liệu ra

In ra 2·m nhóm dòng; nhóm thứ p 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à p:

  • Nếu không có cách nào làm ra đúng p đơ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 bp (|bp|≤1018): lợi nhuận lớn nhất.
    • Dòng thứ i trong m dòng tiếp theo in ra ba số nguyên ti,1,ti,2,ti,3 (0≤ti,s≤k): loại cây giao cho hộ thứ i trong vụ xuân, vụ hè thu và vụ đông; ti,s=0 nghĩa là hộ thứ i không được giao cây nào trong vụ thứ s.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤m,k,a,b≤200.
  • 1≤cs,i,j≤109, 1≤w1,j,w3,j≤109.

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 p=1: hộ 2 trồng cây 1 vụ hè thu, lợi nhuận 3. Với p=2: cả hai hộ trồng cây 1 vụ hè thu, lợi nhuận 2+3=5. Với p=3: hộ 1 làm vụ hè thu (2), hộ 2 trồng cây 2 vụ xuân (15−22=−7) và cây 1 vụ đông (24−23=1), tổng −4. Với p=4: cả hai hộ phải làm cả vụ xuân lẫn vụ đông, nhưng kho vụ đông chỉ chứa b=1 đơ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 p=4: hộ 1 và hộ 2 làm vụ hè thu (9+9), hộ 3 trồng cây 2 vụ xuân (7−1=6) và cây 2 vụ đông (2−1=1), tổng 25. Không thể làm ra 5 hay 6 đơn vị vì vụ xuân chỉ chứa a=1 đơn vị và hộ làm vụ hè thu không làm thêm vụ nào khác.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0