Разбор задачи «Часовщики в мастерской»

Идея задачи

У нас есть ряд из n мест, каждое место либо занято (1), либо свободно (0).

Рассадка считается окончательной, если одновременно выполнены два условия:

1. никакие два часовщика не сидят на соседних местах;
2. нельзя посадить ещё одного часовщика ни на одно свободное место так, чтобы первое условие осталось выполненным.

Нужно определить, является ли данная рассадка окончательной.

Что именно надо проверить

Многие сразу думают только о первом условии: проверить, что в строке нет двух соседних единиц. Но этого недостаточно.

Например, строка 1001 не содержит соседних 1, однако ответ для неё всё равно No, потому что в середине можно посадить ещё одного часовщика.

Значит, нужно проверить сразу две вещи:

• в текущей строке нет соседних 1;
• не существует такой позиции с 0, куда можно поставить 1, не нарушив правило.

Наблюдение

Для каждой позиции важны только её соседи.

Пусть мы рассматриваем место i.

• если s[i] = '1', то слева и справа не должно быть 1;
• если s[i] = '0', то если слева нет 1 и справа нет 1, то сюда можно посадить ещё одного часовщика, а значит текущая рассадка не окончательная.

Получается, достаточно один раз пройти по строке и для каждой позиции посмотреть на соседей.

Разберём два типа позиций

1. Текущая позиция занята

Если s[i] = '1', то:

• если i > 0 и s[i - 1] = '1', это нарушение;
• если i + 1 < n и s[i + 1] = '1', это тоже нарушение.

В таком случае сразу выводим No.

2. Текущая позиция свободна

Если s[i] = '0', то проверяем, можно ли сюда посадить человека.

Это возможно тогда и только тогда, когда:

• слева нет 1;
• справа нет 1.

Если это так, значит рассадка не максимальна, и ответ тоже No.

Если ни на одной позиции не найдено нарушения, то ответ Yes.

Почему этого достаточно

Мы буквально проверяем определение из условия.

Корректность

Если программа вывела No, то произошло одно из двух:

• либо нашлась занятая позиция рядом с другой занятой позицией, то есть уже нарушено основное правило;
• либо нашлась свободная позиция, у которой оба соседа не заняты, а значит туда можно безопасно посадить ещё одного часовщика.

В обоих случаях рассадка не является окончательной.

Полнота

Если программа вывела Yes, то:

• нигде нет двух соседних 1;
• ни в одну позицию с 0 нельзя поставить 1 без нарушения правила.

Значит, оба условия окончательной рассадки выполнены, следовательно, ответ действительно правильный.

Примеры

Пример 1

101

• соседних 1 нет;
• свободное место посередине уже нельзя занять, потому что по обе стороны стоят часовщики.

Ответ: Yes.

Пример 2

0

• нарушений пока нет;
• но единственное место свободно, и туда можно посадить часовщика.

Ответ: No.

Пример 3

1001

• соседних 1 нет;
• одна из средних позиций подходит для нового часовщика.

Ответ: No.

Пример 4

11

• уже есть два соседних часовщика.

Ответ: No.

Крайние случаи

Один символ

• 1 -> ответ Yes, потому что всё уже хорошо и добавить никого нельзя;
• 0 -> ответ No, потому что можно посадить одного часовщика.

Начало и конец строки

У крайних позиций только один сосед, поэтому их надо проверять аккуратно.

Например:

• в строке 10 ответ Yes;
• в строке 01 ответ Yes;
• в строке 00 ответ No, потому что можно посадить часовщика хотя бы на одно из мест.

Алгоритм

1. Считываем n и строку s.
2. Для каждой позиции i:
   • определяем, есть ли 1 слева;
   • определяем, есть ли 1 справа;
   • если s[i] = '1' и хотя бы один сосед равен 1, выводим No;
   • если s[i] = '0' и ни один сосед не равен 1, выводим No.
3. Если цикл завершился без ошибок, выводим Yes.

Сложность

Мы один раз проходим по строке длины n.

• Время: O(n)
• Память: O(1), если не считать хранения самой строки

Решение на C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    for (int i = 0; i < n; ++i) {
        bool leftOne = (i > 0 && s[i - 1] == '1');
        bool rightOne = (i + 1 < n && s[i + 1] == '1');

        if (s[i] == '1') {
            if (leftOne || rightOne) {
                cout << "No\n";
                return 0;
            }
        } else {
            if (!leftOne && !rightOne) {
                cout << "No\n";
                return 0;
            }
        }
    }

    cout << "Yes\n";
    return 0;
}

Пояснение к коду

Для каждой позиции мы заранее вычисляем:

• leftOne — стоит ли 1 слева;
• rightOne — стоит ли 1 справа.

Дальше:

• если текущий символ 1, то наличие хотя бы одной соседней 1 делает ответ No;
• если текущий символ 0, то отсутствие соседних 1 с обеих сторон означает, что можно посадить ещё одного часовщика, и ответ тоже No.

Если после полного прохода нарушений не найдено, печатаем Yes.

Решение на Python

n = int(input())
s = input().strip()

for i in range(n):
    left_one = i > 0 and s[i - 1] == '1'
    right_one = i + 1 < n and s[i + 1] == '1'

    if s[i] == '1':
        if left_one or right_one:
            print("No")
            break
    else:
        if not left_one and not right_one:
            print("No")
            break
else:
    print("Yes")

Пояснение к коду

Здесь используется конструкция for ... else.

• Если внутри цикла найдено нарушение, программа печатает No и выполняет break.
• Если цикл завершился полностью, значит нарушений нет, и тогда выполняется блок else, в котором печатается Yes.

Это удобно и делает код компактным.

Типичные ошибки

Ошибка 1. Проверять только отсутствие соседних единиц

Такое решение неверно.

Например, для строки 1001 оно скажет Yes, хотя правильный ответ No, потому что можно посадить ещё одного часовщика.

Ошибка 2. Неправильно обрабатывать края строки

У первой позиции нет левого соседа, а у последней нет правого. Если забыть это учесть, можно получить выход за границы массива или неверную проверку.

Ошибка 3. Считать, что любой 0 делает ответ No

Это тоже неверно. Не каждый ноль позволяет посадить нового часовщика.

Например, в строке 101 средний 0 уже зажат двумя единицами, и использовать его нельзя.

Вывод

Это задача на аккуратную проверку условий.

Главная идея очень простая: у каждой позиции нужно посмотреть только на соседей. После этого легко понять:

• есть ли уже нарушение правила;
• можно ли улучшить текущую рассадку.

Именно поэтому задача решается за один проход по строке.