← 返回题目列表

AtCoder · agc043_b

B. 123 三角形

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给定的是一系列 N 数字 a_1a_2\ldots a_N,其中每个元素是 1, 2,或 3。 让 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 \leq N \leq 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