← 返回题目列表

AtCoder · arc192_a

A. ARC 弧

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

分数: 400 点

问题陈述

给你一个正整数 N 和一个序列 A=(A_1,A_2,\dots,A_N) 长度 N,包括 0 和 1.

我们称一个字符串 S 长度 N,仅由大写英文字母组成,a 好字符串 如果可以执行以下操作任意次数(可能为零),以便序列 A 不包含 0。在这里, S_i (1\leq i\leq N) 表示 i- 第一个字符 S,我们定义 S_{N+1}=S_1, S_{N+2}=S_2,和 A_{N+1}=A_1.

  • 执行以下操作之一:
    • 选择一个整数 i 与 1\leq i\leq N 这样 S_i= A, S_{i+1}= R,和 S_{i+2}= C,并替换每个 A_i 和 A_{i+1} 与 1.
    • 选择一个整数 i 与 1\leq i\leq N 这样 S_{i+2}= A, S_{i+1}= R,和 S_i= C,并替换每个 A_i 和 A_{i+1} 与 1.

判断是否存在好的字符串。

约束

  • 3\leq N\leq 200000
  • A_i\in \lbrace 0,1 \rbrace (1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

如果存在好的字符串,则打印 Yes;否则,打印 No.

法官不区分大小写;例如,如果正确答案是 Yes,输出如 yes, YES,或 yEs 也将被接受。


示例输入 1

12
0 1 0 1 1 1 1 0 1 1 1 0

示例输出 1

Yes

例如, RARCARCCRAGC 是一个很好的字符串。这是因为可以更改的所有元素 A to 1 通过执行以下操作:

  • 最初, A=(0,1,0,1,1,1,1,0,1,1,1,0).
  • 执行第一个操作 i=2。然后, A=(0,1,1,1,1,1,1,0,1,1,1,0).
  • 执行第一个操作 i=5。然后, A=(0,1,1,1,1,1,1,0,1,1,1,0).
  • 执行第二个操作 i=8。然后, A=(0,1,1,1,1,1,1,1,1,1,1,0).
  • 执行第二个操作 i=12。然后, A=(1,1,1,1,1,1,1,1,1,1,1,1).

由于存在好的字符串,因此输出 Yes.


示例输入 2

3
0 0 0

示例输出 2

No

好的字符串不存在。


示例输入 3

29
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

示例输出 3

Yes

自从 A 已不包含 0,每个长度的字符串 29 由大写英文字母组成是一个好的字符串。