3.5. Разбор задач к главе «Стандартная библиотека C++»

Вам надо написать функцию Print, которая умеет печатать в поток std::cout элементы переданного контейнера через указанную строку-разделитель. Первый аргумент функции — контейнер. Гарантируется, что по этому контейнеру можно проитерироваться с помощью стандартного цикла range-based for, и что элементы контейнера можно напечатать в поток std::cout с помощью стандартного оператора <<. Второй аргумент функции — строка-разделитель, которую надо печатать между элементами. В конце необходимо напечатать перевод строки \n.

Пример вызова:

int main() {
    std::vector<int> data = {1, 2, 3};
    Print(data, ", ");  // 1, 2, 3
}

Примечание

В вашем решении должен быть только код функции Print без функции main. Подключите все необходимые для реализации библиотеки. Используйте константные ссылки для получения параметров и при итерации в цикле, чтобы избежать лишних копирований: если этого не сделать, то программа не скомпилируется.

Прежде всего определимся с заголовком функции Print. Она должна работать с любым контейнером. Проще всего будет сделать тип контейнера шаблонным параметров функции (да и название задачи на это намекает):

template <typename Container>
void Print(const Container& data, const std::string& delimiter);

Сам контейнер и строку-разделитель мы будем принимать по константной ссылке, чтобы избежать лишних и ненужных копирований. Про необходимость передачи по константной ссылке даже написано в примечании к условию (это специально проверяется в тестах).

Постараемся решить задачу, не предполагая ничего дополнительного о контейнере, кроме того, что сказано в условии. Гарантируется, что по контейнеру можно пройтись с помощью range-based for:

for (const auto& elem : data) {
    // ...
}

Строку-разделитель следует печатать только между элементами. Для этого нам нужно понимать, последний ли элемент сейчас печатается. Но гораздо проще проверять, первый ли это элемент. Заведём для этого логическую переменную, изначально установленную в true, и сбросим её на первой итерации цикла.

#include <iostream>
#include <string>

template <typename Container>
void Print(const Container& data, const std::string& delimiter) {
    bool first = true;

    for (const auto& elem : data) {
        if (!first) {
            std::cout << delimiter;
        } else {
            first = false;
        }

        std::cout << elem;
    }

    std::cout << "\n";
}

Решения, использующие итераторы, тоже допустимы, так как range-based for на самом деле под капотом обращается к функциям begin и end:

for (auto iter = std::begin(data); iter != std::end(data); ++it) {
    // ...
}

Однако не следуют проверять, является ли элемент последним, с помощью такого сравнения:

    if (iter == std::prev(std::end(data))) {
        // ...
    }

У однонаправленных итераторов (например, у односвязного списка forward_list) взятие prev приведёт к неопределенному поведению. По аналогичной причине это не будет работать с некоторыми реализациями unordered_set.

Вместо этого можно либо написать next(iter) == end(data), либо, как в решении выше, проверять не на конец, а на начало (сравнивать iter с begin(data)):

#include <iostream>
#include <iterator>
#include <string>

template <typename Container>
void Print(const Container& data, const std::string& delimiter) {
    for (auto iter = std::begin(data); iter != std::end(data); ++iter) {
        std::cout << *iter;
        if (std::next(iter) != std::end(data)) {
            std::cout << delimiter;
        }
    }
    std::cout << "\n";
}

Отметим также, что первое решение скорее всего покажет большую производительность, так как компилятору будет проще оптимизировать инструкцию if над логической переменной, а процессору будет проще предугадать правильную ветку исполнения. Однако реальная разность в производительности на такой примитивной задаче вряд ли будет заметна на уровне погрешности.

В университете проводится письменная контрольная работа. студентов сдают свои работы в общую стопку, причем некоторые кладут свою работу сверху, а другие (считая, что чем позже их работу проверят, тем лучше) — снизу. Проверяются работы в том порядке, в котором лежат, начиная с верхней. Определите, чья работа будет проверена -й по счёту.

Формат ввода

Первая строка содержит одно натуральное число , не превосходящее 10000, — число студентов.

Каждая из последующих строк содержит фамилию студента — строку из латинских букв длиной от 2 до 10 символов, и через пробел слово top или bottom — положил этот студент свою работу сверху или снизу.

Следующая строка содержит одно целое число от 0 до 10000 — для какого числа работ нужно определить их автора.

Следующие строк содержат по одному числу от 1 до — номер в стопке очередной интересующей нас работы.

Формат вывода

Выведите строк. В -й строке выведите фамилию студента, чья работа будет проверена -й по счёту.

Пример 1

Пример 2

Самая подходящая для нашей задачи структура данных — std::deque. В этот контейнер можно эффективно вставлять новые элементы по краям и обращаться к элементам по индексам. Будем хранить в деке имена студентов в том порядке, в котором их работы попадают в стопку. Для этого при считывании позиции top будем использовать функцию push_front, а в случае позиции bottom — функцию push_back. Обе функции в среднем работают за константное время.

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

int main() {
    std::deque<std::string> works;

    int n = 0;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::string name, position;
        std::cin >> name >> position;

        if (position == "top") {
            works.push_front(name);
        } else {
            works.push_back(name);
        }
    }

    int k = 0;
    std::cin >> k;
    for (int i = 0; i < k; ++i) {
        int x = 0;
        std::cin >> x;
        std::cout << works[x - 1] << "\n";
    }
}

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

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

• +left W — добавить вагон с номером слева
• +right W — добавить вагон с номером справа
• -left N — отцепить и убрать вагонов слева
• -right 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();
        }
    }

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

Петя решил написать свой собственный текстовый редактор и просит вас помочь протестировать его прототип. На текущей стадии разработки в редакторе есть только возможность загрузить файл и выполнять с ним такие действия:

• переместить курсор на строчку вниз (Down)
• переместить курсор на строчку вверх (Up)
• вырезать текущую строку в буфер обмена (Ctrl+X)
• вставить строку из буфера перед текущей строкой (Ctrl+V)

Изначально курсор находится на первой (начальной) строке.

Операции Down с курсором на последней строке и Up с курсором на первой строке должны игнорироваться.

Любой текстовый файл в системе заканчивается переводом строки. Поэтому последняя строка любого файла является пустой. Операция Ctrl+X на пустой строке ничего не делает.

Изначально буфер редактора пустой. Операция Ctrl+X перезаписывает буфер, если в нём уже было какое-то значение. Операция Ctrl+V не очищает буфер и может быть использована несколько раз подряд. Операция Ctrl+V при пустом буфере ничего не делает.

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

Формат ввода

Программе на вход подаётся набор строк, разделённых переносом строки. Длина каждой строки не превышает 3000 символов. Последняя строка в файле является пустой. Она означает завершение ввода файла. Других пустых строк в файле быть не может.

После этого и до окончания ввода программе подаются команды Down, Up, Ctrl+X, Ctrl+V.

Формат вывода

Выведите получившийся файл построчно.

Пример 1

Пример 2

Примечание

Если условие кажется вам запутанным, попробуйте воспользоваться настоящим текстовым редактором, например Sublime. Создайте пустой файл, вставьте любой пример из условия и исполняйте заданные команды. В итоге вы должны получить точно такой же файл, как в ответе. Таким образом описанное в условии поведение в точности соответствует поведению множества настоящих текстовых редакторов.

Используйте std::getline для считывания строчек файла.

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

Запишем все строки (кроме последней пустой) в список. В роли курсора будет выступать итератор списка. Вспомним, что операции над списком не инвалидируют существующие итераторы.

Далее будем последовательно обрабатывать команды.

1. Команда Up.
   Необходимо передвинуть итератор на одну позицию назад. Для этого можно воспользоваться конструкцией --cursor. Необходимо не забыть про случай, когда курсор уже находится на первой строке.

2. Команда Down.
   Необходимо передвинуть итератор на одну позицию вперёд, воспользовавшись конструкцией ++cursor. Перед этим надо проверить, не находится ли курсор на последний строке.

3. Команда Ctrl+X.
   Копируем текущее значение итератора в буфер. После этого перезаписываем курсор с помощью cursor = file.erase(cursor). Напомним, что erase возвращает итератор на следующий элемент в списке, что соответствует требуемому поведению.

4. Команда Ctrl+V.
   Проверяем, что буфер не пуст, и используем функцию insert.

#include <iostream>
#include <list>
#include <string>
#include <utility>

int main() {
    std::list<std::string> file;

    while (true) {
        std::string line;
        std::getline(std::cin, line);

        if (line.empty()) {
            break;
        }

        file.push_back(line);
    }

    auto cursor = file.begin();
    std::string buffer;

    std::string command;
    while (std::cin >> command) {
        if (command == "Up") {
            if (cursor == file.begin()) {
                continue;
            }
            --cursor;
        } else if (command == "Down") {
            if (cursor == file.end()) {
                continue;
            }
            ++cursor;
        } else if (command == "Ctrl+X") {
            if (cursor == file.end()) {
                continue;
            }
            buffer = std::move(*cursor);
            cursor = file.erase(cursor);
        } else if (command == "Ctrl+V") {
            if (buffer.empty()) {
                continue;
            }
            file.insert(cursor, buffer);
        }
    }

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

Обратите внимание, что при вырезании строки в буфер мы используем функцию std::move. Она позволяет забрать владение строкой, которая вот-вот будет удалена из списка, и сэкономить на её копировании. Подробнее про move-семантику рассказано в параграфе «Жизненный цикл объекта».

Эта задача — продолжение предыдущей задачи Ctrl+X, Ctrl+V. В качестве основы вы можете взять код оттуда.

Петя продолжает разработку своего текстового редактора. На этот раз добавилось еще одна операция — зажать клавишу Shift (Shift).

Операции Up и Down при зажатой клавише Shift выделяют строки в текстовом редакторе. Если курсор находится на строке , то после операций Shift, Down, Down выделенными окажутся строки и .

Операция Ctrl+X вырезает выделенные строки из файла в буфер. Операция Ctrl+V копирует строки из буфера, заменяя выделенные строки в файле.

Операции Ctrl+X и Ctrl+V сбрасывают выделение после исполнения и отпускают клавишу Shift. Если при исполнении этих операций в файле не выделена ни одна строка, поведение должно соответствовать предыдущей задаче Ctrl+X, Ctrl+V.

Формат ввода

Программе на вход подаётся набор строк, разделённых переносом строки. Длина каждой строки не превышает 3000 символов. Последняя строка в файле является пустой. Она означает завершение ввода файла. Других пустых строк в файле быть не может.

После этого и до окончания ввода программе подаются команды Down, Up, Ctrl+X, Ctrl+V, Shift.

Формат вывода

Выведите получившийся файл построчно.

Пример

Примечание

Для вырезания строк из файла в буфер удобно использовать функцию splice. Разберитесь самостоятельно по документации, как она устроена.

Как и рекомендуется в условии, возьмём за основу код из предыдущей задачи. Однако теперь в качестве буфера у нас будет не одна строка, а лист строк.

Также нам понадобятся дополнительные переменные для обработки нажатия клавиши Shift:

• В логической переменной shiftPressed будем поддерживать текущее состояние клавиши: true если клавиша нажата
  и false если нет.
• В переменной shift будем хранить указатель на строчку, на которой произошло нажатие клавиши Shift.
• В переменной shiftOffset будем поддерживать разность номера строки где сейчас находится курсор и номера
  строки на которой была нажата клавиша Shift.

Далее будем последовательно обрабатывать команды.

1. Команда Up.
   Добавим проверку нажата ли сейчас клавиша Shift. Если нажата – уменьшим shiftOffset на единицу. Иначе передвинем указатель shift вместе с курсором.

2. Команда Down.
   Аналогично команде Up, только здесь мы будем увеличивать shiftOffset на единицу.

3. Команда Shift.
   Единственное, что мы должны сделать при вызове этой команды – поставить переменной shiftPressed значение true.

4. Команда Ctrl+X.
   Воспользуемся функцией .splice, которая позволит нам эффективно и без копирования «вырезать» элементы из одного листа и вставить их в другой. Достаточно лишь передать этой функции два итератора cursor и shift. Воспользуемся переменной shiftOffset чтобы понять, какой из этих двух итераторов должен идти первым. Также нужно корректно обработать операцию Ctrl+X без зажатой клавиши Shift (cursor == shift). В таком случае необходимо заранее сделать копию курсора, иначе после операции .splice старый курсор будет ссылаться на элемент в буфере, а не в файле. В конце не забудем «обнулить» все переменные, связанные с клавишей Shift.

5. Команда Ctrl+V.
   Сначала сделаем операцию .erase, аналогично определяя порядок итераторов с помощью shiftOffset. После сделаем .insert, передав ему итераторы на наш буфер. В конце также не забудем обнулить Shift переменные.

Итоговое решение:

#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> file;

    while (true) {
        std::string line;
        std::getline(std::cin, line);

        if (line.empty()) {
            break;
        }

        file.push_back(line);
    }

    auto cursor = file.begin();

    std::list<std::string> buffer;

    bool shiftPressed = false;
    int shiftOffset = 0;
    auto shift = file.begin();

    std::string command;
    while (std::cin >> command) {
        if (command == "Up") {
            if (cursor == file.begin()) {
                continue;
            }

            --cursor;
            if (!shiftPressed) {
                shift = cursor;
            } else {
                --shiftOffset;
            }
        } else if (command == "Down") {
            if (cursor == file.end()) {
                continue;
            }

            ++cursor;
            if (!shiftPressed) {
                shift = cursor;
            } else {
                ++shiftOffset;
            }
        } else if (command == "Ctrl+X") {
            if (shift == cursor && cursor == file.end()) {
                continue;
            }

            buffer.clear();

            if (shift == cursor) {
                auto toSplice = cursor;
                cursor = std::next(cursor);
                buffer.splice(buffer.begin(), file, toSplice);
            } else if (shiftOffset < 0) {
                buffer.splice(buffer.begin(), file, cursor, shift);
                cursor = shift;
            } else {
                buffer.splice(buffer.begin(), file, shift, cursor);
            }

            shiftPressed = false;
            shift = cursor;
            shiftOffset = 0;
        } else if (command == "Ctrl+V") {
            if (buffer.empty()) {
                continue;
            }

            if (shiftOffset < 0) {
                cursor = file.erase(cursor, shift);
            } else if (shiftOffset > 0) {
                cursor = file.erase(shift, cursor);
            }

            file.insert(cursor, buffer.begin(), buffer.end());

            shiftPressed = false;
            shift = cursor;
            shiftOffset = 0;
        } else if (command == "Shift") {
            shiftPressed = true;
        }
    }

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

На вход подаётся последовательность целых чисел. Для каждого числа выведите в отдельной строке слово YES, если это число ранее встречалось в последовательности, и NO, если не встречалось.

Формат ввода

Вводится список чисел. Все числа списка находятся на одной строке и разделены пробелом. Каждое число представимо типом int.

Формат вывода

Выведите ответ на задачу.

Пример

Эту задачу удобно решить через std::set, но так как нам не важен порядок элементов, то лучше будет использовать std::unordered_set. Будем сохранять прочитанные числа и выводить каждый раз YES, если это число уже есть в нашем множестве, и NO в противном случае. Не забудем сохранить само число во множестве.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> numbers;
    int number;
    while (std::cin >> number) {
        if (numbers.contains(number)) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
            numbers.insert(number);
        }
    }
}

Можно было бы вместо вызова contains воспользоваться тем, что функция insert возвращает пару из итератора и успешности вставки:

       if (numbers.insert(number).second) {
           std::cout << "NO\n";
       } else {
           std::cout << "YES\n";
       }

Вам даны слова. Выведите в алфавитном порядке список общих букв всех слов.

Формат ввода

На вход поступают слова (по одному в строке), состоящие из маленьких латинских букв алфавита. Длина слов не превосходит 100 символов, а количество слов не превосходит 1000.

Формат вывода

Выведите в алфавитном порядке без пробелов список букв, которые присутствуют в каждом слове.

Пример 1

Пример 2

Воспользуемся контейнером std::map<char, int>. Будем для каждой буквы подсчитывать число слов, в которых эта буква встретилась. Затем напечатаем все буквы, которые встретились во всех словах.

Если какая-то буква повторяется в слове, то важно не посчитать её дважды. Для этого сначала буквы всех слов сложим в set или unordered_set.

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::map<char, int> counter;
    std::string word;
    int wordsCount = 0;
    while (std::cin >> word) {
        ++wordsCount;
        std::set<char> letters(word.begin(), word.end());
        for (char c : letters) {
            ++counter[c];
        }
    }
    for (auto [c, freq] : counter) {
        if (freq == wordsCount) {
            std::cout << c;
        }
    }
    std::cout << "\n";
}

Дан список всех файлов в некоторой файловой системе. Необходимо вывести все непустые директории этой файловой системы в лексикографическом порядке.

Гарантируется, что все пути начинаются от корня файловой системы. Все пути состоят из слешей (/), латинских символов, цифр и точек. Два слеша никогда не стоят подряд.

Формат ввода

На вход подаются строки, описывающие пути ко всем файлам в системе. Каждый путь содержится в отдельной строке. Число строк не превосходит 10000.

Формат вывода

Выведите все непустые директории в этой файловой системе в лексикографическом порядке. Каждый путь должен начинаться со слеша и заканчиваться слешом.

Пример 1

Пример 2

Воспользуемся контейнером set. Если нам дан путь к некоторому файлу, то все его родительские директории заведомо непустые. Надо будет аккуратно вырезать из этого пути все подстроки, которые заканчиваются на /, и сложить их в set.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> dirs;
    std::string path;
    while (std::getline(std::cin, path)) {
        for (size_t i = 0; i != path.size(); ++i) {
            if (path[i] == '/') {
                dirs.insert(path.substr(0, i + 1));
            }
        }
    }
    for (const auto& dir : dirs) {
        std::cout << dir << "\n";
    }
}

Профессор написал научную книгу и составил для неё предметный указатель. Это список ключевых слов, для каждого из которых указана страница, на которой это слово встречается. Теперь профессор хочет для каждой страницы выписать в алфавитном порядке все ключевые слова, которые на эту страницу попали (если такие вообще есть). Помогите профессору решить эту задачу.

Формат ввода

Сначала задано натуральное число n, не превосходящее 1000 — количество слов, которое требуется обработать. Далее идут n строк. В каждой строке сначала записано ключевое слово. Затем идёт натуральное число, также не превосходящее 1000, — номер страницы. Ключевые слова состоят из латинских букв, не бывают пустыми и по длине не превосходят 16 символов. Слова в списке, конечно, могут повторяться.

Формат вывода

Выпишите в порядке возрастания все страницы, на которых присутствуют ключевые слова. После каждого номера страницы через пробел выпишите в алфавитном порядке сами эти слова. Если на какой-то странице слово встретилось несколько раз, то повторять его не нужно. Завершающего пробела в конце строк быть не должно.

Пример

Воспользуемся ассоциативным контейнером, который будет номерам страниц сопоставлять множества слов на этой странице. Так как в ответе надо вывести страницы по возрастанию, а слова — по алфавиту, то нам подойдут упорядоченные контейнеры std::map и std::set.

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::map<int, std::set<std::string>> index;

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::string word;
        int page;
        std::cin >> word >> page;
        index[page].insert(word);
    }

    for (const auto& [page, words] : index) {
        std::cout << page;
        for (const auto& word : words) {
            std::cout << " " << word;
        }
        std::cout << "\n";
    }
}

Будем называть символьной -граммой последовательность из последовательно идущих символов в одном слове в тексте. Для данного числа подсчитайте суммарное количество каждой -граммы в тексте.

Формат ввода

В первой строке заданы два числа: m — число слов в тексте (от 1 до 100000) и n — длина -граммы (от 1 до 5). Далее идет слов. Можно считать, что слова отделены пробелами или переносами строк. Обработку пунктуации и регистра реализовывать не нужно. Читайте слова просто через std::cin >> word.

Формат вывода

Выведите все -граммы, отсортированные по убыванию частоты, а в случае равных частот — лексикографически (по алфавиту). Для каждой -граммы напечатайте также её частоту (смотрите формат в примере).

Пример

Задача похожа на классическую задачу про подсчёт частоты слов в тексте, только вместо слов надо будет подсчитывать подстроки слов длины N.

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

int main() {
    size_t m, n;
    std::cin >> m >> n;

    std::unordered_map<std::string, int> freqs;

    for (size_t i = 0; i != m; ++i) {
        std::string word;
        std::cin >> word;
        for (size_t j = n; j <= word.size(); ++j) {
            ++freqs[word.substr(j - n, n)];
        }
    }

    std::vector<std::pair<std::string, int>> sorted(freqs.begin(), freqs.end());
    std::sort(
        sorted.begin(),
        sorted.end(),
        [](const auto& p1, const auto& p2) {
            return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first);
        }
    );

    for (const auto& [word, freq] : sorted) {
        std::cout << word << " - " << freq << "\n";
    }
}

Пожалуй, самый нетривиальный фрагмент здесь — выделение подстрок:

for (size_t j = n; j <= word.size(); ++j) {
    ++freqs[word.substr(j - n, n)];
}

Здесь j пробегает все позиции за последним символом подстроки. Соотвественно, j - n — всевозможные начальные позиции подстрок длины n. Так организованный цикл защищён от случайных переполнений и вычитаний большего числа из меньшего в беззнаковом типе size_t. В таких конструкциях всегда полезно проверять себя на "крайних" случаях (например, когда n совпадает с word.size()).

Если известно, что n мало по сравнению со средним размером слова, то более выгодным по скорости может оказаться другое решение: сначала сохраняем в std::unordered_map все слова, а сами -граммы строим как std::unordered_map<std::string_view, int>:

#include <algorithm>
#include <iostream>
#include <string>
#include <string_view>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

int main() {
    size_t m, n;
    std::cin >> m >> n;

    std::unordered_map<std::string, int> words;
    words.reserve(m);
    for (size_t i = 0; i != m; ++i) {
        std::string word;
        std::cin >> word;
        ++words[word];
    }

    std::unordered_map<std::string_view, int> freqs;

    for (const auto& [word, freq] : words) {
        std::string_view sv = word;
        for (size_t j = n; j <= sv.size(); ++j) {
            freqs[sv.substr(j - n, n)] += freq;
        }
    }

    std::vector<std::pair<std::string_view, int>> sorted(freqs.begin(), freqs.end());
    std::sort(
        sorted.begin(),
        sorted.end(),
        [](const auto& p1, const auto& p2) {
            return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first);
        }
    );

    for (const auto& [word, freq] : sorted) {
        std::cout << word << " - " << freq << "\n";
    }
}

Требуется написать шаблонную функцию Duplicate, которая получает на вход вектор и дублирует все его элементы в конце вектора. Например, из вектора с элементами 1, 2, 3 должен получиться вектор с элементами 1, 2, 3, 1, 2, 3. Вася написал вот такую реализацию, которая почему-то не работает:

#include <vector>

template <typename T>
void Duplicate(std::vector<T>& v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        v.push_back(*it);
    }
}

Вам надо исправить код Васи.

Примечания

Сдайте в систему только исправленный код функции Duplicate без функции main. Подключите все необходимые для вашей реализации библиотеки. Заголовок функции Вася написал правильно, в этом можете не сомневаться.

Решение Васи не работает, так как в процессе вставки итераторы вектора инвалидируются и программа попадает в неопределённое поведение. Самый простой способ исправить проблему — переписать цикл через индексы. При этом исходный размер вектора надо запомнить в начале цикла. Это можно сделать прямо в секции инициализации цикла for:

#include <vector>

template <typename T>
void Duplicate(std::vector<T>& v) {
    for (size_t n = v.size(), i = 0; i < n; ++i) {
        v.push_back(v[i]);
    }
}

Другой способ — зарезервировать в векторе заранее удвоенное число элементов. Тогда при вставке не будет происходить реаллокаций, и итераторы не будут инвалидироваться. Исходное решение заработает. Но его всё же удобнее переписать через алгоритм copy:

#include <algorithm>
#include <vector>

template <typename T>
void Duplicate(std::vector<T>& v) {
    v.reserve(v.size() * 2);
    std::copy(v.begin(), v.end(), std::back_inserter(v));
}

Вам надо написать свою реализацию стандартного алгоритма unique. Заголовок функции должен быть таким:

template <typename Iter>
Iter Unique(Iter first, Iter last);

Функция должна переупорядочить элементы диапазона [first; last) так, чтобы подряд идущие одинаковые элементы в ней не встречались. Функция возвращает итератор за последний элемент итоговой последовательности. Что останется в пределах от этого вернувшегося итератора до старого last — не важно. Время работы функции должно линейно зависеть от длины диапазона.

Примечания

В вашем решении должен быть только код этой шаблонной функции и не должно быть функции main. Использовать вызов std::unique нельзя.

Будем идти по диапазону от начала до конца двумя итераторами. Первый итератор будет сдвигаться всегда на одну позицию вправо. А второй итератор будет проматывать повторы, сдвигаясь на ближайший правый элемент, отличный от текущего. Будем записывать значение из второго итератора в ячейку, на которую указывает первый итератор. В конце цикла первый итератор как раз будет указывать за последний записанный элемент.

template <typename Iter>
Iter Unique(Iter first, Iter last) {
    auto it1 = first;
    auto it2 = first;
    while (it2 != last) {
        if (it1 != it2) {
            *it1 = *it2;
        }
        ++it1;
        const auto& value = *it2;
        while (it2 != last && *it2 == value) {
            ++it2;
        }
    }
    return it1;
}

Заметим, что вместо *it1 = *it2 правильнее было бы написать *it1 = std::move(*it2), так как нам больше не потребуется значение в ячейке *it2, и у него можно отобрать владение. Это имеет смысл, если значения — сложные типы с нетривиальным копированием (например, контейнеры). Подробнее про move-семантику рассказано в параграфе «Жизненный цикл объекта».

Напишите свою реализацию стандартного алгоритма set_difference. Заголовок функции должен быть таким:

template <typename InIter1, typename InIter2, typename OutIter>
OutIter SetDifference(InIter1 first1, InIter1 last1,
                      InIter2 first2, InIter2 last2,
                      OutIter out);

Функция должна сформировать элементы разности диапазонов [first1, last1) и [first2, last2) и записать их в последовательность, начинающуюся с out. Исходные диапазоны предполагаются отсортированными. Каждый элемент считается со своей кратностью. Функция должна вернуть итератор, который указывает за последний записанный элемент.

Примечания

В вашем решении должен быть только код этой шаблонной функции и не должно быть функции main. Программа должна использовать константную память и быть линейной по сложности. Допускается сравнивать итераторы с помощью == и !=, а также сравнивать элементы с помощью <. Использовать вызов std::set_difference нельзя.

Будем идти двумя итераторами it1 и it2 по первому и второму диапазонам. Если текущий элемент во втором диапазоне меньше элемента в первом, то промотаем второй итератор вперёд. Если текущие элементы в диапазонах оказались разными, то элемент первого диапазона не встречается во втором и должен попасть в ответ. Если же элементы оказались равными, то нужно продвинуть оба итератора на одну позицию вперёд.

В реализации необходимо следить за тем, чтобы итераторы не вышли за допустимые границы. К тому же, сравнивать сами элементы можно только с помощью оператора <.

template <typename InIter1, typename InIter2, typename OutIter>
OutIter SetDifference(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter out) {
    auto it1 = first1;
    auto it2 = first2;

    while (it1 != last1) {
        while (it2 != last2 && *it2 < *it1) {
            ++it2;
        }
        if (it2 == last2 || *it1 < *it2) {
            *out = *it1;
            ++out;
        } else if (it2 != last2) {
            ++it2;
        }
        ++it1;
    }
    return out;
}

В этой задаче нужно применить функцию std::lower_bound и итераторы для быстрого поиска ближайшего элемента в отсортированном массиве.

Формат ввода

В первой строке входных данных содержатся натуральные числа n и k, не превосходящие 100000. Во второй строке задаются целых n чисел первого массива, отсортированного по неубыванию, а в третьей строке – k целых чисел второго массива. Каждое число в обоих массивах по модулю не превосходит . Второй массив, в отличие от первого, не отсортирован.

Формат вывода

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

Сложим числа первого массива в вектор. Второй массив складывать в вектор не нужно: мы сможем подбирать ближайший элемент из первого массива на лету. Оформим этот подбор в функции Approx. Она получает на вход первый массив и число x из второго массива. Так как первый массив отсортирован, то мы можем применить алгоритм std::lower_bound, чтобы бинарным поиском найти итератор первого элемента, большего или равного x. Дальше возможны такие взаимоисключающие случаи:

1. Все числа в массиве меньше x. Тогда вернётся итератор end(). Достаточно вернуть последнее число из массива.
2. Все числа в массиве больше x. Тогда вернётся итератор begin(). Возвращаем первое число из массива.
3. В массиве есть число x. Его и возвращаем.
4. В массиве есть числа как меньшие x, так и большие x, но нет самого x. Тогда надо сравнить с x два элемента: *std::prev(iter) и *iter.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int Approx(const std::vector<int>& v, int x) {
    auto iter = std::lower_bound(v.begin(), v.end(), x);
    if (iter == v.end()) {
        return *std::prev(iter);
    } else if (iter == v.begin()) {
        return *iter;
    } else if (*iter == x) {
        return *iter;
    } else {
        int x1 = *std::prev(iter);
        int x2 = *iter;
        if (std::abs(x1 - x) <= std::abs(x2 - x)) {
            return x1;
        } else {
            return x2;
        }
    }
}

int main() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> v(n);
    for (int i = 0; i != n; ++i) {
        std::cin >> v[i];
    }

    for (int i = 0; i != k; ++i) {
        int x;
        std::cin >> x;
        std::cout << Approx(v, x) << "\n";
    }
}

Андрею надо написать шаблонную функцию Process, которая обрабатывает вектор с числами некоторого типа T. Его функция должна вызвать другую функцию PrintResults, чтобы напечатать с определенным форматированием положительные числа из вектора. Функция PrintResults принимает на вход пару итераторов, как и многие алгоритмы стандартной библиотеки. Поэтому Андрей решил сначала скопировать нужные элементы исходного вектора в другой массив, чтобы передать его начало и конец в эту функцию.
Вот код Андрея:

#include <algorithm>
#include <vector>

template <typename T>
void Process(const std::vector<T>& data) {
    std::vector<T> filtered;

    auto filteredLast = std::copy_if(
        data.begin(),
        data.end(),
        filtered.begin(),
        [](const T& x) { return x > 0; }
    );

    PrintResults(filtered.begin(), filteredLast);
}

Этот код почему-то не работает. Найдите ошибку и сдайте исправленное решение.

Примечания

Вам нужно сдать только исправленный код Андрея. В вашей программе не должно быть функции main.

Проблема в том, что в решении Андрея применяется алгоритм std::copy_if к пустой выходной последовательности. Правильнее всего будет воспользоваться функций std::back_inserter. Теперь можно не запоминать результат работы copy_if: он всё равно будет равен filtered.end().

#include <algorithm>
#include <iterator>
#include <vector>

template <typename T>
void Process(const std::vector<T>& data) {
    std::vector<T> filtered;

    std::copy_if(
        data.begin(),
        data.end(),
        std::back_inserter(filtered),
        [](const T& x) { return x > 0; }
    );

    PrintResults(filtered.begin(), filtered.end());
}

На вход подаётся скобочная последовательность — строка, которая состоит из скобок ()[]{}. Вам нужно определить, является ли она правильной. В правильной скобочной последовательности каждой открывающей скобке соответствует закрывающая и пары скобок корректно вложены друг в друга.

Формат ввода

Строка, состоящая из символов ()[]{}.

Формат вывода

Напечатайте YES, если скобочная последовательность является правильной, и NO в противном случае.

Пример 1

Пример 2

Пример 3

Воспользуемся адаптером std::stack. Будем помещать в стек открывающие скобки. Если нам встретилась закрывающая скобка, то убедимся, что она соответствует открывающей скобке на вершине стека и уберём из стека эту вершину. Скобочная последовательность будет правильной, если в конце стек окажется пустым. Удобно оформить этот алгоритм в виде функции IsCorrect, которая принимает строку.

#include <iostream>
#include <stack>
#include <string>

bool IsCorrect(const std::string& sequence) {
    std::stack<char> brackets;

    for (char bracket : sequence) {
        if (bracket == '(' || bracket == '{' || bracket == '[') {
            brackets.push(bracket);
        } else {
            if (brackets.empty()) {
                return false;
            }
            char top = brackets.top();
            if ((top == '(' && bracket == ')') || (top == '{' && bracket == '}') || (top == '[' && bracket == ']')) {
                brackets.pop();
            } else {
                return false;
            }
        }
    }

    return brackets.empty();
}

int main() {
    std::string sequence;
    std::getline(std::cin, sequence);
    if (IsCorrect(sequence)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Рассмотрим последовательность целых чисел длины . По ней с шагом 1 двигается «окно» длины . Другими словами, сначала в «окне» видны первые чисел, на следующем шаге в «окне» уже будут находиться чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения «окна» определить в нём минимальное число.

Формат ввода

В первой строке входных данных содержатся два натуральных числа и — длины последовательности и «окна». При этом , , . На следующей строке находятся чисел — сама последовательность.

Формат вывода

Выходые данные должны содержать строк — минимумы для каждого положения «окна».

Пример

Примечание

Для решения задачи рекомендуется использовать std::multiset для хранения окна. Решение с непосредственным подсчётом минимума для каждого положения окна будет неэффективным.

С одной стороны, нам потребуется хранить последовательность чисел в окне, чтобы знать, в каком порядке они будут выходить из окна. Можно было бы сложить все числа в std::vector, но это слишком расточительно. Достаточно хранить только элементы из окна. На эту роль отлично подходит адаптер std::queue.

С другой стороны, нам надо уметь быстро находить минимальный элемент в окне. Для этого можно воспользоваться контейнером std::multiset (числа могут повторяться, поэтому std::set не подойдёт).

Итак, алгоритм таков:

1. Добавляем в окно новый элемент.
2. Если окно заполнено, то печатаем минимальный элемент окна и удаляем из него крайний элемент.

#include <iostream>
#include <queue>
#include <set>

int main() {
    int n, k;
    std::cin >> n >> k;

    std::queue<int> numbers;
    std::multiset<int> window;

    for (int i = 1; i <= n; ++i) {
        int x;
        std::cin >> x;
        numbers.push(x);
        window.insert(x);
        if (i >= k) {
            std::cout << *window.begin() << "\n";
            auto iter = window.find(numbers.front());
            window.erase(iter);
            numbers.pop();
        }
    }
}

Напишите программу, которая будет обрабатывать последовательность запросов таких видов:

1. CLEAR — сделать очередь с приоритетами пустой (если в очереди уже были какие-то элементы, то удалить все).

2. ADD n — добавить в очередь с приоритетами число n (вмещается в стандартный тип int).

3. EXTRACT — вынуть из очереди с приоритетами максимальное значение. Следует изменить данные в памяти и вывести на экран найденное максимальное значение, или, если очередь была пустой, слово CANNOT.

Формат ввода

Во входных данных записана произвольная последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке. Суммарное количество всех запросов не превышает 200000.

Формат вывода

Для каждого запроса типа EXTRACT выведите его результат в отдельной строке.

Пример

Название задачи подсказывает, что нужно использовать контейнер std::priority_queue. Фактически, нужно реализовать обработчик команд. Так как отдельной функции clear у адаптеров нет, то придётся очищать очередь поэлементно.

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    std::string command;
    while (std::cin >> command) {
        if (command == "CLEAR") {
            while (!pq.empty()) {
                pq.pop();
            }
        } else if (command == "ADD") {
            int x;
            std::cin >> x;
            pq.push(x);
        } else if (command == "EXTRACT") {
            if (pq.empty()) {
                std::cout << "CANNOT\n";
            } else {
                std::cout << pq.top() << "\n";
                pq.pop();
            }
        }
    }
}

Вам надо написать функцию NextToken для выделения очередного токена в строке. Токеном считается последовательность символов до указанного символа-разделителя (или до конца строки).

Использоваться функция будет примерно так:

int main() {
    std::string_view sv = "Hello world and good bye";

    const char delimiter = ' ';
    std::string_view token;

    // Делим строку на токены по разделителю и перебираем эти токены:
    while (NextToken(sv, delimiter, token)) {
        // обрабатываем очередной token
        // например, печатаем его на экране:
        std::cout << token << "\n";
    }
}

Результатом выполнения такой программы будет

Hello
world
and
good
bye

Сдайте только код функции NextToken и подключите необходимые библиотеки. Ваша функция будет скомпилирована с нашей функцией main. Гарантируется, что входная строка не заканчивается на разделитель. Догадайтесь сами, какие аргументы должна принимать функция NextToken. Эта функция может менять первый аргумент (sv).

Первый аргумент функции имеет тип std::string_view: это не самостоятельная строка, а отсылка к подстроке какой-то другой строки. По условию задачи её можно изменять. Будем при каждом вызове функции сдвигать её к началу следующего токена. Для этого будем этот аргумент будем принимать по ссылке. Аналогично, последний аргумент функции тоже изменяется (в него должен быть записан токен), поэтому он тоже должен быть принят по ссылке.

Заметим, что функция возвращает false, если токенов больше нет.

#include <string_view>

bool NextToken(std::string_view& sv, char delim, std::string_view& tok) {
    if (sv.empty()) {
        return false;
    }

    auto pos = sv.find(delim);
    if (pos != sv.npos) {  // разделитель найден
        tok = sv.substr(0, pos);  // вырезаем очередной токен
        sv.remove_prefix(pos + 1);  // сдвигаем sv за разделитель
    } else {
        tok = sv;
        sv.remove_prefix(sv.size());  // формально тут получится пустая строка
    }
    return true;
}

Такая функция не может отличить случай изначально пустой строки от случая последнего пустого токена в строке, которая заканчивается на разделитель. Однако по условию задачи это не важно.

Выведите k самых частотных слов текста и их частоты.

Формат ввода

В первой строке указано натуральное число k, не превосходящее 1000. Далее идут строки текста объёмом до 1 Mб. Слова в тексте разделены пробелами или переводами строк. Различать регистр и обрабатывать пунктуацию не нужно.

Формат вывода

В выводе должно быть не более k самых частотных слов текста. Через табуляцию после слова напечатайте его частоту. Слова должны быть упрядочены по убыванию частоты, а при равенстве частот — по алфавиту.

Пример

В параграфе про ассоциативные контейнеры мы рассматривали задачу про частотный словарь. Там мы печатали весь словарь целиком. В этой задаче требуется вывести только k самых частотных слов, где k мало по сравнению с размером словаря. Для этого можно было бы переложить слова в вектор и воспользоваться алгоритмомpartial_sort:

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

int main() {
    size_t k;
    std::cin >> k;

    // Подсчитываем частоты слов
    std::unordered_map<std::string, int> words;
    std::string word;
    while (std::cin >> word) {
        ++words[word];
    }

    // Переносим слова и их частоты в вектор
    std::vector<std::pair<std::string, int>> v(words.begin(), words.end());

    // Находим максимальные k элементов
    std::partial_sort(
        v.begin(),
        v.begin() + std::min(v.size(), k),  // k может оказаться больше размера вектора
        v.end(),
        [](const auto& p1, const auto& p2) { return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first); }
    );

    // Печатаем топовые слова
    for (size_t i = 0; i < k && i < v.size(); ++i) {
        const auto& [word, freq] = v[i];
        std::cout << word << "\t" << freq << "\n";
    }
}

Рассмотрим аналогичное решение, где вместо std::partial_sort используется адаптер std::priority_queue. Мы будем поддерживать в очереди с приоритетами не более k элементов. В качестве значений положим туда пары из частоты и самого слова, причём частоту умножим на -1, чтобы она стала отрицательной. Этот трюк позволит выкидывать с вершины очереди пару с минимальной по модулю частотой, а в случае равенства частот — с лексикографически максимальным словом.

Когда все слова будут обработаны, в очереди с приоритетами останутся нужные нам слова. Но извлекаться они будут в противоположном порядке. Чтобы получить правильный порядок, проще всего скопировать их в вектор и развернуть этот вектор наоборот.

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

int main() {
    size_t k;
    std::cin >> k;

    std::unordered_map<std::string, int> words;
    std::string word;
    while (std::cin >> word) {
        ++words[word];
    }

    using TPair = std::pair<int, std::string>;  // удобный псевдоним для типа

    std::priority_queue<TPair> pq;
    for (const auto& [word, freq] : words) {
        pq.push({-freq, word});  // нарочно кладём отрицательную частоту
        if (pq.size() > k) {
            pq.pop();  // выкидываем элемент с минимальной (то есть, максимальной отрицательной) частотой
        }
    }

    // Копируем элементы в вектор
    std::vector<TPair> top;
    top.reserve(k);

    while (!pq.empty()) {
        const auto& [freq, word] = pq.top();
        top.push_back({-freq, word});  // возвращаем настоящую частоту
        pq.pop();
    }

    // Переворачиваем вектор
    std::reverse(top.begin(), top.end());

    for (const auto& [freq, word] : top) {
        std::cout << word << "\t" << freq << "\n";
    }
}