問題一覧 > 通常問題

No.937 Ultra Sword

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 30
作問者 : leafirby / テスター : otamay6
お気に入りにしたユーザー ProblemId : 3585 / 自分の提出
問題文最終更新日: 2020-05-05 12:48:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 232 (順位表) の他の問題:

Added 11/30 17:55) after_contest has been added to the test cases.

Problem Statement

The hero $null$ has obtained the Ultra Sword.
There are $N$ monsters in the dungeon, and the $HP$ of the $i$-th monster is $A_i$.
By swinging the Ultra Sword, $null$ can sacrifice $1$ monster, the $i$-th one, and for all monsters having $HP$ that is a positive integer multiple of that monster's $HP$,
reduce their $HP$ down to the value obtained by dividing it by $A_i$.
When this happens, the $HP$ of the sacrificed monster becomes $1$ and the Ultra Sword breaks, so the Ultra Sword cannot be swung $2$ or more times.
In addition, $null$ is also an excellent magician and can use the following $3$ types of magic any number of times.

  • Choose $2$ monsters $(i,j)$ with different $HP$ and create a monster with $HP$ equal to $A_i\ xor\ A_j$.
  • Choose $1$ monster $(i)$ and create a monster whose $HP$ is $2$ times $A_i$.
  • Set the $HP$ of all monsters you have created to $0$.
  • The Ultra Sword and the magic may be used in any order.
    Here, $null$ wants to make the sum of the $HP$ of all monsters as small as possible. Find the minimum possible sum of the $HP$ of all monsters when acting optimally.
    Here, $xor$ denotes the exclusive OR taken per $bit$.

    Input

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

    $2\le N \le 10^5$
    $1\le A_i\le 10^5$
    All inputs are integers.

    Output

    Print a newline at the end.

    Sample

    Sample 1
    Input
    3
    10 20 30
    Output
    6

    If you swing the Ultra Sword sacrificing the $1$st monster, the $HP$ of the $2$nd monster becomes $2$, and
    the $HP$ of the $3$rd monster becomes $3$, so the sum of the $HP$ of all monsters becomes $6$, which is the minimum.

    Sample 2
    Input
    4
    28 24 32 20
    Output
    26

    Create a monster whose $HP$ is the $xor$ of the $HP$ of the $1$st monster and the $2$nd monster. (Call this the $5$th monster.)
    The $HP$ of the $5$th monster is $4$, and swinging the Ultra Sword with the $5$th monster as the sacrifice makes the sum of the $HP$ of all monsters $27$.
    Then, using the $3$rd magic makes the $HP$ of the $5$th monster $0$, and the sum of the $HP$ of all monsters becomes $26$, which is the minimum.

    Sample 3
    Input
    5
    232 232 232 232 232
    Output
    5

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