問題一覧 > 通常問題

No.3642 OHO SHI KA TSU（Buying ver.）

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 7
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
ProblemId : 13630 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:37:20
Paken新入生コンday2の他の問題:

問題文

$N$ 個のグッズがあります。グッズ $i$ は $1$ 個購入するのに $W_i$ 円必要で、$1$ 個購入するたびに幸福度が $V_i$ 上昇します。販売量の調整のためグッズ $i$ は $1$ 回の買い物で $C_i$ 個までしか買うことができません。

また、$1$ 回の買い物で $X$ 円を支払うたびに幸福度が $Y$ 上昇する特典が無料で $1$ つ手に入ります。つまり、あなたが $1$ 回の買い物で $x$ 円支払った場合、追加で幸福度が $\displaystyle\left\lfloor \frac{x}{X}\right\rfloor\times Y$ 上昇します。

適切にグッズを1つ以上買ったとき、$1$ 回の買い物での $\displaystyle\frac{幸福度の合計}{支払った金額}$ を最大でいくつにできるかを求めてください。

制約

  • $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$
  • 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題15 %$N=1$
小課題23 %$Y=0$
小課題32 %$X=1$
小課題410 %$N \le 20,\ C_i=1$
小課題515 %$N \le 8,\ C_i \le 5$
小課題620 %$N\leq 100,\ C_i=1$
小課題730 %入力で与えられる値は全て $100$ 以下
小課題815 %追加の制約はない

入力

$N\ X\ Y$
$W_1\ V_1\ C_1$
$W_2\ V_2\ C_2$
$\vdots$
$W_N\ V_N\ C_N$

出力

答えを一行に出力してください。

真の解との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定されます。

サンプル

サンプル1
入力
4 6 3
2 2 3
3 3 2
4 1 1
8 9 2
出力
1.611111111

グッズ $1$ を $1$ 個、グッズ $4$ を $2$ 個買うことを考えます。支払う金額は $18$、グッズだけの幸福度の合計は $20$ です。

特典は $\displaystyle\left\lfloor\frac{19}{6}\right\rfloor=3$ 個手に入れることができ、追加で幸福度が $9$ 上昇します。

よってこの場合は $\displaystyle\frac{29}{18}$ となります。$\displaystyle\frac{29}{18}$ より大きい値を達成することはできないため、$\displaystyle\frac{29}{18}$ が答えになります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。