Шёл очередной контест Петрозаводских сборов. Игроки команды Psych Up быстро нашли простую задачу, и Федя сел за компьютер. Через пять минут решение было готово. Не тратя времени на тестирование, Федя отправил его на проверку и через несколько секунд получил вердикт Time Limit Exceeded. Федя скомкал условие задачи и вышел из класса, хлопнув дверью. Что-то шло не так, нужно было развеяться. По пути в туалет он услышал разговор авторов контеста. Паша обсуждал со своим другом решение той самой задачи. Федя смог разобрать из их разговора только слова «собственные числа». Федя подумал и решил, что у него, конечно же, есть собственные числа. Например, дата рождения, номер квартиры, оценка на последнем экзамене, количество поездок на соревнования. Но ведь контест командный. А что такое собственные числа команды? Естественно, что число является собственным для команды, если оно собственное для каждого из её участников. С такими радостными мыслями Федя направился назад в аудиторию.Исходные данные Входные данные состоят из трёх блоков по две строки. Первая строка каждого блока содержит целое число n —количество собственных чисел очередного игрока (1 ≤ n ≤ 4 000). Во второй строке блока записано n целых различных чисел в порядке возрастания — собственные числа очередного игрока. Все собственные числа — целые, положительные и не превосходят 10^9.

Задача: найти «собственные числа команды» — числа, которые встречаются во всех трёх списках участников. Каждый список упорядочен по возрастанию и содержит уникальные положительные числа.

Пояснение решения (пошагово)

• Пусть A, B, C — три отсортированных массива (числа — уникальны в каждом массиве).
• Нужно взять их пересечение. Так как массивы отсортированы, можно пройтись по ним двумя-три динамическими курсорами (трёхуказательным способом).
• Идея: одновременно смотрим на текущие элементы A[i], B[j], C[k].
  • Если A[i] == B[j] == C[k], это число присутствует во всех трёх — добавляем в результат и инкрементируем все три индекса.
  • Иначе находим минимальное из трёх значений и инкрементируем соответствующий указатель(и), чтобы не пропустить возможные общие элементы.
• Продолжаем до тех пор, пока один из списков не закончится.
• В итоге получаем отсортированный список общих чисел (потому что развиваемся по отсортированным спискам).

Сложность: времени O(n1 + n2 + n3), памяти O(1) помимо входных массивов и результата.

Пример реализации

1. Python (читает из stdin все числа по порядку: n1, A; n2, B; n3, C)

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    n1 = data[idx]; idx += 1
    A = data[idx:idx+n1]; idx += n1

    n2 = data[idx]; idx += 1
    B = data[idx:idx+n2]; idx += n2

    n3 = data[idx]; idx += 1
    C = data[idx:idx+n3]; idx += n3

    i = j = k = 0
    res = []
    while i < n1 and j < n2 and k < n3:
        a, b, c = A[i], B[j], C[k]
        if a == b == c:
            res.append(a)
            i += 1
            j += 1
            k += 1
        else:
            mn = a
            if b < mn: mn = b
            if c < mn: mn = c
            if a == mn: i += 1
            if b == mn: j += 1
            if c == mn: k += 1

    print(' '.join(map(str, res)))

if __name__ == "__main__":
    solve()

2. C++ (эффективная реализация на три указателя)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n1;
    if (!(cin >> n1)) return 0;
    vector<long long> A(n1);
    for (int i = 0; i < n1; ++i) cin >> A[i];

    int n2; cin >> n2;
    vector<long long> B(n2);
    for (int i = 0; i < n2; ++i) cin >> B[i];

    int n3; cin >> n3;
    vector<long long> C(n3);
    for (int i = 0; i < n3; ++i) cin >> C[i];

    int i = 0, j = 0, k = 0;
    vector<long long> res;

    while (i < n1 && j < n2 && k < n3) {
        if (A[i] == B[j] && B[j] == C[k]) {
            res.push_back(A[i]);
            ++i; ++j; ++k;
        } else {
            long long mn = min({A[i], B[j], C[k]});
            if (A[i] == mn) ++i;
            if (B[j] == mn) ++j;
            if (C[k] == mn) ++k;
        }
    }

    for (size_t t = 0; t < res.size(); ++t) {
        if (t) cout << ' ';
        cout << res[t];
    }
    cout << '\n';
    return 0;
}

Дополнительно

• Можно решить и через преобразование одного списка в множество и пересечение множеств: result = sorted(set(A) & set(B) & set(C)). Это проще в реализации на Python и подходит для данной размерности (каждый n ≤ 4000).
• Вывод: если общих чисел нет, программа печатает пустую строку (нужно согласовать формат вывода в конкретной задаче; при необходимости можно выводить что-то вроде пустого вывода или специального значения, но здесь пустая строка корректна, если требования не против).

Если хотите, могу адаптировать код под конкретный язык или формат ввода/вывода из вашей задачи.