問題一覧 > 通常問題

No.3642 OHO SHI KA TSU (Buying ver.)

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 9
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
お気に入りにしたユーザー ProblemId : 13630 / 自分の提出
問題文最終更新日: 2026-08-25 18:37:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Paken新入生コンday2 (順位表) の他の問題:

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 15 %$N=1$
Subtask 23 %$Y=0$
Subtask 32 %$X=1$
Subtask 410 %$N \le 20,\ C_i=1$
Subtask 515 %$N \le 8,\ C_i \le 5$
Subtask 620 %$N\leq 100,\ C_i=1$
Subtask 730 %All values given in the input are at most $100$
Subtask 815 %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もしくは右上の雲マークをクリックしてアカウントを作成してください。