FARMING - VNOI

FARMING - Nuga làm ruộng

Giới hạn

Thời gian: 1.6s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Nuga có M thửa ruộng rất rộng trên cánh đồng. Nhân dịp hè rảnh rỗi, Nuga quyết định sẽ trồng cây trên các thửa ruộng này để kiếm tiền đi du lịch.

Nuga sẽ canh tác trên các thửa ruộng một cách song song . Mỗi thửa ruộng có thể dùng để canh tác nhiều vụ , nhưng mỗi vụ chỉ được phép trồng một loại cây nhất định trên ruộng đó. Khi thu hoạch xong một vụ, Nuga có thể bắt đầu trồng vụ mới vào ngay ngày hôm sau , hoặc cũng có thể để không ruộng một thời gian rồi mới trồng vụ mới.

Có N loại cây trồng đánh số từ 1 đến N. Mỗi loại cây trồng có một đặc điểm riêng về giá hạt giống, thời gian canh tác, thu nhập hứa hẹn. Nuga dùng tiền vốn để mua hạt giống. Sau khi thu hoạch, thu nhập hứa hẹn sẽ được cộng vào số vốn mà bạn ấy có. Ngoài ra còn có đòi hỏi về kinh nghiệm canh tác, do mỗi loại cây cần có phương pháp chăm sóc riêng. Kinh nghiệm thu được khi trồng mỗi loại cây cũng khác nhau. Trồng càng nhiều vụ thì càng có nhiều kinh nghiệm, tức là kinh nghiệm thu được sau mỗi vụ sẽ được cộng vào tổng kinh nghiệm. Chi tiết về các thông tin trên được cho trong bảng sau:

Loại cây Đòi hỏi kinh nghiệm Thời gian canh tác (Ngày) Giá hạt giống (Đồng) Thu nhập hứa hẹn (Đồng) Kinh nghiệm thu được 1 R ₁ T ₁ S ₁ P ₁ E ₁ 2 R ₂ T ₂ S ₂ P ₂ E ₂ ... ... ... ... ... ... N R _N T _N S _N P _N E _N

Ban đầu Nuga chỉ có F đồng tiền vốn và G kinh nghiệm . Do thời gian nghỉ hè của Nuga có hạn nên bạn ấy chỉ muốn canh tác không quá D ngày để còn dành thời gian đi du lịch.

Bạn hãy giúp Nuga lập lịch canh tác sao cho thu được nhiều tiền nhất nhé!

Dữ liệu

- Dòng đầu chứa 5 số nguyên M, N, D, F, G.

- N dòng tiếp theo, dòng thứ i ghi 5 số nguyên R _i , T _i , S _i , P _i , E _i .

Kết quả

- Dòng đầu ghi tổng số tiền lớn nhất mà Nuga thu được sau không quá D ngày canh tác.

- M nhóm dòng tiếp theo, mỗi nhóm dòng ghi mô tả về quá trình canh tác trên một ruộng:

+ Dòng đầu tiên là một số nguyên X thể hiện số vụ cần canh tác trên ruộng đó.

+ Theo theo là X dòng mô tả về các vụ lần lượt theo thứ tự canh tác: Dòng thứ i gồm 2 số nguyên j, k thể hiện rằng Nuga cần trồng cây loại k trong vụ thứ i , bắt đầu từ ngày thứ j (tính từ lúc Nuga bắt đầu canh tác ruộng đầu tiên).

Giới hạn

- 1 ≤ M ≤ 50

- 1 ≤ N ≤ 50

- 1 ≤ D, T _i ≤ 100

- 1 ≤ G, R _i , E _i ≤ 1,000

- 1 ≤ F, S _i , P _i ≤ 100,000

Ví dụ

Dữ liệu

3 3 5 10000 5
5 3 3000 5000 2
10 2 7000 10000 3
10 1 6000 8000 2

Kết quả 1

Kết quả 2

Kết quả 3

Giải thích kết quả 3

Ngày canh tác thứ Ruộng 1 Ruộng 2 Ruộng 3 Tổng tiền (Đồng) Tổng kinh nghiệm Ban đầu - - - 10,000 5 1 Trồng cây 1 Trồng cây 1 Trồng cây 1 1,000 5 2 Chăm sóc Chăm sóc Chăm sóc 1,000 5 3 Thu hoạch Thu hoạch Thu hoạch 16,000 11 4 Trồng cây3
Thu hoạch Trồng cây 2 Để trống 11,000 13 5 Trồng cây3
Thu hoạch Thu hoạch Để trống 23,000 18

Tính điểm

- Với mỗi test, bạn chỉ được tính điểm nếu lịch gieo trồng hợp lí, đúng với số tiền kiếm được.

- Điểm mỗi test đúng đắn được tính dựa trên kết quả tốt nhất của tất cả các thí sinh (và của cả BTC)

Cụ thể, nếu kết quả tốt nhất là best, và chương trình của bạn đưa ra result thì:

Điểm = result/best * hệ số điểm. (Trong đó hệ số điểm = 100/tổng số test)

- Tổng điểm của bạn là tổng điểm các test đúng đắn.

- Với test ví dụ, best = 24000. Nếu hệ số điểm = 5, kết quả 1 sẽ được 4.58 điểm, kết quả 2 sẽ được 5.00 điểm, và kết quả 3 sẽ được 4.79 điểm.

Người up: voj
Nguồn bài: <a href="http://vn.spoj.pl/VM09/"> VNOI Marathon 2009 </a> <br/> Round 5 <br/> Problem Setter: Phạm Lê Quang