|Nộp bài||Các bài nộp||Làm tốt nhất||Về danh sách bài|
FARMING - Nuga làm ruộng
Nuga has M large paddies on the field. This summer, she decides to cultivate fruits on those paddies to earn money for travelling.
The cultivation on those paddies are parallel. Each paddy can be used for many seasons, but Nuga can plant only one kind of fruits on that paddy each season. After havesting the fruit of a season, Nuga can cultivate the next season on the next day, or she can also keep the paddy empty for a while and cultivate later.
There are N kinds of fruits that are numbered from 1 to N. Each of them has its own characteristic of seed-price, time-until-harvest, promised-income. Nuga use her fund-money to buy seeds. When harvest, the promised-income will be added to her fund. More over, each fruit requires some experience of cultivation, that means Nuga can plant that fruit only if she has enough required-experience. After harvesting a season, Nuga gains some experience which depends on the kind of fruits of that season. Those experience will be added to her total-experience. Refer the following table for more details:
|Kinds of Fruits||Required Experience||Time until Harvest (Day)||Seed Price (VNĐ)||Promised Income (VNĐ)||Gained Experience|
At beginning, Nuga has only F VNĐ of fund and G experience. Because of the short summer, Nuga wants to cultivate in no more than D days, and then she can go travelling.
Please help Nuga to earn as much money as possible.
- The first line contains 5 integers M, N, D, F, G.
- N following lines, the ith line contains 5 integers Ri, Ti, Si, Pi, Ei.
- The first line contains the maximum possible amount of money that Nuga can earn in no more than D days.
- Following M groups of line, each contains information about the cultivations on a paddy:
+ Started by a line contains an integer X that stands for the number of seasons need to be cultivated.
+ The following X lines decribe about each season in the order of cultivations: The ith line contains 2 integers j, k describe that Nuga must plant the kth fruit in the ith season, at the jth day from when Nuga cultivated the first paddy.
- 1 ≤ M ≤ 50
- 1 ≤ N ≤ 50
- 1 ≤ D, Ti ≤ 100
- 1 ≤ G, Ri, Ei ≤ 1,000
- 1 ≤ F, Si, Pi ≤ 100,000
3 3 5 10000 5 5 3 3000 5000 2 10 2 7000 10000 3 10 1 6000 8000 2
22000 2 1 1 4 2 2 1 1 4 2 1 1 1
24000 3 1 1 4 3 5 3 3 1 1 4 3 5 3 1 1 1
23000 3 1 1 4 3 5 3 2 1 1 4 2 1 1 1
Explaination of output 3
|Day number||Paddy 1||Paddy 2||Paddy 3||Total fund(VNĐ)||Total experience|
|1||Plant fruit 1||Plant fruit 1||Plant fruit 1||1,000||5|
|4||Plant fruit 3
|Plant fruit 2||Empty||11,000||13|
|5||Plant fruit 3
- For each test case, you will get points if your schedule of cultivation are logical and matched with the maximum money.
- Points for each test case are calculated based on the best result of all contestants and the author.
If the best result is "best", and yours is "result", then your points are:
Points = result/best * coefficient. (Coefficient = 100/number_of_test_cases)
- Your total points = sum of all correct tests.
- With the example, best = 24000. If the cofficient = 5, output 1 will get 4.58 points, output 2 will get 5.00 points, and output 3 will get 4.79 points.
|Được gửi lên bởi:||VOJ Team|
|Thời gian chạy:||1.600s|
|Giới hạn mã nguồn:||50000B|
|Cluster:||Cube (Intel G860)|
|Ngôn ngữ cho phép:||Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET|
|Nguồn bài:||VNOI Marathon 2009|
Problem Setter: Phạm Lê Quang
các bác cho e hỏi e đc 100 là AC chưa ạ