Разбор задачи «Сеть музеев и хранилищ артефактов»

Идея задачи

В сети есть два типа объектов:

• музеи, обозначенные числом 0;
• хранилища артефактов, обозначенные числом 1.

Объекты вводятся в работу по одному, в заданном порядке. Нужно определить, после запуска какого минимального количества первых объектов уже окажется, что все объекты хотя бы одного типа введены в работу.

Иначе говоря, нам нужно найти самый ранний момент, когда:

• либо уже открыты все музеи;
• либо уже открыты все хранилища.

Как посмотреть на задачу проще

Если бы мы знали:

• сколько всего музеев в сети;
• сколько всего хранилищ в сети,

то дальше можно было бы идти слева направо по последовательности запусков и отслеживать, сколько объектов каждого типа ещё не открыто.

Например:

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

Как только число неоткрытых музеев стало равно нулю, это означает, что открыты все музеи.

Как только число неоткрытых хранилищ стало равно нулю, это означает, что открыты все хранилища.

Первый такой момент и будет ответом.

Пошаговый пример

Рассмотрим последовательность:

0 0 1 1 0

Сначала посчитаем общее количество объектов каждого типа:

• музеев (0) — 3;
• хранилищ (1) — 2.

Теперь идём по порядку:

1. Открыли 0:
   • осталось неоткрытых музеев: 2;
   • осталось неоткрытых хранилищ: 2.
2. Открыли 0:
   • осталось неоткрытых музеев: 1;
   • осталось неоткрытых хранилищ: 2.
3. Открыли 1:
   • осталось неоткрытых музеев: 1;
   • осталось неоткрытых хранилищ: 1.
4. Открыли 1:
   • осталось неоткрытых музеев: 1;
   • осталось неоткрытых хранилищ: 0.

На четвёртом шаге все хранилища уже открыты. Значит, ответ равен 4.

Алгоритм

1. Считываем n и последовательность a.
2. Подсчитываем:
   • cnt0 — сколько всего нулей в массиве;
   • cnt1 — сколько всего единиц в массиве.
3. Проходим по массиву слева направо.
4. Для текущего элемента:
   • если это 0, уменьшаем cnt0;
   • если это 1, уменьшаем cnt1.
5. После каждого шага проверяем:
   • если cnt0 == 0, то все музеи уже открыты;
   • если cnt1 == 0, то все хранилища уже открыты.
6. Как только одно из этих условий выполнилось, выводим номер шага.

Почему алгоритм работает

Докажем корректность.

Пусть после обработки первых k элементов:

• cnt0 — количество музеев, которые ещё не открыты;
• cnt1 — количество хранилищ, которые ещё не открыты.

Это правда, потому что:

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

Тогда:

• условие cnt0 == 0 означает, что не осталось ни одного неоткрытого музея, то есть открыты все музеи;
• условие cnt1 == 0 означает, что открыты все хранилища.

Задача просит найти минимальный номер шага, когда выполнено хотя бы одно из этих условий. Мы проверяем их после каждого шага по порядку, поэтому первый найденный момент и будет минимальным.

Следовательно, алгоритм работает правильно.

Оценка сложности

Мы:

• один раз считаем количество нулей и единиц;
• один раз проходим по массиву.

Итоговая сложность:

• по времени: O(n);
• по памяти: O(n), если хранить массив целиком.

Это эффективно и легко укладывается в ограничения задачи.

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    int cnt0 = 0, cnt1 = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] == 0) {
            ++cnt0;
        } else {
            ++cnt1;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            --cnt0;
        } else {
            --cnt1;
        }

        if (cnt0 == 0 || cnt1 == 0) {
            cout << i + 1 << '\n';
            return 0;
        }
    }

    return 0;
}

Пояснение к коду на C++

• Сначала считываем весь массив и одновременно считаем, сколько в нём нулей и единиц.
• Потом ещё раз идём по массиву.
• Для каждого элемента уменьшаем соответствующий счётчик.
• Если один из счётчиков стал равен нулю, сразу выводим ответ.

Обратите внимание, что выводится i + 1, потому что шаги нумеруются с единицы, а индексы массива — с нуля.

Решение на Python

n = int(input())
a = list(map(int, input().split()))

cnt0 = a.count(0)
cnt1 = a.count(1)

for i in range(n):
    if a[i] == 0:
        cnt0 -= 1
    else:
        cnt1 -= 1

    if cnt0 == 0 or cnt1 == 0:
        print(i + 1)
        break

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

Здесь используется тот же самый подход:

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

На что обратить внимание

1. Не нужно моделировать открытые объекты отдельно

Некоторые пытаются хранить, какие объекты уже открылись, в дополнительных массивах или множествах. Здесь это не требуется. Нам важно только одно: сколько объектов каждого типа ещё не открыто.

2. Ответ ищется по первому подходящему моменту

Мы не ищем максимум, минимум по всем вариантам или что-то сложное. Нужно просто идти слева направо и остановиться в первый момент, когда один из типов полностью открыт.

3. В задаче всегда есть оба типа объектов

По условию гарантируется, что среди объектов есть хотя бы один 0 и хотя бы один 1. Значит, ответ точно существует.

Главная мысль задачи очень простая:

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

Это хорошая задача на внимательное чтение условия и аккуратную реализацию простой идеи.