No.549 素材合成システム
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 251
作問者 :
nanae
/ テスター :
はむこ
タグ : / 解いたユーザー数 251
作問者 :
nanae
/ テスター :
はむこ
問題文最終更新日: 2017-07-27 23:21:30
問題文
あなたはYukicoder's Gateというソーシャルゲームで遊んでいます。
Yukicoder's Gateは複数のアンドロイドを育てるRPGです。
あなたは今$N$人のアンドロイドを所持しており、それらの経験値はそれぞれ
$x_1, x_2, \dots, x_N$ となっています。
あなたはこの$N$人のアンドロイドを合成システムにより、1人のアンドロイドにまとめようと思っています。
ここで合成システムの詳細は次のようになっています。
- 素材アンドロイドの経験値を$a$, 被合成アンドロイドの経験値を$b$とする
- 被合成アンドロイドの経験値に、素材アンドロイドの経験値の半分切り捨ての値が加算される
- すなわち合成により、被合成アンドロイドの経験値は $b + \left \lfloor \frac{a}{2} \right \rfloor$となる
- 素材アンドロイドは消滅する
最後に残る1人のアンドロイドの経験値としてあり得る最大値を求めてください。
入力
$N$ $x_1$ $x_2$ ... $x_N$
一行目にあなたが所持しているアンドロイドの数$N$が与えられます。
二行目に各アンドロイドの経験値$x_i$が半角スペース区切りで与えられます。
制約は以下の通りです。
- $2 \leq N \leq 10^5$
- $1 \leq x_i \leq 10^4$
- 入力は全て整数で与えられる
出力
最後に残る1人のアンドロイドの経験値としてあり得る最大値
最後に改行してください。
サンプル
サンプル1
入力
3 1 2 3
出力
4
このとき、以下のような合成手順で合成していくと、経験値4のアンドロイドが残ります。
- アンドロイド2をアンドロイド1へ合成すると、アンドロイド1の経験値は2になり、アンドロイド2は消滅する
- 残るアンドロイドの経験値は2, x, 3となります（xはアンドロイドが消滅していることを表す）
- アンドロイド1をアンドロイド3へ合成すると、アンドロイド3の経験値は4となり、アンドロイド1は消滅します
- 残るアンドロイドの経験値はx, x, 4 となり、これで合成が終了します
サンプル2
入力
5 2 2 2 2 2
出力
6
このときは「アンドロイド$i(>1)$をアンドロイド1へ合成する」を繰り返すことで 経験値6のアンドロイドが残り、これが最大値となります。
サンプル3
入力
16 5 48 74 84 94 13 24 15 92 79 74 89 32 30 5 24
出力
435
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。