No.937 Ultra Sword

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : leafirbyleafirby / テスター : otamay6otamay6
1 ProblemId : 3585 / 出題時の順位表
問題文最終更新日: 2019-12-01 01:14:24

11/30 17:55追記)テストケースに、after_contestを追加しました。

問題文

勇者$null$くんは、ウルトラソードを手に入れました。
ダンジョンには$N$匹のモンスターがいて、$i$体目のモンスターの$HP$は$A_i$です。
$null$くんはウルトラソードを振ることで,$i$番目のモンスター$1$体を生贄にして,そのモンスターの$HP$の正整数倍の$HP$を持つ、
すべてのモンスターの$HP$を$A_i$で割った値まで削ることができます。
このとき,生贄にされたモンスターの$HP$は$1$になり、ウルトラソードは壊れてしまうのでウルトラソードを$2$回以上振ることはできません。
また、$null$くんは優れた魔術師でもあり、何度でも以下の$3$種類の魔法を使うことができます。

  • $HP$が異なる$2$匹のモンスター$(i,j)$を選び,$A_i\ xor\ A_j$の$HP$を持つモンスターを作る。
  • $1$匹のモンスター$(i)$を選び,$A_i$の$2$倍の$HP$を持つモンスターを作る。
  • 自分で作った全てのモンスターの$HP$を$0$にする。
  • ウルトラソードと魔法を使う順番は自由です。
    このとき,$null$くんは全てのモンスターの$HP$の総和をできるだけ小さくしたいです。適切に行動したときの全てのモンスターの$HP$の総和の最小値を求めてください。
    ただし、$xor$は$bit$ごとの排他的論理和を表します。

    入力

    $N$
    $A_1,A_2,....A_N$

    $2\le N \le 10^5$
    $1\le A_i\le 100000$
    入力は全て整数である。

    出力

    最後に改行してください。

    サンプル

    サンプル1
    入力
    3
    10 20 30
    出力
    6

    $1$体目のモンスターを生贄としてウルトラソードを振ると、$2$体目のモンスターの$HP$は$2$になり、
    $3$体目のモンスターの$HP$は$3$になるので、全てのモンスターの$HP$の総和は$6$になり、これが最小です。

    サンプル2
    入力
    4
    28 24 32 20
    出力
    26

    $1$体目のモンスターと$2$体目のモンスターの$HP$の$xor$をとった$HP$を持つモンスターを作ります。(これを$5$体目のモンスターと呼びます。)
    $5$体目のモンスターの$HP$は$4$で、$5$体目のモンスターを生贄としてウルトラソードを振ると、全てのモンスターの$HP$の総和は$27$になります。
    このとき、$3$つ目の魔法を使うと、$5$体目のモンスターの$HP$は$0$となり、全てのモンスターの$HP$の総和は$26$となり、これが最小です。

    サンプル3
    入力
    5
    232 232 232 232 232
    出力
    5

    提出ページヘ
    下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

    言語
    問題によって提出できない言語があります。参考
    ソースコード
    ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
    テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。