No.3642 OHO SHI KA TSU (Buying ver.)
タグ : / 解いたユーザー数 9
作問者 :
kazuppa
/ テスター :
Problem Statement
There are $N$ goods. Buying $1$ unit of goods $i$ costs $W_i$ yen, and each time you buy $1$ unit, your happiness increases by $V_i$. To regulate sales volume, you can buy at most $C_i$ units of goods $i$ in $1$ shopping trip.
Also, in $1$ shopping trip, each time you pay $X$ yen, you receive for free $1$ bonus item that increases your happiness by $Y$. That is, if you pay $x$ yen in $1$ shopping trip, your happiness additionally increases by $\displaystyle\left\lfloor \frac{x}{X}\right\rfloor\times Y$.
Choosing appropriately and buying 1 or more goods, find the maximum possible value of $\displaystyle\frac{幸福度の合計}{支払った金額}$ (total happiness divided by the amount paid) in $1$ shopping trip.
Constraints
- $1\leq N\leq 500$
- $1\leq X\leq 500$
- $0\leq Y\leq 500$
- $1\leq W_i\leq 500$
- $1\leq V_i\leq 500$
- $1\leq C_i\leq 500$
- All inputs are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask Name | Score | Constraints |
|---|---|---|
| Subtask 1 | 5 % | $N=1$ |
| Subtask 2 | 3 % | $Y=0$ |
| Subtask 3 | 2 % | $X=1$ |
| Subtask 4 | 10 % | $N \le 20,\ C_i=1$ |
| Subtask 5 | 15 % | $N \le 8,\ C_i \le 5$ |
| Subtask 6 | 20 % | $N\leq 100,\ C_i=1$ |
| Subtask 7 | 30 % | All values given in the input are at most $100$ |
| Subtask 8 | 15 % | No additional constraints |
Input
$N\ X\ Y$ $W_1\ V_1\ C_1$ $W_2\ V_2\ C_2$ $\vdots$ $W_N\ V_N\ C_N$
Output
Output the answer on one line.
Your answer is judged correct if its absolute or relative error from the true answer is at most $10^{-6}$.
Sample
Sample 1
Input
4 6 3 2 2 3 3 3 2 4 1 1 8 9 2
Output
1.611111111
Consider buying goods $1$ in a quantity of $1$ unit and goods $4$ in a quantity of $2$ units. The amount paid is $18$, and the total happiness from the goods alone is $20$.
You can obtain $\displaystyle\left\lfloor\frac{19}{6}\right\rfloor=3$ bonus items, which additionally increase your happiness by $9$.
Therefore, the value in this case is $\displaystyle\frac{29}{18}$. No value greater than $\displaystyle\frac{29}{18}$ can be achieved, so $\displaystyle\frac{29}{18}$ is the answer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。