Что спрашивают

Каждая строка описывает одну единицу: артикул, цену и статус 0 — продана, 1 — осталась. Цена внутри артикула одинакова. Дорогим считается артикул с ценой строго выше среднего по всем единицам базы, включая непроданные.

Лидер дорогих выбирается по числу проданных, затем большей цене, затем меньшему остатку. Выведите выручку лидера и его остаток. N ≤ 10 000, цена ≤ 10 000, дорогие товары есть.

Приём решения

За один проход накопим сумму всех цен total и для каждого артикула сохраним цену, число проданных sold и оставшихся remaining. Среднее считается по N строкам, а не по числу различных артикулов.

Цена дорогая, если price * N > total. Умножение целых точно эквивалентно строгому сравнению со средним и не требует float. Далее среди дорогих сравним тройки (sold, price, -remaining) и выберем максимум.

Так сначала побеждает число продаж, потом цена и только затем меньший остаток. Нельзя сравнивать выручку раньше числа продаж: один дорогой проданный товар может дать больше денег, но всё равно проиграть по первому критерию.

После выбора вычислим sold * price и вернём remaining. Если несколько артикулов совпали по всем трём критериям, оба выходных числа у них одинаковы. Время O(N), память O(U), где U — число артикулов.

Разбор на примере

Ввод

11
2 40 1
1 10 0
3 40 0
2 40 0
4 100 0
1 10 0
2 40 1
3 40 0
1 10 0
2 40 0
1 10 0

Вывод

80 0
Разбор примера по шагам
АртикулПродано / цена / осталосьРешение
14 / 10 / 010 × 11 ≤ 380: не дорогой
22 / 40 / 2Кандидат
32 / 40 / 0Лучше по остатку
41 / 100 / 0Меньше продаж

Сумма цен 380, единиц 11, среднее примерно 34,55. Артикул 1 дешёвый и исключается. У артикулов 2 и 3 по две продажи и цена 40, но у 3 нет остатка, поэтому он побеждает. Артикул 4 дал выручку 100, однако продан только один раз. Ответ лидера: 2 × 40 = 80, остаток 0.

Код на Python и C++

По условию дорогие артикулы есть, даже если их продажи нулевые. Такие кандидаты участвуют в сравнении; выручка лидера тогда может быть нулём.

В C++ группы лежат в map<long long, array<long long, 3>>, а кандидаты сравниваются как tuple, в том же порядке, что кортежи в Python.

import sys


def solve(rows):
    groups = {}
    total = 0
    for article, price, status in rows:
        total += price
        group = groups.setdefault(article, [price, 0, 0])
        if status == 0:
            group[1] += 1
        else:
            group[2] += 1
    candidates = []
    for price, sold, remaining in groups.values():
        if price * len(rows) > total:
            candidates.append((sold, price, -remaining))
    sold, price, negative_remaining = max(candidates)
    return sold * price, -negative_remaining


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    rows = list(zip(data[1::3], data[2::3], data[3::3]))
    print(*solve(rows))
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <tuple>
using namespace std;

int main() {
    int n;
    cin >> n;
    // groups[артикул] = {цена, продано, осталось}.
    map<long long, array<long long, 3>> groups;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        long long article, price, status;
        cin >> article >> price >> status;
        total += price;
        if (!groups.count(article))
            groups[article] = {price, 0, 0};
        if (status == 0)
            groups[article][1] += 1;
        else
            groups[article][2] += 1;
    }
    tuple<long long, long long, long long> best = {-1, -1, 0};
    for (auto& [article, group] : groups) {
        auto [price, sold, remaining] = group;
        if (price * n > total)
            best = max(best, {sold, price, -remaining});
    }
    auto [sold, price, negative_remaining] = best;
    cout << sold * price << ' ' << -negative_remaining << endl;
}

Типичные ошибки

  • Перепутать значения статуса

    Статус 0 обозначает проданный товар, 1 — оставшийся. Иначе одновременно изменятся продажи и остаток.

  • Взять среднее по артикулам

    Каждая единица имеет свой вес в среднем. Артикул из ста единиц учитывается сто раз.

  • Выбрать максимальную выручку

    Первый критерий — число проданных единиц. Выручка вычисляется только после выбора лидера.

  • Включить цену на уровне среднего

    Дорогая цена должна строго превышать среднее. Равенство price × N и total не подходит.