/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
各要素が 1 か 2 か 3 である長さ N の数字列 a_1a_2\ldots a_N が与えられます。 x_{i,j} を次のように定義します。
- x_{1,j} := a_j \quad (1 \leq j \leq N)
- x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N かつ 1 \leq j \leq N+1-i)
x_{N,1} を求めてください。
制約
- 2 ≦ N ≦ 10^6
- a_i = 1,2,3 (1 \leq i \leq N)
入力
入力は以下の形式で標準入力から与えられる。
N a_1a_2\ldotsa_N
出力
x_{N,1} を出力せよ。
入力例 1
4 1231
出力例 1
1
x_{1,1},x_{1,2},x_{1,3},x_{1,4} はそれぞれ、1,2,3,1 です。
x_{2,1},x_{2,2},x_{2,3} はそれぞれ、|1-2| = 1,|2-3| = 1,|3-1| = 2 です。
x_{3,1},x_{3,2} はそれぞれ、|1-1| = 0,|1-2| = 1 です。
最後に、 x_{4,1} = |0-1| = 1 なので、答えは 1 です。
入力例 2
10 2311312312
出力例 2
0
Score : 700 points
Problem Statement
Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3. Let x_{i,j} defined as follows:
- x_{1,j} := a_j \quad (1 \leq j \leq N)
- x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)
Find x_{N,1}.
Constraints
- 2 \leq N \leq 10^6
- a_i = 1,2,3 (1 \leq i \leq N)
Input
Input is given from Standard Input in the following format:
N a_1a_2\ldotsa_N
Output
Print x_{N,1}.
Sample Input 1
4 1231
Sample Output 1
1
x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.
x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.
x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.
Finally, x_{4,1} = |0-1| = 1, so the answer is 1.
Sample Input 2
10 2311312312
Sample Output 2
0