Вопрос задан 24.09.2026 в 13:54. Предмет Информатика. Спрашивает Овчинникова Лера.

Задача C. Работа Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Жарасхан работает в крупной корпорации "ӘСЕМ". У Жарасхана есть n документов выложенных в ряд. В каждом документе содержится секретное число ai. Также у Жарасхана есть некоторые поручения от начальника. Есть 3 типа поручений: В поручениях первого типа начальник просит сообщить секретное число в самом левом документе, а затем уничтожить этот документ. В поручениях второго типа начальник просит сообщить секретное число в самом правом документе, а затем уничтожить этот документ. В поручениях третьего типа начальник просит сообщить секретное число в документе который лежит в середине всех документов, а затем уничтожить этот документ. Если у списка документов нет серединного документа, выбрать документ который лежит слева от середины. Но Жарасхан заранее знает что начальство даст все поручения в повторяющемся порядке. А именно начальник даст поручение первого типа, затем второго, затем третьего, и еще раз первого, второго, третьего и так далее пока список документов не окажется пуст. Жарасхан очень занят другими поручениями. Он просит вас помочь, иначе он лишится работы. Формат входных данных В первой строке входных данных содержит единственное целое положительное число n (1 ⩽ n ⩽ 105) — количество документов в списке. Вторая строка содержит n целых чисел ai (1 ⩽ ai ⩽ 109) — секретные числа в документах. Формат выходных данных Выведите n чисел — секретные числа которых должен Жарасхан сообщить начальнику после каждой операции. Система оценки 56% тестов имеют ограничения 1 ⩽ n ⩽ 1000 44% тестов имеют ограничения 1 ⩽ n ⩽ 105 В данной задаче ровно 50 тестов. За каждый пройденный тест участник получает 2 балла. Пример стандартный ввод стандартный вывод 6 4 5 9 8 6 7 4 7 9 5 6 8 Замечание В первом тестовом примере удаляется первое число. Оставшиеся документы: [5, 9, 8, 6, 7] Затем удаляется последнее число. Оставшиеся документы: [5, 9, 8, 6] Так как список не имеет серединного документа, следует выбрать число которое лежит слева от середины. Оставшиеся документы: [5, 8, 6] Эти поручения обрабатываются и дальше по такому же порядку.

Перейти к ответам

Отвечу на вопрос мгновенно! Нейросеть ChatGPT. Жми!

Ответы на вопрос

Отвечает Алхазов Филипп.

Задачу удобно решать через двусвязный список: в нём можно удалять левый, правый и средний элемент за \(O(1)\), если заранее хранить итератор на середину.

Средний документ — это элемент с индексом \(\lfloor (m-1)/2 \rfloor\), где \(m\) — текущее количество документов. Если документов чётное число, берём левый из двух центральных.

Поддерживаем итератор \(mid\) на середину. После каждого удаления сдвигаем его:

удалили левый: если старая длина была чётной, \(mid\) сдвигается вправо;
удалили правый: если старая длина была нечётной, \(mid\) сдвигается влево;
удалили середину: если старая длина была чётной, новая середина справа от удалённой, иначе слева.

Пример кода на C++:

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

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

    int n;
    cin >> n;
    list<long long> a;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        a.push_back(x);
    }

    auto mid = a.begin();
    advance(mid, (n - 1) / 2);

    for (int op = 0; op < n; op++) {
        int m = a.size();

        if (op % 3 == 0) {
            auto it = a.begin();
            cout << *it << ' ';
            if (m == 1) { a.erase(it); break; }
            if (m % 2 == 0) ++mid;
            a.erase(it);
        } else if (op % 3 == 1) {
            auto it = prev(a.end());
            cout << *it << ' ';
            if (m == 1) { a.erase(it); break; }
            if (m % 2 == 1) --mid;
            a.erase(it);
        } else {
            auto it = mid;
            cout << *it << ' ';
            if (m == 1) { a.erase(it); break; }
            if (m % 2 == 0) mid = next(it);
            else mid = prev(it);
            a.erase(it);
        }
    }

    return 0;
}