A. Row

Codeforces

IDCF982A

Time1000ms

Memory256MB

Difficulty—

brute forceconstructive algorithms

English · Original

Chinese · Translation

Formal · Original

You're given a row with $n$ chairs. We call a seating of people "maximal" if the two following conditions hold: 1. There are no neighbors adjacent to anyone seated. 2. It's impossible to seat one more person without violating the first rule. The seating is given as a string consisting of zeros and ones ($0$ means that the corresponding seat is empty, $1$ — occupied). The goal is to determine whether this seating is "maximal". Note that the first and last seats are **not** adjacent (if $n \ne 2$). ## Input The first line contains a single integer $n$ ($1 \leq n \leq 1000$) — the number of chairs. The next line contains a string of $n$ characters, each of them is either zero or one, describing the seating. ## Output Output "_Yes_" (without quotation marks) if the seating is "maximal". Otherwise print "_No_". You are allowed to print letters in whatever case you'd like (uppercase or lowercase). [samples] ## Note In sample case one the given seating is maximal. In sample case two the person at chair three has a neighbour to the right. In sample case three it is possible to seat yet another person into chair three.

你面前有一排 n 把椅子。我们称一种坐人方式为“最大”的，如果满足以下两个条件：坐人方式由一个由 0 和 1 组成的字符串表示（0 表示对应座位为空，1 表示被占用）。你的目标是判断这种坐人方式是否为“最大”的。注意：第一把和最后一把椅子 *不* 相邻（当 n != 2 时）。第一行包含一个整数 n（1 lt.eq n lt.eq 1000）— 椅子的数量。第二行包含一个长度为 n 的字符串，每个字符为 0 或 1，描述坐人情况。如果坐人方式是“最大”的，请输出 "_Yes_"（不带引号）；否则输出 "_No_"。你可以任意使用大写或小写字母输出。在第一个样例中，给定的坐人方式是最大的。在第二个样例中，第三把椅子上的人右边有一个邻居。在第三个样例中，可以在第三把椅子上再安排一个人。 ## Input 第一行包含一个整数 n（1 lt.eq n lt.eq 1000）— 椅子的数量。第二行包含一个长度为 n 的字符串，每个字符为 0 或 1，描述坐人情况。 ## Output 如果坐人方式是“最大”的，请输出 "_Yes_"（不带引号）；否则输出 "_No_"。你可以任意使用大写或小写字母输出。 [samples] ## Note 在第一个样例中，给定的坐人方式是最大的。在第二个样例中，第三把椅子上的人右边有一个邻居。在第三个样例中，可以在第三把椅子上再安排一个人。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of chairs. Let $ s \in \{0,1\}^n $ be a binary string representing the seating, where $ s_i = 1 $ means chair $ i $ is occupied, and $ s_i = 0 $ means it is empty, for $ i \in \{1, \dots, n\} $. **Constraints** $ 1 \le n \le 1000 $ **Objective** Determine whether $ s $ is *maximal*, i.e., the following two conditions hold: 1. **No two adjacent seats are both occupied**: $$ \forall i \in \{1, \dots, n-1\}, \quad s_i = 1 \implies s_{i+1} = 0 $$ 2. **No empty seat can be occupied without violating condition 1** (i.e., every empty seat has at least one adjacent occupied seat): $$ \forall i \in \{1, \dots, n\}, \quad s_i = 0 \implies \exists j \in \{i-1, i+1\} \cap \{1, \dots, n\} \text{ such that } s_j = 1 $$ Output "Yes" if both conditions hold; otherwise, output "No".

Samples

Input #1

3
101

Output #1

Yes

Input #2

4
1011

Output #2

No

Input #3

5
10001

Output #3

No

API Response (JSON)

{
  "problem": {
    "name": "A. Row",
    "description": {
      "content": "You're given a row with $n$ chairs. We call a seating of people \"maximal\" if the two following conditions hold: 1.  There are no neighbors adjacent to anyone seated. 2.  It's impossible to seat one m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF982A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a row with $n$ chairs. We call a seating of people \"maximal\" if the two following conditions hold:\n\n1.  There are no neighbors adjacent to anyone seated.\n2.  It's impossible to seat one m...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你面前有一排 n 把椅子。我们称一种坐人方式为“最大”的，如果满足以下两个条件：\n\n坐人方式由一个由 0 和 1 组成的字符串表示（0 表示对应座位为空，1 表示被占用）。你的目标是判断这种坐人方式是否为“最大”的。\n\n注意：第一把和最后一把椅子 *不* 相邻（当 n != 2 时）。\n\n第一行包含一个整数 n（1 lt.eq n lt.eq 1000）— 椅子的数量。\n\n第二行包含一个长度为 n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of chairs.  \nLet $ s \\in \\{0,1\\}^n $ be a binary string representing the seating, where $ s_i = 1 $ means chair $ i $ is occupied, and $ s_i = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments