Problem F
バラバラ問題
Languages
en
ja
![/problems/fallingapart/file/statement/ja/img-0001.jpg](/problems/fallingapart/file/statement/ja/img-0001.jpg)
アリスとボブは、新しい整数を手に入れて、カクテルパーティでそれを他のカップルに披露した後、よく眠るために家に向かいました。その整数がかなり大きかったので、彼らは一緒にそれを運ばざるを得ませんでした。その時、ベイズ湾の右の、ブール大通りを災害が襲いました。$2$ 人のどちらが最初につまづいたのかわかりませんが、彼らはつまづきました。そして彼らの前の道路で、それらの整数は $n$ 個の正の整数のピースに粉々に砕けました。
すでに高価な整数の取得のための財政的なストレス下にあった、このカップルの結婚は、この事件を乗り越えることができませんした。そして、ボブとアリスは分かれることを決心しました。そのため、どのように残った整数を分割するのかが問題となりました。ボブとアリスは、残りの $n$ 個のピースでゲームをプレイすることを決めました: $2$ 人は何も残らなくなるまで何度も、交互に交代でピースを選択します。
ボブとアリスは、共にとても利益を得たいので、出来るだけ整数の合計が最大になるように取得しようとします。それぞれの終わる整数の値を計算してください。両方のプレイヤーが最適にプレイすると仮定します。A がアルファベット順で B の前に来るので、アリスが最初に動きます。
入力
入力は2行で構成されます。
-
$1 \leq n \leq 15$の単一の整数、ピースの数。
-
スペースで区切られた $a_0, a_1, \dots , a_{n-1}$のピースの値。これは $1 \leq a_ i \leq 100$で与えられる。
出力
$2$つの整数を含む$1$行の出力、アリスのピースの値の合計とボブのピースの値の合計
サンプル入力 1 | サンプル出力 1 |
---|---|
3 3 1 2 |
4 2 |
サンプル入力 2 | サンプル出力 2 |
---|---|
4 1 2 2 1 |
3 3 |