README.md

    Решение задач, на языке C++, из двух курсов “Алгоритмы: теория и практика. Методы” и “Алгоритмы: теория и практика. Структуры данных” на образовательной платформе Stepik

    Условия задач взяты из материалов Алгоритмы: теория и практика. Методы и Алгоритмы: теория и практика. Структуры данных. Данные задачи выполняюются путем консольного ввода (через cin) данных и оценкой выведенного результата через консоль (через cout). Тестовые входные данные с выходными данными, для каждой задачи, приведены в материалах курса.

    1.Алгоритмы: теория и практика. Методы: (20/20)

    2.Алгоритмы: теория и практика. Структуры данных: (15/17)

    Алгоритмы: теория и практика. Методы

    Раздел 2. Введение: теория и задачи.


    • Задача 2.1. Небольшое число Фибоначчи

      Дано целое число 1 ≤ n ≤ 40, необходимо вычислить n число Фибоначчи.

      Решение: a_small_Fibonacci_number.cpp

    • Задача 2.2. Последняя цифра большого числа Фибоначчи.

      Дано число 1 ≤ n ≤ 10^7, необходимо найти последнюю цифру n-го числа Фибоначчи.

      Решение: the_last_digit_of_a_large_Fibonacci_number.cpp

    • Задача 2.3. Огромное число Фибоначчи по модулю.

      Даны целые числа 1 ≤ n ≤ 10^18 и 2 ≤ m ≤ 10^5, необходимо найти остаток от деления n-го числа Фибоначчи на m.

      Решение: a_huge_Fibonacci_number_modulo.cpp

    • Задача 2.4. Наибольший общий делитель.

      По данным двум числам 1 ≤ a, b ≤ 2⋅10^9, найдите их наибольший общий делитель.

      Решение: greatest_common_divisor.cpp

    Раздел 4. Жадные алгоритмы: теория и задачи.


    • Задача 4.1. Покрыть отрезки точками.

      По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек. В первой строке дано число 1 ≤ n ≤ 100 отрезков. Каждая из последующих n строк содержит по два числа 0 ≤ l < r ≤ 10^9, задающих начало и конец отрезка. Выведите оптимальное число m точек и сами m точек. Если таких множеств точек несколько, выведите любое из них.

      Решение: points_on_the_segment.cpp

    • Задача 4.2. Непрерывный рюкзак.

      Первая строка содержит количество предметов 1 ≤ n ≤ 10^3 и вместимость рюкзака 0 ≤ W ≤ 2⋅10^6. Каждая из следующих n строк задаёт стоимость 0 ≤ ci ≤ 2⋅10^6 и объем 0 < wi ≤ 2⋅10^6 предмета (n, W, ci, wi - целые числа). Выведите максимальную стоимость частей предметов (от каждого предмета можно отделить любую часть, стоимость и объём при этом пропорционально уменьшатся), помещающихся в данный рюкзак, с точностью не менее трёх знаков после запятой.

      Решение: continuous_backpack.cpp

    • Задача 4.3. Различные слагаемые.

      По данному числу 1 ≤ n ≤ 10^9 найдите максимальное число k, для которого n можно представить как сумму k различных натуральных слагаемых. Выведите в первой строке число k, во второй — k слагаемых.

      Решение: various_summand.cpp

    • Задача 4.4. Кодирование Хаффмана.

      По данной непустой строке s длины не более 10^4, состоящей из строчных букв латинского алфавита, постройте оптимальный беспрефиксный код. В первой строке выведите количество различных букв k, встречающихся в строке, и размер получившейся закодированной строки. В следующих k строках запишите коды букв в формате “letter: code”. В последней строке выведите закодированную строку.

      Решение: huffman_coding.cpp

    • Задача 4.5. Декодирование Хаффмана.

      Восстановите строку по её коду и беспрефиксному коду символов. В первой строке входного файла заданы два целых числа k и l через пробел — количество различных букв, встречающихся в строке, и размер получившейся закодированной строки, соответственно. В следующих k строках записаны коды букв в формате “letter: code”. Ни один код не является префиксом другого. Буквы могут быть перечислены в любом порядке. В качестве букв могут встречаться лишь строчные буквы латинского алфавита; каждая из этих букв встречается в строке хотя бы один раз. Наконец, в последней строке записана закодированная строка. Исходная строка и коды всех букв непусты. Заданный код таков, что закодированная строка имеет минимальный возможный размер. В первой строке выходного файла выведите строку s. Она должна состоять из строчных букв латинского алфавита. Гарантируется, что длина правильного ответа не превосходит 10^4 символов.

      Решение: huffman_decoding.cpp

    • Задача 4.6. Очередь с приоритетами.

      Первая строка входа содержит число операций 1 ≤ n ≤ 10^5. Каждая из последующих n строк задают операцию одного из следующих двух типов: Insert x, где 0 ≤ x ≤ 10^9 — целое число; ExtractMax. Первая операция добавляет число x в очередь с приоритетами, вторая — извлекает максимальное число и выводит его.

      Решение: priority_queue.cpp

    Раздел 6. “Разделяй и властвуй”: теория и задачи.


    • Задача 6.1. Двоичный поиск.

      В первой строке даны целое число 1 ≤ n ≤ 10^5 и массив A[1 … n] из n различных натуральных чисел, не превышающих 10^9, в порядке возрастания, во второй — целое число 1 ≤ k ≤ 10^5 и k натуральных чисел b1 ,…, bk, не превышающих 10^9. Для каждого i от 1 до k необходимо вывести индекс 1 ≤ j ≤ n, для которого A[j] = bi, или −1, если такого j нет.

      Решение: binary_search.cpp

    • Задача 6.2. Число инверсий.

      Первая строка содержит число 1 ≤ n ≤ 10^5, вторая — массив A[1 … n], содержащий натуральные числа, не превосходящие 10^9. Необходимо посчитать число пар индексов 1 ≤ i < j ≤ n, для которых A[i] > A[j]. (Такая пара элементов называется инверсией массива. Количество инверсий в массиве является в некотором смысле его мерой неупорядоченности: например, в упорядоченном по неубыванию массиве инверсий нет вообще, а в массиве, упорядоченном по убыванию, инверсию образуют каждые два элемента.)

      Решение: number_of_inversions.cpp

    • Задача 6.3. Точки и отрезки.

      В первой строке задано два целых числа 1 ≤ n ≤ 50000 и 1 ≤ m ≤ 50000 — количество отрезков и точек на прямой, соответственно. Следующие n строк содержат по два целых числа ai и bi ai ≤ bi) — координаты концов отрезков. Последняя строка содержит m целых чисел — координаты точек. Все координаты не превышают 10^8 по модулю. Точка считается принадлежащей отрезку, если она находится внутри него или на границе. Для каждой точки в порядке появления во вводе выведите, скольким отрезкам она принадлежит.

      Решение: points_and_segments.cpp

    • Задача 6.4. Сортировка подсчётом.

      Первая строка содержит число 1 ≤ n ≤ 10^4, вторая — n натуральных чисел, не превышающих 10. Выведите упорядоченную по неубыванию последовательность этих чисел.

      Решение: sorting_by_counting.cpp

    Раздел 8. Динамическое программирование.


    • Задача 8.1. Наибольшая последовательнократная подпоследовательность.

      Дано целое число Дано целое число 1 ≤ n ≤ 10^3 и массив A[1 … n] натуральных чисел, не превосходящих 2⋅10^9. Выведите максимальное 1 ≤ k ≤ n, для которого найдётся подпоследовательность 1 ≤ i1 ​< i2 ​< … < ik ​≤ n длины k, в которой каждый элемент делится на предыдущий (формально: для всех 1 ≤ j < k, A[ij] A[ij+1]).

      Решение: the_greatest_sequencefold_subsequence.cpp

    • Задача 8.2. Наибольшая невозрастающая подпоследовательность.

      Дано целое число 1 ≤ n ≤ 10^5 и массив A[1 … n], содержащий неотрицательные целые числа, не превосходящие 10^9. Найдите наибольшую невозрастающую подпоследовательность в A. В первой строке выведите её длину k, во второй — её индексы 1 ≤ i1 < i2 < … < ik ≤ n (таким образом, A[i1] ≥ A[i2] ≥ … ≥ A[in]).

      Полезная информация по задаче. Решение: the_greatest_increasing_subsequence.cpp

    • Задача 8.3. Расстояние редактирования.

      Вычислите расстояние редактирования двух данных непустых строк длины не более 10^2, содержащих строчные буквы латинского алфавита.

      Решение: editing_distance.cpp

    • Задача 8.4. Рюкзак.

      Первая строка входа содержит целые числа 1 ≤ W ≤ 10^4 и 1 ≤ n ≤ 300 — вместимость рюкзака и число золотых слитков. Следующая строка содержит n целых чисел 0 ≤ w1 ,…, wn ≤ 10^5, задающих веса слитков. Найдите максимальный вес золота, который можно унести в рюкзаке.

      Решение: backpack.cpp

    • Задача 8.5. Лестница.

      Даны число 1 ≤ n ≤ 10^2 ступенек лестницы и целые числа −10^4 ≤ a1 ,…, an ≤ 10^4, которыми помечены ступеньки. Найдите максимальную сумму, которую можно получить, идя по лестнице снизу вверх (от нулевой до n-й ступеньки), каждый раз поднимаясь на одну или две ступеньки.

      Решение: stairs.cpp

    • Задача 8.6. Калькулятор.

      У вас есть примитивный калькулятор, который умеет выполнять всего три операции с текущим числом x: заменить x на 2x, 3x или x + 1. По данному целому числу 1 ≤ n ≤ 10^5 определите минимальное число операций k, необходимое, чтобы получить n из 1. Выведите k и последовательность промежуточных чисел.

      Решение: calculator.cpp

    Алгоритмы: теория и практика. Структуры данных.

    Раздел 1. Базовые структуры данных.


    • Задача 1.1. Расстановка скобок в коде.

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

      Решение: placing_pare_theses_in_the_code.cpp

    • Задача 1.2. Высота дерева.

      Вычислить высоту данного дерева.

      Решение: height_of_the_tree.cpp

    • Задача 1.3. Симуляция обработки сетевых пакетов.

      Реализовать обработчик сетевых пакетов.

      Решение: simulation_of_network_packet_processing.cpp

    • Задача 1.4. Стек с поддержкой максимума.

      Реализовать стек с поддержкой операций push, pop и max.

      Решение: stack_with_maximum_support.cpp

    • Задача 1.5. Максимум в скользящем окне.

      Найти максимум в каждом окне размера m данного массива чисел A[1 … n].

      Решение: maximum_in_the_sliding_window.cpp

    Раздел 2. Очереди с приоритетом и системы непересекающихся множеств.


    • Задача 2.1. Построение кучи.

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

      Решение: creating_a_heap.cpp

    • Задача 2.2. Параллельная обработка.

      По данным n процессорам и m задач определите, для каждой из задач, каким процессором она будет обработана.

      Решение: parallel_processing.cpp

    • Задача 2.3. Объединение таблиц.

      Ваша цель в данной задаче — реализовать симуляцию объединения таблиц в базе данных. В базе данных есть n таблиц, пронумерованных от 1 до n, над одним и тем же множеством столбцов (атрибутов). Каждая таблица содержит либо реальные записи в таблице, либо символьную ссылку на другую таблицу. Изначально все таблицы содержат реальные записи, и i-я таблица содержит ri записей. Ваша цель — обработать m запросов типа (destinationi, sourcei).

      Решение: merging_tables.cpp

    • Задача 2.4. Автоматический анализ программ.

      Проверить, можно ли присвоить переменным целые значения, чтобы выполнить заданные равенства вида xi = xj и неравенства вида xp != xq.

      Решение: automatic_program_analysis.cpp

    Раздел 3. Хеш-таблицы.


    • Задача 3.1. Телефонная книга.

      Реализовать структуру данных, эффективно обрабатывающую запросы вида add number name, del number и find number.

      Решение: phone_book.cpp

    • Задача 3.2. Хеширование цепочками.

      Хеширование цепочками — один из наиболее популярных методов реализации хеш-таблиц на практике. Ваша цель в данной задаче — реализовать такую схему, используя таблицу с m ячейками и полиномиальной хеш-функцией на строках.

      Решение: chain_hashing.cpp

    • Задача 3.3. Поиск образца в тексте.

      Найти все вхождения строки Pattern в строку Text.

      Решение: search_for_a_sample_in_the_text.cpp

    Раздел 4. Деревья поиска.


    • Задача 4.1. Обход дерева.

      Построить in-order, pre-order и post-order обходы данного двоичного дерева.

      Решение: bypass_of_binary_tree.cpp

    • Задача 4.2. Проверка свойства дерева поиска.

      Проверить, является ли данное двоичное дерево деревом поиска.

      Решение: checking_the_properties_of_the_search_tree.cpp

    • Задача 4.3. Проверка свойства дерева поиска.

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

      Решение: checking_a_more_general_property_of_the_search_tree.cpp

    Описание

    Решение задач из курса по алгоритмам на платформе Stepik (Tasks and solutions from the Algorithm Course on the Stepik educational platform. C++ language.)

    Конвейеры
    0 успешных
    0 с ошибкой