F - Spices

Contest Duration: 2022-01-23(Sun) 12:00 - 2022-01-23(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Spices Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

スパイス屋には、スパイス $1$ 、スパイス $2$ 、 $\ldots$ 、スパイス $2^N-1$ の $2^N-1$ 種類のスパイスがそれぞれ $1$ 個ずつ売られています。 $i = 1, 2, \ldots, 2^N-1$ について、スパイス $i$ の値段は $c_i$ 円です。高橋君はそれらを好きなだけ買うことができます。

高橋君は帰宅後、買ったスパイスのうち $1$ つ以上を選び、それらを組み合わせてカレーを作る予定です。
高橋君がスパイス $A_1$ 、スパイス $A_2$ 、 $\ldots$ 、スパイス $A_k$ の $k$ 個のスパイスを組み合わせると、完成するカレーの辛さは $A_1 \oplus A_2 \oplus \cdots \oplus A_k$ になります。ここで、 $\oplus$ はビットごとの排他的論理和を表します。

高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず $1$ 以上 $2^N-1$ 以下の任意の整数の辛さのカレーを作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してください。

制約

$2 \leq N \leq 16$
$1 \leq c_i \leq 10^9$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $c_1$   $c_2$   $\ldots$   $c_{2^N-1}$

出力

高橋君が支払う金額としてあり得る最小値を出力せよ。

入力例 1Copy

Copy

2
4 5 3

出力例 1Copy

Copy

高橋君がスパイス $1$ とスパイス $3$ を買うと、下記の通り、 $1$ 以上 $3$ 以下の任意の整数の辛さのカレーを作ることができます。

辛さ $1$ のカレーを作るには、スパイス $1$ のみを使い、
辛さ $2$ のカレーを作るには、スパイス $1$ とスパイス $3$ を組み合わせ、
辛さ $3$ のカレーを作るには、スパイス $3$ のみを使えば良いです。

このとき高橋君が支払う金額は $c_1 + c_3 = 4 + 3 = 7$ 円であり、これが高橋君が支払う金額としてあり得る最小値です。

入力例 2Copy

Copy

4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

出力例 2Copy

Copy

Score : $500$ points

Problem Statement

The shop supaisu-ya sells $2^N-1$ kinds of spices: Spice $1$ , Spice $2$ , $\ldots$ , Spice $2^N-1$ . One pack of each spice is in stock. For each $i = 1, 2, \ldots, 2^N-1$ , Spice $i$ costs $c_i$ yen. Takahashi can buy any of these spices.

He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If $k$ spices, Spice $A_1$ , Spice $A_2$ , $\ldots$ , Spice $A_k$ , are mixed, the hotness of the resulting curry is $A_1 \oplus A_2 \oplus \cdots \oplus A_k$ , where $\oplus$ denotes the bitwise XOR.

Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from $1$ through $2^N-1$ . Print the minimum possible amount of money Takahashi pays.

Constraints

$2 \leq N \leq 16$
$1 \leq c_i \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $c_1$   $c_2$   $\ldots$   $c_{2^N-1}$

Output

Print the minimum possible amount of money Takahashi pays.

Sample Input 1Copy

Copy

2
4 5 3

Sample Output 1Copy

Copy

If Takahashi buys Spice $1$ and $3$ , he can make curry of any hotness from $1$ through $3$ , as follows.

To make curry of hotness $1$ , use just Spice $1$ .
To make curry of hotness $2$ , mix Spice $1$ and Spice $3$ .
To make curry of hotness $3$ , use just Spice $3$ .

Here, Takahashi pays $c_1 + c_3 = 4 + 3 = 7$ yen, which is the minimum possible amount he pays.

Sample Input 2Copy

Copy

4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

Sample Output 2Copy

Copy