Wagons.md

Разбор задачи "Вагоны"

Условие

Вы - машинист. Вам поручено реализовать функцию void MakeTrain(), чтобы сформировать поезд из набора вагонов.

У каждого вагона есть номер (помещается в int). Номера вагонов внутри состава могут повторяться.

Изначально путь, на котором формируется состав, пустой. Вы должны уметь выполнять следующие команды, которые поступают в отдельных строках на входе:

+left W - добавить вагон с номером W слева

+right W - добавить вагон с номером W справа

-left N - отцепить и убрать N вагонов слева

-right N - отцепить и убрать N вагонов справа

В последних двух командах N может быть больше текущей длины состава - в этом случае надо убрать весь состав целиком. Отцеплять вагоны по одному может быть долго: постарайтесь сразу отцеплять по N штук.

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

На вход подаются строки с командами в указанном формате. Всего будет не более 1 млн команд. Оформите ваше решение в функции void MakeTrain(). Эта функция должна читать данные со стандартного потока ввода и печатать их в стандартный поток вывода. Подключите все необходимые библиотеки. В вашем решении не должно быть функции main.

Решение

Для хранения последовательности вагонов нам нужен контейнер, позволяющий эффективно добавлять и удалять элементы с обоих концов. Мы знаем два таких контейнера в стандартной библиотеке - std::list и std::deque.

В условии есть совет отцеплять вагоны сразу по N штук. Это намекает на то, что deque будет более подходящим контейнером: его итераторы являются итераторами произвольного доступа, а значит, можно будет быстро найти место расцепки.

К тому же в задании есть нестандартные ограничения по времени. Контейнер std::list может оказаться медленнее дека, потому что он аллоцирует отдельные ячейки памяти под каждый элемент. Напротив, std::deque аллоцирует сразу большие страницы памяти.

Итак, выбираем std::deque<int>:

#include <deque>
#include <iostream>
#include <string>

void MakeTrain() {
    using Wagon = int;
    std::deque<Wagon> train;

    std::string command;
    Wagon wagon;
    size_t k;
    while (std::cin >> command) {
        if (command == "+left") {
            std::cin >> wagon;
            train.push_front(wagon);
        } else if (command == "+right") {
            std::cin >> wagon;
            train.push_back(wagon);
        } else if (command == "-left") {
            std::cin >> k;
            k = std::min(k, train.size());
            train.erase(train.begin(), train.begin() + k);
        } else if (command == "-right") {
            std::cin >> k;
            k = std::min(k, train.size());
            train.erase(train.end() - k, train.end());
        }
    }

    for (const auto& wagon : train) {
        std::cout << wagon << " ";
    }
    std::cout << "\n";
}

Здесь мы используем псевдоним Wagon вместо int, чтобы в будущем можно было легко поменять тип. (В конце при выводе вагонов по-хорошему не надо было бы печатать последний пробел, но в тестах ответ проверяется с точность до пробельных символов в конце, и такое решение проходит.)

Мы специально просим в этой задаче написать код в отдельной функции, чтобы в своей функции main позвать std::ios_base::sync_with_stdio(false) и ускорить ввод-вывод, так что накладные расходы на ввод-вывод данных будут минимальными.

Можно сгенерировать искусственный тест, где будут случайные добавления вагонов с разных сторон, а потом - серия мелких удалений (и так несколько раз). Попробуем сравнить скорость работы этой программы для deque и для list на таком тесте с опцией компилятора -O3 (то есть, с полностью включенными оптимизациями). Оказывается, что list медленнее на 20%.

Заметим, что в решении с deque отцепка вагонов по одному через pop_back или pop_front на самом деле оказывается не медленнее вызова erase с парой итераторов.

Неверные решения

Разберём два неправильных решения этой задачи. Первое - пытаться считывать данные через getline в строку, а потом отдельно разбирать её через stringstream:

    std::string line;
    std::string command;
    Wagon wagon;
    while (std::getline(std::cin, line)) {
        std::istringstream ss(line);
        ss >> command >> wagon;
        // ...
    }

Это удобно, но в данном случае сильно замедляет программу. Поток istringstream внутри хранит копию исходной строки, а на это требуются накладные расходы.

Второе ошибочное решение - такое:

    if (command == "+left") {
        std::cin >> wagon;
        train.push_front(wagon);
    } else if (command == "+right") {
        std::cin >> wagon;
        train.push_back(wagon);
    } else if (command == "-left") {
        std::cin >> k;
        for (size_t i = 0; i < std::min(k, train.size()); ++i) {
            train.pop_front();
        }
    } else if (command == "-right") {
        std::cin >> k;
        for (size_t i = 0; i < std::min(k, train.size()); ++i) {
            train.pop_back();
        }
    }

Тут просто будет неверный ответ. Найдите ошибку самостоятельно.