日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

問題文

JOI 高校の葵さんは，数列に対して，隣り合う各項の差の絶対値を順に並べた数列を考えるのが好きである．

はじめ，黒板には長さ N の数列 A₁, A₂, …, A_N が書かれている．

葵さんは以下の操作を N - 1 回繰り返す．

• 黒板に書かれている数列の長さが m であり，その数列が b₁, b₂, …, b_m であるとする． 黒板に書かれている数列 b₁, b₂, …, b_m を消し，長さ m-1 の数列 |b₁ - b₂|, |b₂ - b₃|, …, |b_m-1 - b_m| を新たに黒板に書く．ただし，|x| は x の絶対値を表す．

N - 1 回の操作が終了した後，黒板には 1 つの値（長さ 1 の数列）が書かれている．

はじめ黒板に書かれていた数列の情報が与えられるので，N - 1 回の操作が終了した後黒板に書かれている値を求めるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 2 000．
• 0 ≦ A_i ≦ 10⁹．
• 入力される値はすべて整数である．

小課題

1. (25 点) N=2．
2. (75 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁ A₂ … A_N

出力

N - 1 回の操作が終了した後黒板に書かれている値を出力せよ．

入出力例

入力例 1
4
3 1 4 1

出力例 1
1

はじめ黒板には長さ 4 の数列 3,1,4,1 が書かれている．

葵は (4-1=)3 回の操作を行う．

• 1 回目の操作では，黒板から長さ 4 の数列 3,1,4,1 を消し，長さ 3 の数列 2,3,3 を書く．
• 2 回目の操作では，黒板から長さ 3 の数列 2,3,3 を消し，長さ 2 の数列 1,0 を書く．
• 3 回目の操作では，黒板から長さ 2 の数列 1,0 を消し，長さ 1 の数列 1 を書く．

3 回の操作が終了した後に黒板に書かれている値は 1 であるので，1 を出力する．

この入力例は小課題 2 の制約を満たす．

入力例 2
2
2 4

出力例 2
2

この入力例はすべての小課題の制約を満たす．

入力例 3
6
2 7 5 3 3 11

出力例 3
3

この入力例は小課題 2 の制約を満たす．

入力例 4
10
3 1 4 1 5 9 2 6 5 3

出力例 4
0

この入力例は小課題 2 の制約を満たす．

入力例 5
2
0 0

出力例 5
0

この入力例はすべての小課題の制約を満たす．