ВсОШ: школьный этап · словарь для подсчёта

D. Самое частое число

Задача в стиле школьного этапа ВсОШ по информатике — составлена для Grape, это не задание с олимпиады. Официальные задания и разборы — на siriusolymp.ru.

Как проверяет автоматическая система

  • Ответ — сама программа. Система запускает её на многих тестах: часть видна в условии, остальные скрыты.
  • На каждом тесте программа должна напечатать ровно ответ — без слов вроде «Ответ:».
  • Есть ограничение по времени: слишком медленная или зависшая программа тест не проходит.
  • Здесь так же: кнопка проверяет на всех тестах и останавливается на первой ошибке.

Условие

словарь для подсчёта

Дано N чисел. Найди число, которое встречается чаще всех. Если таких несколько — выведи самое маленькое из них.

Входные данные. В первой строке — N (1 ≤ N ≤ 105). Во второй — N целых чисел через пробел, от 1 до 109.

Выходные данные. Одно число — ответ.

Входные данныеВыходные данные
5 1 3 3 2 11
1 77
3 5 5 55
Твоя программа на Python
Разбор

Идея. Считаем, сколько раз встретилось каждое число, в словаре count. Числа до миллиарда, поэтому список на миллиард ячеек не подойдёт, а в словаре хранятся только встретившиеся числа.

Потом выбираем лучшее: встречается чаще — лучше; встречается так же часто, но само меньше — тоже лучше.

Решение на Python — комментарий после # объясняет строку, Python его не выполняет.

n = int(input())  # сколько чисел
a = list(map(int, input().split()))  # сами числа
count = {}  # словарь: число → сколько раз встретилось
for x in a:  # идём по числам
    count[x] = count.get(x, 0) + 1  # get(x, 0) — сколько было, или 0, если ещё не встречалось
best = None  # лучший ответ, пока не нашли
for x in count:  # перебираем разные числа
    if best is None or count[x] > count[best] or (count[x] == count[best] and x < best):  # чаще или так же, но меньше
        best = x  # новый лучший ответ
print(best)  # печатаем ответ

Что используется в решении.

  • input() читает одну строку ввода, int() превращает её в целое число.
  • if условие: — ветвление: строки с отступом под ним выполняются, только если условие верно.
  • and — «и»: условие верно, только если верны обе части.
  • > — «больше».
  • print() — выводит ответ. Печатаем только ответ, без лишних слов.