問題一覧 > 通常問題

No.937 Ultra Sword

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : leafirbyleafirby / テスター : otamay6otamay6
2 ProblemId : 3585 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-05 12:48:05

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 10^5$
    入力は全て整数である。

    出力

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

    サンプル

    サンプル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

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