C - Kode Festival

Contest Duration: 2016-11-27(Sun) 05:25 - 2016-11-27(Sun) 06:55 (local time) (90 minutes)

C - Kode Festival Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $100$ 点

問題文

「硬度フェスティバル」は毎年開催される、世界で一番硬い石を決める大会です。

今年の硬度フェスティバルには $2^N$ 個の石が参加します。 $i$ 番目の石の硬度は $A_i$ です。

大会では石をトーナメント形式でぶつけ合って、最硬の石を決めます。

硬度 $X$ の石と硬度 $Y$ の石をぶつけると以下のような結果になります。

$X$ > $Y$ のとき：硬度が $Y$ だった石は砕けて、硬度が $X$ だった石の硬度は $X-Y$ になります。このとき硬度が $X$ だった石が勝ち残ります。
$X$ = $Y$ のとき：どちらかの石が砕けます。もう片方の石が硬度が元と変わらないまま残ります。このとき砕けなかった方の石が勝ち残ります。
$X$ < $Y$ のとき：硬度が $X$ だった石は砕けて、硬度が $Y$ だった石の硬度は $Y-X$ になります。このとき硬度が $Y$ だった石が勝ち残ります。

$2^N$ 個の石は以下のようなトーナメント形式で勝負をします。

( $1$ 番目の石、 $2$ 番目の石)、( $3$ 番目の石、 $4$ 番目の石)、... の組み合わせでぶつけ合う。
( $(1, 2)$ の勝ち残り、 $(3, 4)$ の勝ち残り)、( $(5, 6)$ の勝ち残り、 $(7, 8)$ の勝ち残り)、... の組み合わせでぶつけ合う。
同様に、勝ち残りが $1$ つだけになるまで続ける。

最後まで勝ち残る石の、最後の時点での硬度を求めてください。

制約

$1 \leq N \leq 18$
$1 \leq A_i \leq 10^9$
$A_i$ は整数である。

入力

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

 $N$ 
 $A_1$ 
 $A_2$ 
 $:$ 
 $A_{2^N}$

出力

最後まで勝ち残る石の、最後の時点での硬度を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $100$ points

Problem Statement

Kode Festival is an anual contest where the hardest stone in the world is determined. (Kode is a Japanese word for "hardness".)

This year, $2^N$ stones participated. The hardness of the $i$ -th stone is $A_i$ .

In the contest, stones are thrown at each other in a knockout tournament.

When two stones with hardness $X$ and $Y$ are thrown at each other, the following will happen:

When $X$ > $Y$ : The stone with hardness $Y$ will be destroyed and eliminated. The hardness of the stone with hardness $X$ will become $X-Y$ .
When $X$ = $Y$ : One of the stones will be destroyed and eliminated. The hardness of the other stone will remain the same.
When $X$ < $Y$ : The stone with hardness $X$ will be destroyed and eliminated. The hardness of the stone with hardness $Y$ will become $Y-X$ .

The $2^N$ stones will fight in a knockout tournament as follows:

The following pairs will fight: (the $1$ -st stone versus the $2$ -nd stone), (the $3$ -rd stone versus the $4$ -th stone), ...
The following pairs will fight: (the winner of ( $1$ -st versus $2$ -nd) versus the winner of ( $3$ -rd versus $4$ -th)), (the winner of ( $5$ -th versus $6$ -th) versus the winner of ( $7$ -th versus $8$ -th)), ...
And so forth, until there is only one stone remaining.

Determine the eventual hardness of the last stone remaining.

Constraints

$1 \leq N \leq 18$
$1 \leq A_i \leq 10^9$
$A_i$ is an integer.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$ 
 $A_2$ 
:
 $A_{2^N}$

Output

Print the eventual hardness of the last stone remaining.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy