Разбор задачи «Коллекция значков»

Идея задачи

У каждого значка есть три бинарных признака:

• блестящий;
• круглый;
• редкий.

Каждый значок описывается тремя числами 0 или 1.

Три коллекционера забирают только те значки, у которых ровно один признак равен 1:

• только блестящий;
• только круглый;
• только редкий.

Если у значка:

• нет ни одного признака;
• есть сразу два признака;
• есть все три признака,

то такой значок остаётся в музее.

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

Как понять, забирают значок или нет

Для каждого значка нам известны три значения:

• L[i]
• D[i]
• N[i]

Так как каждое из них равно либо 0, либо 1, можно просто посчитать их сумму:

cnt = L[i] + D[i] + N[i]

Тогда:

• если cnt == 1, значок забирают;
• иначе значок остаётся.

Значит, задача сводится к очень простой идее:

1. пройти по всем значкам;
2. посчитать, сколько из них будут забраны;
3. вывести M - taken.

Почему это правильно

Рассмотрим все возможные случаи для одного значка.

Случай 1. Сумма признаков равна 0

Например: 0 0 0.

У значка нет ни одного нужного признака, значит никто его не забирает.

Случай 2. Сумма признаков равна 1

Например:

• 1 0 0
• 0 1 0
• 0 0 1

У значка есть ровно один признак, значит его забирает соответствующий коллекционер.

Случай 3. Сумма признаков равна 2

Например:

• 1 1 0
• 1 0 1
• 0 1 1

У значка сразу два признака. По условию такие значки никто не забирает.

Случай 4. Сумма признаков равна 3

Например: 1 1 1.

У значка есть все три признака. Его тоже никто не забирает.

Получается, единственный случай, когда значок забирают, — это когда сумма трёх чисел равна ровно 1.

Значит, алгоритм корректен.

Пошаговый алгоритм

Пусть дано M значков.

Для каждого значка:

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

После обработки всех значков выводим:

M - taken

Пример

Пусть входные данные такие:

4

1 0 0 1 1 0 0 0 0 0 0 1

Разберём по строкам:

1. 1 0 0 → сумма 1 → значок забирают;
2. 1 1 0 → сумма 2 → значок остаётся;
3. 0 0 0 → сумма 0 → значок остаётся;
4. 0 0 1 → сумма 1 → значок забирают.

Всего забрали 2 значка, значит осталось:

4 - 2 = 2

Ответ: 2.

Эффективность

Мы один раз проходим по всем значкам.

Время работы

На каждый значок тратится константное время, значит общая сложность:

O(M)

Использование памяти

Если обрабатывать значки сразу при чтении, дополнительная память не нужна, кроме нескольких переменных:

O(1)

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

Замечание по реализации

Хотя в исходной функции могут использоваться массивы L, D, N, в стандартном решении удобнее просто читать входные данные построчно и сразу обрабатывать их.

Так код получается:

• короче;
• понятнее;
• экономнее по памяти.

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

#include <iostream>
using namespace std;

int main() {

    int M;
    cin >> M;

    int taken = 0;

    for (int i = 0; i < M; ++i) {
        int l, d, n;
        cin >> l >> d >> n;

        int cnt = l + d + n;
        if (cnt == 1) {
            ++taken;
        }
    }

    cout << M - taken << '\n';
    return 0;
}

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

• taken — количество значков, которые заберут;
• в цикле читаем три числа для очередного значка;
• считаем сумму cnt;
• если cnt == 1, увеличиваем taken;
• в конце выводим число оставшихся значков.

Решение на Python

def main():
    m = int(input())
    taken = 0

    for _ in range(m):
        l, d, n = map(int, input().split())
        cnt = l + d + n
        if cnt == 1:
            taken += 1

    print(m - taken)


if __name__ == "__main__":
    main()

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

Логика полностью такая же, как и в решении на C++:

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

Частые ошибки

1. Проверять только конкретные варианты

Некоторые пытаются отдельно проверять:

• 1 0 0
• 0 1 0
• 0 0 1

Это работает, но запись через сумму проще и надёжнее:

l + d + n == 1

2. Хранить все данные без необходимости

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

3. Перепутать, что нужно вывести

Нужно вывести количество оставшихся значков, а не количество забранных.

То есть ответ — это:

M - taken