問題一覧 > 通常問題

No.1717 Levi-Civita Triangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : zkouzkou / テスター : nok0nok0 Kite_kumaKite_kuma 👑 ygussanyygussany
17 ProblemId : 6619 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-10 01:02:59

問題文

$0$, $1$, $2$ から成る長さ $2N + 1$ の数列 $(A_1, A_2, \ldots, A_{2N+1})$ が与えられます。 この数列に対し以下の操作を $N$ 回適用します。

  • 元の数列を、長さが $2$ だけ短い新しい数列で置き換える。 古い数列と新しい数列の $i$ 番目の要素をそれぞれ $P_i$, $Q_i$ とする。 このとき、$Q_i$ を下記のルールで決定する。
$$ Q_i = \begin{cases} 1 & ((P_i, P_{i+1}, P_{i+2}) \in \{(0, 1, 2), (1, 2, 0), (2, 0, 1)\}) \\ 2 & ((P_i, P_{i+1}, P_{i+2}) \in \{(2, 1, 0), (1, 0, 2), (0, 2, 1)\}) \\ 0 & (\mathrm{otherwise}) \end{cases} $$ 最終的な数列は、$1$ つの要素から成る数列となります。その要素を出力してください。

制約

  • 入力は全て整数である
  • $1 \le N \le 10^5$
  • $0 \le A_i \le 2$ $(1 \le i \le 2N + 1)$

入力

入力は以下の形式で標準入力から与えられます。 
$N$
$A_1$ $A_2$ $\cdots$ $A_{2N+1}$

出力

最終的な数列は、$1$ つの要素から成る数列となります。その要素を出力してください。

サンプル

サンプル1
入力
1
0 1 2
出力
1

サンプル2
入力
2
1 2 0 2 1
出力
2

サンプル3
入力
3
0 1 2 2 0 1 0
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。