Турнирная таблица

1. Идея

Нужно смоделировать уже сыгранные матчи и для каждой команды накопить статистику:

• сколько матчей сыграно;
• сколько побед, ничьих и поражений;
• сколько забито и пропущено;
• сколько набрано очков.

После этого останется только отсортировать команды по правилам из условия:

1. больше очков;
2. больше разница мячей забито - пропущено;
3. больше забитых мячей;
4. лексикографически меньшее название.

Задача полностью решается прямой реализацией.

2. Наблюдения

Наблюдение 1. Один матч влияет сразу на две команды

Если известен результат team1 team2 g1 g2, то:

• обе команды увеличивают число сыгранных матчей на 1;
• team1 забила g1 и пропустила g2;
• team2 забила g2 и пропустила g1.

Дальше отдельно обновляется результат:

• если g1 > g2, то у team1 победа и 3 очка, у team2 поражение;
• если g1 < g2, то наоборот;
• если g1 == g2, то у обеих команд ничья и по 1 очку.

Наблюдение 2. Нужен быстрый доступ к команде по названию

Во входных данных матчи задаются названиями команд. Значит, удобно хранить отображение:

• название -> номер команды

Тогда по каждой строке матча можно быстро найти нужные записи статистики.

Наблюдение 3. Все критерии сортировки известны заранее

После подсчёта статистики достаточно один раз отсортировать все команды по составному ключу:

• по убыванию очков;
• по убыванию разницы мячей;
• по убыванию забитых;
• по возрастанию названия.

3. Алгоритм

1. Считать n и m.
2. Считать названия всех команд.
3. Для каждой команды создать пустую статистику:
   • played, wins, draws, losses, goals_for, goals_against, points.
4. Построить словарь или хеш-таблицу name -> index, чтобы быстро находить команду.
5. Для каждого из m матчей:
   • считать team1, team2, g1, g2;
   • найти статистику обеих команд;
   • обновить число сыгранных матчей;
   • обновить забитые и пропущенные мячи;
   • по сравнению g1 и g2 обновить победы, ничьи, поражения и очки.
6. Отсортировать команды по правилам из условия.
7. Вывести для каждой команды: название сыграно побед ничьих поражений забито пропущено очки

4. Почему это работает

Докажем, что алгоритм строит правильную турнирную таблицу.

Рассмотрим любой матч team1 team2 g1 g2.

• Команда team1 действительно сыграла один матч, забила g1 и пропустила g2.
• Команда team2 действительно сыграла один матч, забила g2 и пропустила g1.

Это точно соответствует определению статистики.

Дальше есть три возможных исхода:

Случай 1. g1 > g2

Тогда team1 выиграла матч, значит:

• побед у team1 становится на 1 больше;
• очков у team1 становится на 3 больше;
• поражений у team2 становится на 1 больше.

Это полностью совпадает с правилами начисления очков.

Случай 2. g1 < g2

Аналогично:

• team2 получает победу и 3 очка;
• team1 получает поражение.

Случай 3. g1 == g2

Тогда обе команды сыграли вничью:

• у обеих увеличивается число ничьих;
• обе получают по 1 очку.

Опять всё совпадает с условием.

Так как каждый матч обрабатывается ровно один раз и его вклад в статистику обеих команд учитывается правильно, после обработки всех m матчей статистика каждой команды будет точной.

Теперь про сортировку. В условии задан строгий порядок сравнения команд:

1. очки;
2. разница мячей;
3. забитые мячи;
4. название.

Алгоритм сортирует команды ровно по этим критериям и ровно в этом порядке. Значит, итоговый порядок команд в выводе совпадает с требуемой турнирной таблицей.

Следовательно, алгоритм корректен.

5. Сложность

Пусть:

• n — число команд;
• m — число сыгранных матчей.

Тогда:

• обработка всех матчей занимает O(m);
• сортировка команд занимает O(n log n).

Итоговая сложность: O(m + n log n).

Память:

• хранение статистики команд и отображения названий — O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Team {
    string name;
    long long played = 0;
    long long wins = 0;
    long long draws = 0;
    long long losses = 0;
    long long goals_for = 0;
    long long goals_against = 0;
    long long points = 0;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Team> teams(n);
    unordered_map<string, int> id;

    for (int i = 0; i < n; i++) {
        cin >> teams[i].name;
        id[teams[i].name] = i;
    }

    for (int i = 0; i < m; i++) {
        string team1, team2;
        long long g1, g2;
        cin >> team1 >> team2 >> g1 >> g2;

        int a = id[team1];
        int b = id[team2];

        teams[a].played++;
        teams[b].played++;

        teams[a].goals_for += g1;
        teams[a].goals_against += g2;

        teams[b].goals_for += g2;
        teams[b].goals_against += g1;

        if (g1 > g2) {
            teams[a].wins++;
            teams[a].points += 3;
            teams[b].losses++;
        } else if (g1 < g2) {
            teams[b].wins++;
            teams[b].points += 3;
            teams[a].losses++;
        } else {
            teams[a].draws++;
            teams[b].draws++;
            teams[a].points++;
            teams[b].points++;
        }
    }

    sort(teams.begin(), teams.end(), [](const Team& a, const Team& b) {
        if (a.points != b.points) return a.points > b.points;
        long long diff_a = a.goals_for - a.goals_against;
        long long diff_b = b.goals_for - b.goals_against;
        if (diff_a != diff_b) return diff_a > diff_b;
        if (a.goals_for != b.goals_for) return a.goals_for > b.goals_for;
        return a.name < b.name;
    });

    for (const Team& t : teams) {
        cout << t.name << ' '
             << t.played << ' '
             << t.wins << ' '
             << t.draws << ' '
             << t.losses << ' '
             << t.goals_for << ' '
             << t.goals_against << ' '
             << t.points << '\n';
    }

    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

teams = []
stats = {}
index = {}

for i in range(n):
    name = input().strip()
    teams.append(name)
    index[name] = i
    stats[name] = [0, 0, 0, 0, 0, 0, 0]
    # played, wins, draws, losses, goals_for, goals_against, points

for _ in range(m):
    team1, team2, g1, g2 = input().split()
    g1 = int(g1)
    g2 = int(g2)

    s1 = stats[team1]
    s2 = stats[team2]

    s1[0] += 1
    s2[0] += 1

    s1[4] += g1
    s1[5] += g2

    s2[4] += g2
    s2[5] += g1

    if g1 > g2:
        s1[1] += 1
        s1[6] += 3
        s2[3] += 1
    elif g1 < g2:
        s2[1] += 1
        s2[6] += 3
        s1[3] += 1
    else:
        s1[2] += 1
        s2[2] += 1
        s1[6] += 1
        s2[6] += 1

teams.sort(key=lambda name: (
    -stats[name][6],
    -(stats[name][4] - stats[name][5]),
    -stats[name][4],
    name
))

for name in teams:
    s = stats[name]
    print(name, s[0], s[1], s[2], s[3], s[4], s[5], s[6])