Question

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

На вход подаётся количество запросов N, затем N строк с номерами задач (от 1 до 12).

Программа должна вывести информацию о каждой задаче, которая встретилась хотя бы один раз: номер задачи и количество запросов. Строки упорядочиваются по убыванию количества запросов; при равенстве — по возрастанию номеров задач.

**Пример входных данных:**
```
6
1
2
1
1
5
2
```

**Пример выходных данных:**
```
1 3
2 2
5 1
```

Accepted Answer

Программа подсчитывает частоту каждой задачи и выводит их в порядке убывания частоты, при равенстве — по возрастанию номера

Answer

Идея решения: подсчитать частоту каждого номера задачи в массиве размером 12, затем отсортировать пары (номер, частота) по убыванию частоты и возрастанию номера, вывести только те задачи, которые встретились. **Алгоритм:** 1. Инициализируем два массива: `Count` для подсчёта запросов по каждой задаче и `Names` для хранения номеров задач (1–12). 2. Читаем N запросов и увеличиваем счётчик для соответствующей задачи. 3. Сортируем оба массива одновременно: по убыванию `Count`, при равенстве — по возрастанию `Names` (сортировка пузырьком). 4. Выводим только те задачи, у которых `Count[i] > 0`. **Решение на Python:** ```python n = int(input()) count = [0] * 13 # индексы 1-12 names = list(range(13)) # names[i] = i for _ in range(n): task = int(input()) count[task] += 1 # Сортируем по убыванию count, при равенстве по возрастанию names for i in range(12, 1, -1): for j in range(2, i + 1): if count[j - 1] < count[j] or \ (count[j - 1] == count[j] and names[j - 1] > names[j]): count[j - 1], count[j] = count[j], count[j - 1] names[j - 1], names[j] = names[j], names[j - 1] for i in range(1, 13): if count[i] > 0: print(names[i], count[i]) ``` **Решение на Паскале:** ```pascal Var n, num, i, j, t: integer; count: array[1..12] of integer; names: array[1..12] of integer; Begin For i := 1 to 12 do begin count[i] := 0; names[i] := i; end; ReadLn(n); for i := 1 to n do begin ReadLn(t); count[t] := count[t] + 1; end; for i := 12 downto 2 do for j := 2 to i do if count[j - 1] < count[j] then begin t := count[j]; count[j] := count[j - 1]; count[j - 1] := t; t := names[j]; names[j] := names[j - 1]; names[j - 1] := t; end; for i := 1 to 12 do if count[i] > 0 then WriteLn(names[i], ' ', count[i]); End. ``` Входные данные: 6 запросов — 1, 2, 1, 1, 5, 2. После подсчёта: задача 1 → 3 раза, задача 2 → 2 раза, задача 5 → 1 раз. После сортировки: (1, 3), (2, 2), (5, 1). Вывод: ``` 1 3 2 2 5 1 ``` Сложность: $O(1)$ для подсчёта (N итераций по 12 задачам), $O(144)$ для сортировки (константа, так как максимум 12 элементов). Итого $O(N)$.

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