[AtCoder] ABC 138 C – Alchemist

問題

方針

食材の価値

\( 1 \) 回の合成で使用された食材の価値は半減します。食材 \( i \) が合成に使われた回数を \( a_i \) とし、最終的な価値を \( f \) とすると、

\[f = \dfrac{v_1}{2^{a_1}} + \dfrac{v_2}{2^{a_2}} + \cdots +\dfrac{v_N}{2^{a_N}} \]

となります。価値の大きいものの合成回数が増えると \( f \) の値が小さくなるので、価値が低い食材を合成に多く使われた方が良いです。例えば、\( N = 4 \) のとき、\( v_i \leq v_{i+1} \) のように昇順に整列されているとすると、

\[
\begin{eqnarray}
\dfrac{v_1 + v_2 + v_3 + v_4}{4} &\leq& \dfrac{v_1 + v_2}{8} + \dfrac{v_3}{4} + \dfrac{v_4}{2}\\
\dfrac{2v_1 + 2v_2 + 2v_3 + 2v_4}{8} &\leq& \dfrac{v_1 + v_2 + 2v_3 + 4v_4}{8}
\end{eqnarray}
\]

となることが分かります。

コード