1. Идея

Нужно просто преобразовать описание каждого матча из формата a b w в формат winner loser.

Если известны два участника a и b, а также победитель w, то проигравший определяется однозначно:

• если w == a, то проиграл b;
• иначе проиграл a.

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

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

1. Проверять корректность турнирной сетки не требуется.
   По условию гарантируется, что входные данные уже правильные.

2. Для каждого матча вся нужная информация уже есть во входе:

   • два участника;
   • победитель.

   Значит, проигравшего можно найти сразу, без дополнительного моделирования турнира.

3. Матчи нужно выводить в том же порядке, что и во входе.
   Поэтому удобно просто сохранить для каждого раунда список пар (winner, loser).

4. Чемпион турнира — это победитель последнего матча последнего раунда.
   Именно его и нужно вывести в строке Champion: w.

3. Алгоритм

1. Считать k — число раундов.
2. Завести массив rounds, где для каждого раунда будет храниться список пар (winner, loser).
3. Для каждого раунда:
   • считать число матчей m;
   • m раз считать a, b, w;
   • определить проигравшего:
     • если w == a, то loser = b;
     • иначе loser = a;
   • сохранить пару (w, loser) в текущий раунд;
   • если это последний матч последнего раунда, запомнить champion = w.
4. После чтения всех данных:
   • для каждого раунда вывести заголовок Round i:;
   • вывести все пары winner loser;
   • в конце вывести Champion: champion.

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

Рассмотрим один матч.

Во входе даны три числа a, b, w, где w — победитель и по условию он совпадает либо с a, либо с b.

Тогда:

• если победитель a, то второй участник b обязательно проиграл;
• если победитель b, то проиграл a.

Значит, для каждого матча мы корректно восстанавливаем пару winner loser.

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

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

Следовательно, алгоритм выводит ровно требуемое представление сетки.

5. Сложность

Пусть всего в турнире n = 2^k команд.

Тогда всего матчей будет n - 1.

Для каждого матча мы выполняем константное число действий, поэтому:

• время работы: O(n)
• память: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int k;
    cin >> k;

    vector<vector<pair<int, int>>> rounds(k);
    int champion = -1;

    for (int i = 0; i < k; i++) {
        int m;
        cin >> m;
        rounds[i].reserve(m);

        for (int j = 0; j < m; j++) {
            int a, b, w;
            cin >> a >> b >> w;
            int loser;
            if (w == a) {
                loser = b;
            } else {
                loser = a;
            }
            rounds[i].push_back({w, loser});
            if (i == k - 1 && j == m - 1) {
                champion = w;
            }
        }
    }

    for (int i = 0; i < k; i++) {
        cout << "Round " << (i + 1) << ":\n";
        for (auto match : rounds[i]) {
            cout << match.first << " " << match.second << "\n";
        }
    }
    cout << "Champion: " << champion << "\n";

    return 0;
}

7. Код на Python 3

k = int(input())

rounds = []
champion = -1

for i in range(k):
    m = int(input())
    current = []
    for j in range(m):
        a, b, w = map(int, input().split())
        if w == a:
            loser = b
        else:
            loser = a
        current.append((w, loser))
        if i == k - 1 and j == m - 1:
            champion = w
    rounds.append(current)

for i in range(k):
    print(f"Round {i + 1}:")
    for winner, loser in rounds[i]:
        print(winner, loser)

print(f"Champion: {champion}")