Question

В командных олимпиадах по программированию предлагается не более 12 задач. Команда отправляет решения в проверяющую систему в произвольном порядке. Требуется обработать поток запросов и определить три наименее популярные задачи.

На вход подаётся количество запросов N. В каждой из следующих N строк — название задачи (до 100 символов, может содержать буквы, цифры, пробелы и знаки препинания).

Вывести список из трёх задач с наименьшей частотой встречаемости, указав количество запросов по каждой. Если задач менее трёх, вывести все. Если несколько задач имеют одинаковую частоту с третьей по популярности, вывести только одну из них.

**Пример входных данных:**
```
6
А+B
Крестики-Нолики
А+В
Простой делитель
А+В
Простой делитель
```

**Пример выходных данных:**
```
Крестики-Нолики 1
Простой делитель 2
А+В 3
```

Accepted Answer

Крестики-Нолики 1, Простой делитель 2, А+В 3

Answer

Идея решения: прочитать все запросы один раз, подсчитав частоту каждой уникальной задачи в словаре (без сохранения всех N строк в памяти), затем отсортировать по возрастанию частоты и вывести первые три.

**Алгоритм:**

1. Используем словарь для хранения пар (название задачи, количество запросов). Размер словаря не превышает 12.
2. При чтении каждой задачи проверяем, есть ли она в словаре. Если да — увеличиваем счётчик, если нет — добавляем с счётчиком 1.
3. После ввода всех данных сортируем задачи по возрастанию частоты.
4. Выводим первые три задачи (или все, если их меньше трёх).

**Реализация на Python:**

```python
n = int(input())
freq = {}

for _ in range(n):
    task = input()
    if task in freq:
        freq[task] += 1
    else:
        freq[task] = 1

# Сортируем по частоте (возрастание)
sorted_tasks = sorted(freq.items(), key=lambda x: x[1])

# Выводим первые три (или все, если меньше)
count = min(3, len(sorted_tasks))
for i in range(count):
    print(sorted_tasks[i][0], sorted_tasks[i][1])
```

| Задача | Частота |
|---|---|
| Крестики-Нолики | 1 |
| Простой делитель | 2 |
| А+В | 3 |

После сортировки по возрастанию частоты выводим три первые строки.

**Сложность:** $O(n + k \log k)$, где $n$ — количество запросов, $k \le 12$ — число уникальных задач. Память: $O(k)$.

Задание №19Алгоритмы и исполнителиЕГЭ по информатике