Задание EGEINF41E442: Сортировка, отбор и моделирование

Решение.
В исходном файле 9992 строк товаров. Каждая строка соответствует одной единице, поэтому среднюю цену считаем по всем строкам, включая уже проданные товары. Среднее по различным артикулам было бы другой величиной.
Сумма цен всех единиц S = 5576611, количество N = 9992. Средняя цена равна SN = 55766119992. Товар дорогой тогда и только тогда, когда его цена p строго больше этого значения. Чтобы обойтись точными целыми числами, проверяем p · N > S.
Для каждого артикула накапливаем цену, число проданных единиц и остаток. Статус 0 увеличивает число проданных, статус 1 — остаток. Цена всех единиц одного артикула одинакова по условию.
Среди дорогих артикулов сначала выбираем максимальное число продаж. При равенстве сравниваем цены и выбираем большую. Только при равенстве обоих показателей сравниваем остатки и выбираем меньший. Эти три условия удобно объединить в ключ (продано, цена, −остаток), сравниваемый слева направо.
В файле 215 различных артикулов, из них 103 дорогих. Три первых кандидата после применения правил:

У всех трёх продано 51 единица. Артикул 37134 выбывает из-за цены 831, которая меньше 856. Его нулевой остаток не запрещает участие: такого ограничения в условии нет. У двух остальных цена одинакова, поэтому сравниваем остатки 36 и 37 и выбираем артикул 46481.
Сохраните скачанный файл рядом с программой под исходным именем. Программа на Python:

with open("img1_1777467535.txt") as f:
    n = int(f.readline())
    rows = [tuple(map(int, line.split())) for line in f]
total = sum(price for article, price, status in rows)
goods = {}
for article, price, status in rows:
    if article not in goods:
        goods[article] = [price, 0, 0]
    if status == 0:
        goods[article][1] += 1
    else:
        goods[article][2] += 1
candidates = [v for v in goods.values() if v[0] * n > total]
price, sold, left = max(candidates, key=lambda v: (v[1], v[0], -v[2]))
print(price * sold, left)

Выручка от выбранного артикула равна цене одной единицы, умноженной на число проданных: 856 · 51 = 43656. Остаток равен 36.
Проверка: в первичных строках артикула 46481 найдено 87 единиц, из них 51 со статусом 0 и 36 со статусом 1; 51 + 36 = 87. Цена 856 удовлетворяет точному условию 856 · 9992 > 5576611. Независимая группировка строк и последовательное применение трёх критериев дали тот же единственный артикул.
Каждая строка обрабатывается постоянное число раз. Время O(N), память для строк и словаря O(N).
Ответ: 43656 36.