P8826 [Chuanzhi Cup #3 Preliminary] Game (Call for Testdata)

Qingzhengyu is an unbeaten player in the game “Chilan Xianye”. One day, he encountered the following game: You are given an array $a$ of length $n$. Also define $count(x)$ as the number of $1$ bits in the binary representation of $x$. Each time, Qingzhengyu can perform one of the following two operations: - Choose two numbers $a_i, a_j$, and it must satisfy $count(a_i \operatorname{xor} a_j)=1$. Delete either one of them from the array, with cost $C_1$. - Choose two numbers $a_i, a_j$, and it must satisfy $count(a_i \operatorname{xor} a_j) > 1$. Delete either one of them from the array, with cost $C_2$. You want to know the minimum total cost to delete numbers until only one number remains in the array.

The first line contains an integer $n$, which is the size of the array. The second line contains two integers $C_1, C_2$, with meanings as described above. The third line contains $n$ integers, describing the array $a$.

Output one integer in one line, representing the minimum cost.

For $20\%$ of the testdata, $n = 10$. For another $20\%$ of the testdata, the elements in $a$ form a permutation of $[1, n]$. For $100\%$ of the testdata, $1 \leq n \leq {10}^4$, $1 \le C_1, C_2, a \le {10}^9$, and all elements in $a$ are distinct. Translated by ChatGPT 5