Решение алгоритмических задач
Значения функции
Вася делает тест по математике: вычисляет значение функций в различных точках. Стоит отличная погода, и друзья зовут Васю гулять. Но мальчик решил сначала закончить тест и только после этого идти к друзьям. К сожалению, Вася пока не умеет программировать. Зато вы умеете. Помогите Васе написать код функции, вычисляющей y = ax2 + bx + c. Напишите программу, которая будет по коэффициентам a, b, c и числу x выводить значение функции в точке x.
На вход через пробел подаются целые числа a, x, b, c. В конце ввода находится перенос строки.
Выведите одно число — значение функции в точке x.
| Ввод | Вывод |
| -8 -5 -2 7 | -183 |
Чётные и нечётные числа
Представьте себе онлайн-игру для поездки в метро: игрок нажимает на кнопку, и на экране появляются три случайных числа. Если все три числа оказываются одной чётности, игрок выигрывает.
Напишите программу, которая по трём числам определяет, выиграл игрок или нет.
В первой строке записаны три случайных целых числа a, b и c. Числа не превосходят 10^9 по модулю.
Выведите «WIN», если игрок выиграл, и «FAIL» в противном случае.
| Ввод | Вывод |
| 1 2 -3 | FAIL |
Соседи
Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей. Соседним считается элемент, находящийся от текущего на одну ячейку влево, вправо, вверх или вниз. Диагональные элементы соседними не считаются.
Например, в матрице A соседними элементами для (0, 0) будут 2 и 0. А для (2, 1) –— 1, 2, 7, 7.
В первой строке задано n — количество строк матрицы. Во второй — количество столбцов m. Числа m и n не превосходят 1000. В следующих n строках задана матрица. Элементы матрицы — целые числа, по модулю не превосходящие 1000. В последних двух строках записаны координаты элемента, соседей которого нужно найти. Индексация начинается с нуля.
Напечатайте нужные числа в возрастающем порядке через пробел.
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 3 0 |
7 7 |
Хаотичность погоды
Метеорологическая служба вашего города решила исследовать погоду новым способом.
Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день. Под хаотичностью погоды за n дней служба понимает количество дней, в которые температура строго больше, чем в день до (если такой существует) и в день после текущего (если такой существует). Например, если за 5 дней максимальная температура воздуха составляла [1, 2, 5, 4, 8] градусов, то хаотичность за этот период равна 2: в 3-й и 5-й дни выполнялись описанные условия. Определите по ежедневным показаниям температуры хаотичность погоды за этот период.
Заметим, что если число показаний n=1, то единственный день будет хаотичным.
В первой строке дано число n –— длина периода измерений в днях, 1 ≤ n≤ 10^5. Во второй строке даны n целых чисел –— значения температуры в каждый из n дней. Значения температуры не превосходят 273 по модулю.
Выведите единственное число — хаотичность за данный период.
| Ввод | Вывод |
|
7 -1 -10 -8 0 2 0 5 |
3 |
Самое длинное слово
Чтобы подготовиться к семинару, Гоше надо прочитать статью по эффективному менеджменту. Так как Гоша хочет спланировать день заранее, ему необходимо оценить сложность статьи.
Он придумал такой метод оценки: берётся случайное предложение из текста и в нём ищется самое длинное слово. Его длина и будет условной сложностью статьи.
Помогите Гоше справиться с этой задачей.
В первой строке дана длина текста L (1 ≤ L ≤ 10^5).
В следующей строке записан текст, состоящий из строчных латинских букв и пробелов. Слово —– последовательность букв, не разделённых пробелами. Пробелы могут стоять в самом начале строки и в самом её конце. Текст заканчивается переносом строки, этот символ не включается в число остальных L символов.
В первой строке выведите самое длинное слово. Во второй строке выведите его длину. Если подходящих слов несколько, выведите то, которое встречается раньше.
| Ввод | Вывод |
|
19 i love segment tree |
3 |
Палиндром
Помогите Васе понять, будет ли фраза палиндромом. Учитываются только буквы и цифры, заглавные и строчные буквы считаются одинаковыми.
Решение должно работать за O(N), где N — длина строки на входе.
В единственной строке записана фраза или слово. Буквы могут быть только латинские. Длина текста не превосходит 20000 символов.
Фраза может состоять из строчных и прописных латинских букв, цифр, знаков препинания.
Выведите «True», если фраза является палиндромом, и «False», если не является.
| Ввод | Вывод |
| A man, a plan, a canal: Panama | True |
Работа из дома
Вася реализовал функцию, которая переводит целое число из десятичной системы в двоичную. Но, кажется, она получилась не очень оптимальной.
Попробуйте написать более эффективную программу.
Не используйте встроенные средства языка по переводу чисел в бинарное представление.
На вход подаётся целое число в диапазоне от 0 до 10000.
Выведите двоичное представление этого числа.
| Ввод | Вывод |
| 5 | 101 |
Двоичная система
Тимофей записал два числа в двоичной системе счисления и попросил Гошу вывести их сумму, также в двоичной системе. Встроенную в язык программирования возможность сложения двоичных чисел применять нельзя. Помогите Гоше решить задачу.
Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.
Два числа в двоичной системе счисления, каждое на отдельной строке. Длина каждого числа не превосходит 10 000 символов.
Одно число в двоичной системе счисления.
| Ввод | Вывод |
|
1010 1011 |
10101 |
Степень четырёх
Напишите программу, которая определяет, будет ли положительное целое число степенью четвёрки.
Подсказка: степенью четвёрки будут все числа вида 4n, где n – целое неотрицательное число.
На вход подаётся целое число в диапазоне от 1 до 10000.
Выведите «True», если число является степенью четырёх, «False» –— в обратном случае.
| Ввод | Вывод |
| 15 | False |
Факторизация
Основная теорема арифметики говорит: любое число раскладывается на произведение простых множителей единственным образом, с точностью до их перестановки. Например:
Число 8 можно представить как 2 × 2 × 2. Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта отличаются лишь порядком следования множителей. Разложение числа на простые множители называется факторизацией числа.
Напишите программу, которая производит факторизацию переданного числа.
В единственной строке дано число n (2 ≤ n ≤ 10^9), которое нужно факторизовать.
Выведите в порядке неубывания простые множители, на которые раскладывается число n.
| Ввод | Вывод |
| 8 | 2 2 2 |
Списочная форма
Вася просил Аллу помочь решить задачу. На этот раз по информатике.
Для неотрицательного целого числа X списочная форма –— это массив его цифр слева направо. К примеру, для 1231 списочная форма будет [1,2,3,1]. На вход подается количество цифр числа Х, списочная форма неотрицательного числа Х и неотрицательное число K. Числа К и Х не превосходят 10000.
Нужно вернуть списочную форму числа X + K.
В первой строке — длина списочной формы числа X. На следующей строке — сама списочная форма с цифрами записанными через пробел.
В последней строке записано число K, 0 ≤ K ≤ 10000.
Выведите списочную форму числа X+K.
| Ввод | Вывод |
|
4 1 2 0 0 34 |
1 2 3 4 |
Лишняя буква
Васе очень нравятся задачи про строки, поэтому он придумал свою. Есть 2 строки s и t, состоящие только из строчных букв. Строка t получена перемешиванием букв строки s и добавлением 1 буквы в случайную позицию. Нужно найти добавленную букву.
На вход подаются строки s и t, разделённые переносом строки. Длины строк не превосходят 1000 символов. Строки не бывают пустыми.
Выведите лишнюю букву.
| Ввод | Вывод |
|
abcd abcde |
e |
Ближайший ноль (Финальная)
Тимофей ищет место, чтобы построить себе дом. Улица, на которой он хочет жить, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. Каждый участок либо пустой, либо на нём уже построен дом.
Общительный Тимофей не хочет жить далеко от других людей на этой улице. Поэтому ему важно для каждого участка знать расстояние до ближайшего пустого участка. Если участок пустой, эта величина будет равна нулю — расстояние до самого себя.
Помогите Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.
В первой строке дана длина улицы —– n (1 ≤ n ≤ 10^6). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 10^9.
Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.
| Ввод | Вывод |
|
5 0 1 4 9 0 |
0 1 2 1 0 |
Ловкость рук (Финальная)
Игра «Тренажёр для скоростной печати» представляет собой поле из клавиш 4x4. В нём на каждом раунде появляется конфигурация цифр и точек. На клавише написана либо точка, либо цифра от 1 до 9.
В момент времени t игрок должен одновременно нажать на все клавиши, на которых написана цифра t. Гоша и Тимофей могут нажать в один момент времени на k клавиш каждый. Если в момент времени t нажаты все нужные клавиши, то игроки получают 1 балл.
Найдите число баллов, которое смогут заработать Гоша и Тимофей, если будут нажимать на клавиши вдвоём.
В первой строке дано целое число k (1 ≤ k ≤ 5).
В четырёх следующих строках задан вид тренажёра –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.
Выведите единственное число –— максимальное количество баллов, которое смогут набрать Гоша и Тимофей.
| Ввод | Вывод |
|
3 1231 2..2 2..2 2..2 |
2 |
Мониторинг
Алла получила задание, связанное с мониторингом работы различных серверов. Требуется понять, сколько времени обрабатываются определённые запросы на конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца соответствуют идентификатору запроса, а номер строки — идентификатору сервера. Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей исправить баг.
Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.
Транспонированная матрица получается из исходной заменой строк на столбцы.
Например, для матрицы А (слева) транспонированной будет следующая матрица (справа):
В первой строке задано число n — количество строк матрицы. Во второй строке задано m — число столбцов, m и n не превосходят 1000. В следующих n строках задана матрица. Числа в ней не превосходят по модулю 1000.
Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 |
1 0 7 2 2 2 4 7 3 6 1 0 |
Список дел
Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и печатает его элементы. Ниже дано описание структуры, которая задаёт узел списка.
В качестве ответа сдайте только код функции, которая печатает элементы списка. Длина списка не превосходит 5000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
Функция должна напечатать элементы списка по одному в строке.
Нелюбимое дело
Вася размышляет, что ему можно не делать из того списка дел, который он составил. Но, кажется, все пункты очень важные! Вася решает загадать число и удалить дело, которое идёт под этим номером. Список дел представлен в виде односвязного списка. Напишите функцию solution, которая принимает на вход голову списка и номер удаляемого дела и возвращает голову обновлённого списка. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и номер удаляемого элемента и возвращает голову обновлённого списка.
Функция принимает голову списка и индекс элемента, который надо удалить (нумерация с нуля). Список содержит не более 5000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
Верните голову списка, в котором удален нужный элемент.
Нелюбимое дело
Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей: напишите функцию solution, определяющую индекс первого вхождения передаваемого ей на вход значения в связном списке, если значение присутствует. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и искомый элемент, а возвращает целое число — индекс найденного элемента или -1.
Функция на вход принимает голову односвязного списка и элемент, который нужно найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
Функция возвращает индекс первого вхождения искомого элемента в список(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.
Всё наоборот
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список в обратном порядке. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову двусвязного списка и возвращает голову перевёрнутого списка. Ниже дано описание структуры, которая задаёт вершину списка.
Функция принимает на вход единственный аргумент — голову двусвязного списка. Длина списка не превосходит 1000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
Функция должна вернуть голову развернутого списка.
Всё наоборот
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список в обратном порядке. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову двусвязного списка и возвращает голову перевёрнутого списка. Ниже дано описание структуры, которая задаёт вершину списка.
Функция принимает на вход единственный аргумент — голову двусвязного списка. Длина списка не превосходит 1000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:
По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен. Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования. Для Java файл должен называться Solution.java, для C# – Solution.cs Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже). Для Go укажите package main.
Функция должна вернуть голову развернутого списка.
Стек - Max
Нужно реализовать класс StackMax, который поддерживает операцию определения максимума среди всех элементов в стеке. Класс должен поддерживать операции push(x), где x – целое число, pop() и get_max().
В первой строке записано одно число n — количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:
push(x) — добавить число x в стек; pop() — удалить число с вершины стека; get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max() нужно напечатать «None», для команды pop() — «error».
Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».
| Ввод | Вывод |
|
8 get_max push 7 pop push -2 push -1 pop get_max get_max |
None -2 -2 |
Стек - MaxEffective
Реализуйте класс StackMaxEffective, поддерживающий операцию определения максимума среди элементов в стеке. Сложность операции должна быть O(1). Для пустого стека операция должна возвращать None. При этом push(x) и pop() также должны выполняться за константное время.
В первой строке записано одно число — количество команд, оно не превосходит 100000. Далее идут команды по одной в строке. Команды могут быть следующих видов:
push(x) — добавить число x в стек; pop() — удалить число с вершины стека; get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max нужно напечатать «None», для команды pop — «error».
Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».
| Ввод | Вывод |
|
10 pop pop push 4 push -5 push 7 pop pop get_max pop get_max |
error error 4 None |
Скобочная последовательность
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
пустая строка —– правильная скобочная последовательность; правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность; правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная. На вход подаётся последовательность из скобок трёх видов: [], (), {}. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.
Выведите «True» или «False».
| Ввод | Вывод |
| {[()]} | True |
Ограниченная очередь
Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди.
Помогите ему —– реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо поддержать, описаны в формате ввода.
В первой строке записано одно число — количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:
push(x) — добавить число x в очередь; pop() — удалить число из очереди и вывести на печать; peek() — напечатать первое число в очереди; size() — вернуть размер очереди; При превышении допустимого размера очереди нужно вывести «error». При вызове операций pop() или peek() для пустой очереди нужно вывести «None».
Напечатайте результаты выполнения нужных команд, по одному на строке.
| Ввод | Вывод |
|
8 2 peek push 5 push 2 peek size size push 1 size |
None 5 2 2 error 2 |
Списочная очередь
Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:
get() — вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести «error». put(x) — добавить число x в очередь size() — вывести текущий размер очереди
В первой строке записано количество команд n — целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.
Выведите ответ на каждый запрос по одному в строке.
| Ввод | Вывод |
|
10 put -34 put -23 get size get size get get put 80 size |
-34 1 -23 0 error error 1 |
Рекурсивные числа Фибоначчи
У Тимофея было n стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту. Пусть F i —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Тогда выполняется следующее: F0=F1=1. Для всех i ≥ 2 выполнено F i = Fi−1+Fi−2. Определите, сколько кода напишет следующий стажёр –— найдите Fn Решение должно быть реализовано рекурсивно.
На вход подаётся n — целое число в диапазоне от 0 до 32.
Нужно вывести Fn.
| Ввод | Вывод |
| 3 | 3 |
Фибоначчи по модулю
У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 10^6) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными — они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i≥ 2 выполнено Fi=Fi−1+Fi−2.
Определите, сколько кода напишет следующий стажёр –— найдите последние k цифр числа Fn.
Как найти k последних цифр
Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток от его деления на число 10k. Эта операция обозначается как x mod 10k. Узнайте, как записывается операция взятия остатка по модулю в вашем языке программирования.
Также обратите внимание на возможное переполнение целочисленных типов, если в вашем языке такое случается.
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 10^6) и k (1 ≤ k ≤ 8).
Выведите единственное число – последние k цифр числа Fn.
Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
| Ввод | Вывод |
| 3 1 | 3 |
Дек (финальная)
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.
Внимание: при реализации используйте кольцевой буфер.
В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:
push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error». push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error». pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error». pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error». Value — целое число, по модулю не превосходящее 1000.
Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.
| Ввод | Вывод |
|
4 4 push_front 861 push_front -819 pop_back pop_back |
861 -819 |
Калькулятор (финальная)
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример 1: 3 4 + означает 3 + 4 и равно 7
Пример 2: 12 5 / Так как деление целочисленное, то в результате получим 2.
Пример 3: 10 2 4 * - означает 10 - 2 * 4 и равно 2
Разберём последний пример подробнее:
Знак * стоит сразу после чисел 2 и 4, значит к ним нужно применить операцию, которую этот знак обозначает, то есть перемножить эти два числа. В результате получим 8.
После этого выражение приобретёт вид:
10 8 -
Операцию «минус» нужно применить к двум идущим перед ней числам, то есть 10 и 8. В итоге получаем 2.
Рассмотрим алгоритм более подробно. Для его реализации будем использовать стек.
Для вычисления значения выражения, записанного в обратной польской нотации, нужно считывать выражение слева направо и придерживаться следующих шагов:
Обработка входного символа: Если на вход подан операнд, он помещается на вершину стека. Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека. Если входной набор символов обработан не полностью, перейти к шагу 1. После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент. Замечание про отрицательные числа и деление: в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.
Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.
В текущей задаче гарантируется, что деления на отрицательное число нет.
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.
На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.
Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
Выведите единственное число — значение выражения.
| Ввод | Вывод |
| 2 1 + 3 * | 9 |
Генератор скобок
Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
(()) ()() (()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
На вход функция принимает n — целое число от 0 до 10.
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
| Ввод | Вывод |
| 3 |
((())) (()()) (())() ()(()) ()()() |
Комбинации
На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так:
2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'
Вам известно в каком порядке были нажаты кнопки телефона, без учета повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.
На вход подается строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.
Выведите все возможные комбинации букв через пробел.
| Ввод | Вывод |
| 23 | ad ae af bd be bf cd ce cf |
Подпоследовательность
Гоша любит играть в игру «Подпоследовательность»: даны 2 строки, и нужно понять, является ли первая из них подпоследовательностью второй. Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.
В первой строке записана строка s.
Во второй —- строка t.
Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки не могут быть пустыми.
Выведите True, если s является подпоследовательностью t, иначе —– False.
| Ввод | Вывод |
|
abc ahbgdcu |
True |
Печеньки
К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.
Но не всё так просто. Печенья могут быть разного размера. А у каждого ребёнка есть фактор жадности —– минимальный размер печенья, которое он возьмёт. Нужно выяснить, сколько ребят останутся довольными в лучшем случае, когда они действуют оптимально.
Каждый ребёнок может взять не больше одного печенья.
В первой строке записано n —– количество детей.
Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.
В следующей строке записано число m –— количество печенек.
Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.
Оба числа n и m не превосходят 10000.
Нужно вывести одно число –— количество детей, которые останутся довольными
| Ввод | Вывод |
|
2 1 2 3 2 1 3 |
2 |
Гардероб
Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом —– жёлтого, и в конце —– малинового. Помогите Рите справиться с этой задачей.
Примечание: попробуйте решить задачу за один проход по массиву!
В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.
Нужно вывести в строку через пробел цвета предметов в правильном порядке.
| Ввод | Вывод |
|
7 0 2 1 2 0 0 1 |
0 0 0 1 1 2 2 |
Большое число
Вечером ребята решили поиграть в игру «Большое число». Даны числа. Нужно определить, какое самое большое число можно из них составить.
В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
Нужно вывести самое большое число, которое можно составить из данных чисел.
| Ввод | Вывод |
|
3 15 56 2 |
56215 |
Сортировка слиянием
Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.
Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 10^9. Длина сортируемого диапазона не превосходит 10^5.
При написании и отправке решений соблюдайте следующие правила: Отправляйте решение в виде файла. Если текст решения будет вставлен в форму, то будет возвращена ошибка. В качестве компилятора выберите Make. На Java назовите файл с решением Solution.java и реализуйте внутри класса указанные функции, для C# – Solution.cs Для остальных решений не используйте в качестве имени файла слово solution Укажите правильное разрешение для файла (.cpp, .java, .go. .js, .py). Для решений на C++ разрешение .h не поддерживается.
Клумбы
Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанам. На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. Для ландшафтных работ было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. Нужно определить границы будущих клумб. Пример 1: Два одинаковых отрезка [7,8] и [7,8] сливаются в один, но потом их накрывает отрезок[6, 10]. Таким образом, имеем две клумбы с координатами[2, 3]и[6, 10].
В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
Нужно вывести самое большое число, которое можно составить из данных чисел.
| Ввод | Вывод |
|
4 7 8 7 8 2 3 6 10 |
56215 |
Поиск в сломанном массиве (финальная)
Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее, нужно обеспечить возможность находить в нем элемент за O(logn). Можно предполагать, что в массиве только уникальные элементы. Задачу необходимо сдавать с компилятором Make, он выбран по умолчанию, других компиляторов в задаче нет. Решение отправляется файлом. Требуемые сигнатуры функций лежат в заготовках кода на диске.
От вас требуется реализовать функцию, осуществляющую поиск в сломанном массиве. Файлы с заготовками кода, содержащими сигнатуры функций и базовый тест для поддерживаемых языков, находятся на Яндекс.Диске по ссылке. Обратите внимание, что считывать данные и выводить ответ не требуется. Расширение файла должно соответствовать языку, на котором вы пишете (.cpp, .java, .go, .js, .py). Если вы пишете на Java, назовите файл с решением Solution.java, для C# – Solution.cs. Для остальных языков название может быть любым, кроме solution.ext, где ext – разрешение для вашего языка.
Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000. В примерах: В первой строке записано число n –— длина массива. Во второй строке записано положительное число k –— искомый элемент. Далее в строку через пробел записано n натуральных чисел – элементы массива.
Функция должна вернуть индекс элемента, равного k , если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть − 1. Изменять массив нельзя. Для отсечения неэффективных решений ваша функция будет запускаться от 100000 до 1000000 раз.
| Ввод | Вывод |
|
9 5 19 21 100 101 1 4 5 7 12 |
56215 |
Эффективная быстрая сортировка (финальная)
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач Pi и размер штрафа Fi. Штраф начисляется за неудачные попытки и время, затраченное на задачу.
Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.
Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").
Как работает in-place quick sort Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.
Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.
Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся. На рисунке представлен пример разделения при pivot=5. Указатель left — голубой, right — оранжевый.
В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами:
уникальным логином (строкой из маленьких латинских букв длиной не более 20) числом решённых задач Pi штрафом Fi Fi и Pi — целые числа, лежащие в диапазоне от 0 до 10^9.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|
5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
Полиномиальный хеш
Алле очень понравился алгоритм вычисления полиномиального хеша. Помогите ей написать функцию, вычисляющую хеш строки s. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
Полиномиальный хеш считается по формуле: ...
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.
Во второй строке дано число m (1 ≤ m ≤ 10^9) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 10^6), состоящая из больших и маленьких латинских букв.
Выведите целое неотрицательное число –— хеш заданной строки.
| Ввод | Вывод |
|
123 100003 a |
97 |
Сломай меня
Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было.
В этой задаче вам надо будет лишь найти две различные строки, которые для заданной хеш-функции будут давать одинаковое значение.
Гоша использует следующую хеш-функцию:
для a = 1000 и m = 123 987 123. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В задаче единственный тест без ввода
Отправьте две строки, по одной в строке. Строки могут состоять только из маленьких латинских букв и не должны превышать в длину 1000 знаков каждая. Код отправлять не требуется. Строки из примера использовать нельзя.
Пример вывода:
ezhgeljkablzwnvuwqvp
gbpdcvkumyfxillgnqrv
Кружки
В компании, где работает Тимофей, заботятся о досуге сотрудников и устраивают различные кружки по интересам. Когда кто-то записывается на занятие, в лог вносится название кружка.
По записям в логе составьте список всех кружков, в которые ходит хотя бы один человек.
В первой строке даётся натуральное число n, не превосходящее 10 000 –— количество записей в логе.
В следующих n строках —– названия кружков.
Выведите уникальные названия кружков по одному на строке, в порядке появления во входных данных.
| Ввод | Вывод |
|
8
вышивание крестиком рисование мелками на парте настольный керлинг настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение таракановедение |
вышивание крестиком рисование мелками на парте настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение |
Подстроки
На вход подается строка. Нужно определить длину наибольшей подстроки, которая не содержит повторяющиеся символы.
Одна строка, состоящая из строчных латинских букв. Длина строки не превосходит 10 000.
Выведите натуральное число —– ответ на задачу.
| Ввод | Вывод |
| abcabcbb | 3 |
Анаграммная группировка
Вася решил избавиться от проблем с произношением и стать певцом. Он обратился за помощью к логопеду. Тот посоветовал Васе выполнять упражнение, которое называется анаграммная группировка. В качестве подготовительного этапа нужно выбрать из множества строк анаграммы.
Анаграммы –— это строки, которые получаются друг из друга перестановкой символов. Например, строки «SILENT» и «LISTEN» являются анаграммами.
Помогите Васе найти анаграммы.
В первой строке записано число n —– количество строк.
Далее в строку через пробел записаны n строк.
n не превосходит 6000. Длина каждой строки не более 100 символов.
Нужно вывести в отсортированном порядке индексы строк, которые являются анаграммами.
Каждая группа индексов должна быть выведена в отдельной строке. Индексы внутри одной группы должны быть отсортированы по возрастанию. Группы между собой должны быть отсортированы по возрастанию первого индекса.
Обратите внимание, что группа анаграмм может состоять и из одной строки. Например, если в исходном наборе нет анаграмм, то надо вывести n групп, каждая из которых состоит из одного индекса.
| Ввод | Вывод |
|
6 tan eat tea ate nat bat |
0 4 1 2 3 5 |
Странное сравнение
Жители Алгосского архипелага придумали новый способ сравнения строк. Две строки считаются равными, если символы одной из них можно заменить на символы другой так, что первая строка станет точной копией второй строки. При этом необходимо соблюдение двух условий:
Порядок вхождения символов должен быть сохранён. Одинаковым символам первой строки должны соответствовать одинаковые символы второй строки. Разным символам —– разные. Например, если строка s = «abacaba», то ей будет равна строка t = «xhxixhx», так как все вхождения «a» заменены на «x», «b» –— на «h», а «c» –— на «i». Если же первая строка s=«abc», а вторая t=«aaa», то строки уже не будут равны, так как разные буквы первой строки соответствуют одинаковым буквам второй.
В первой строке записана строка s, во второй –— строка t. Длины обеих строк не превосходят 10^6. Обе строки содержат хотя бы по одному символу и состоят только из маленьких латинских букв.
Строки могут быть разной длины.
Выведите «YES», если строки равны (согласно вышеописанным правилам), и «NO» в ином случае.
| Ввод | Вывод |
|
mxyskaoghi qodfrgmslc |
YES |
Сумма четвёрок
У Гоши есть любимое число S. Помогите ему найти все уникальные четвёрки чисел в массиве, которые в сумме дают заданное число S.
В первой строке дано общее количество элементов массива n (0 ≤ n ≤ 1000).
Во второй строке дано целое число S .
В третьей строке задан сам массив. Каждое число является целым и не превосходит по модулю 10^9.
В первой строке выведите количество найденных четвёрок чисел.
В последующих строках выведите найденные четвёрки. Числа внутри одной четверки должны быть упорядочены по возрастанию. Между собой четвёрки упорядочены лексикографически.
| Ввод | Вывод |
|
8 10 2 3 2 4 1 10 3 0 |
3
0 3 3 4 1 2 3 4 2 2 3 3 |
Поисковая система (Финальная)
В этой задаче можно пользоваться хеш-таблицами из стандартных библиотек.
Тимофей пишет свою поисковую систему.
Имеется n документов, каждый из которых представляет собой текст из слов. По этим документам требуется построить поисковый индекс. На вход системе будут подаваться запросы. Запрос —– некоторый набор слов. По запросу надо вывести 5 самых релевантных документов.
Релевантность документа оценивается следующим образом: для каждого уникального слова из запроса берётся число его вхождений в документ, полученные числа для всех слов из запроса суммируются. Итоговая сумма и является релевантностью документа. Чем больше сумма, тем больше документ подходит под запрос.
Сортировка документов на выдаче производится по убыванию релевантности. Если релевантности документов совпадают —– то по возрастанию их порядковых номеров в базе (то есть во входных данных).
Подумайте над случаями, когда запросы состоят из слов, встречающихся в малом количестве документов. Что если одно слово много раз встречается в одном документе?
В первой строке дано натуральное число n —– количество документов в базе (1 ≤ n ≤ 10^4).
Далее в n строках даны документы по одному в строке. Каждый документ состоит из нескольких слов, слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Длина одного текста не превосходит 1000 символов. Текст не бывает пустым.
В следующей строке дано число запросов —– натуральное число m (1 ≤ m ≤ 10^4). В следующих m строках даны запросы по одному в строке. Каждый запрос состоит из одного или нескольких слов. Запрос не бывает пустым. Слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Число символов в запросе не превосходит 100.
Для каждого запроса выведите на одной строке номера пяти самых релевантных документов. Если нашлось менее пяти документов, то выведите столько, сколько нашлось. Документы с релевантностью 0 выдавать не нужно.
| Ввод | Вывод |
|
3 i love coffee coffee with milk and sugar free tea for everyone 3 i like black coffee without milk everyone loves new year mary likes black coffee without milk |
1 2 3 2 1 |
Хеш-таблица (Финальная)
Тимофей, как хороший руководитель, хранит информацию о зарплатах своих сотрудников в базе данных и постоянно её обновляет. Он поручил вам написать реализацию хеш-таблицы, чтобы хранить в ней базу данных с зарплатами сотрудников.
Хеш-таблица должна поддерживать следующие операции:
put key value —– добавление пары ключ-значение. Если заданный ключ уже есть в таблице, то соответствующее ему значение обновляется. get key –— получение значения по ключу. Если ключа нет в таблице, то вывести «None». Иначе вывести найденное значение. delete key –— удаление ключа из таблицы. Если такого ключа нет, то вывести «None», иначе вывести хранимое по данному ключу значение и удалить ключ. В таблице хранятся уникальные ключи.
Требования к реализации:
Нельзя использовать имеющиеся в языках программирования реализации хеш-таблиц (std::unordered_map в С++, dict в Python, HashMap в Java, и т. д.) Разрешать коллизии следует с помощью метода цепочек или с помощью открытой адресации. Все операции должны выполняться за O(1) в среднем. Поддерживать рехеширование и масштабирование хеш-таблицы не требуется. Ключи и значения, id сотрудников и их зарплата, —– целые числа. Поддерживать произвольные хешируемые типы не требуется.
В первой строке задано общее число запросов к таблице n (1≤ n≤ 10^6).
В следующих n строках записаны запросы, которые бывают трех видов –— get, put, delete —– как описано в условии.
Все ключи и значения –— целые неотрицательные числа, не превосходящие 10^9.
При любой последовательности команд, количество ключей в хеш-таблице не может превышать 10^5.
На каждый запрос вида get и delete выведите ответ на него в отдельной строке.
| Ввод | Вывод |
|
10 get 1 put 1 10 put 2 4 get 1 get 2 delete 2 get 2 put 1 5 get 1 delete 2 |
None 10 4 4 None 5 None |
Лампочки
Гоша повесил на стену гирлянду в виде бинарного дерева, в узлах которого находятся лампочки. У каждой лампочки есть своя яркость. Уровень яркости лампочки соответствует числу, расположенному в узле дерева. Помогите Гоше найти самую яркую лампочку в гирлянде, то есть такую, у которой яркость наибольшая.
На вход подается корень дерева. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.
Функция должна вернуть максимальное значение яркости в узле дерева.
Сбалансированное дерево
Гоше очень понравилось слушать рассказ Тимофея про деревья. Особенно часть про сбалансированные деревья. Он решил написать функцию, которая определяет, сбалансировано ли дерево. Дерево считается сбалансированным, если левое и правое поддеревья каждой вершины отличаются по высоте не больше, чем на единицу.
На вход функции подаётся корень бинарного дерева. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.
Функция должна вернуть True, если дерево сбалансировано в соответствии с критерием из условия, иначе - False.
Дерево поиска
Гоша понял, что такое дерево поиска, и захотел написать функцию, которая определяет, является ли заданное дерево деревом поиска. Значения в левом поддереве должны быть строго меньше, в правом —- строго больше значения в узле. Помогите Гоше с реализацией этого алгоритма.
На вход функции подается корень бинарного дерева. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.
Функция должна вернуть True, если дерево является деревом поиска, иначе - False.
Разные деревья поиска
Ребятам стало интересно, сколько может быть различных деревьев поиска, содержащих в своих узлах все уникальные числа от 1 до n. Помогите им найти ответ на этот вопрос.
В единственной строке задано число n. Оно не превосходит 20.
Нужно вывести число, равное количеству различных деревьев поиска, в узлах которых могут быть размещены числа от 1 до n включительно.
| Ввод | Вывод |
| 3 | 5 |
Добавь узел
Дано BST. Надо вставить узел с заданным ключом. Ключи в дереве могут повторяться. На вход функции подаётся корень корректного бинарного дерева поиска и ключ, который надо вставить в дерево. Осуществите вставку этого ключа. Если ключ уже есть в дереве, то его дубликаты уходят в правого сына. Таким образом вид дерева после вставки определяется однозначно. Функция должна вернуть корень дерева после вставки вершины. Ваше решение должно работать за O(h), где h –— высота дерева. На рисунках ниже даны два примера вставки вершин в дерево.
Ключи дерева – натуральные числа, не превосходящие 10^9. Число вершин в дереве не превосходит 10^5. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение. Ниже приведены сигнатуры функций, которые надо реализовать.
Выведи диапазон
Напишите функцию, которая будет выводить по неубыванию все ключи от L до R включительно в заданном бинарном дереве поиска. Ключи в дереве могут повторяться. Решение должно иметь сложность O(h+k), где h –— глубина дерева, k — число элементов в ответе. В данной задаче если в узле содержится ключ x, то другие ключи, равные x, могут быть как в правом, так и в левом поддереве данного узла. (Дерево строил стажёр, так что ничего страшного).
На вход функции подаётся корень дерева и искомый ключ. Число вершин в дереве не превосходит 10^5. Ключи – натуральные числа, не превосходящие 10^9. Гарантируется, что L ≤ R. В итоговом решении не надо определять свою структуру / свой класс, описывающий вершину дерева. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.й
Функция должна напечатать по неубыванию все ключи от L до R по одному в строке.
Просеивание вниз
Напишите функцию, совершающую просеивание вниз в куче на максимум. Гарантируется, что порядок элементов в куче может быть нарушен только элементом, от которого запускается просеивание. Функция принимает в качестве аргументов массив, в котором хранятся элементы кучи, и индекс элемента, от которого надо сделать просеивание вниз. Функция должна вернуть индекс, на котором элемент оказался после просеивания. Также необходимо изменить порядок элементов в переданном в функцию массиве. Индексация в массиве, содержащем кучу, начинается с единицы. Таким образом, сыновья вершины на позиции v это 2v и 2v+1. Обратите внимание, что нулевой элемент в передаваемом массиве фиктивный, вершина кучи соответствует 1-му элементу.
Элементы кучи —– целые числа, лежащие в диапазоне от − 10^9 до 10^9. Все элементы кучи уникальны. Передаваемый в функцию индекс лежит в диапазоне от 1 до размера передаваемого массива. В куче содержится от 1 до 10^5 элементов. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.
Просеивание вверх
Напишите функцию, совершающую просеивание вверх в куче на максимум. Гарантируется, что порядок элементов в куче может быть нарушен только элементом, от которого запускается просеивание. Функция принимает в качестве аргументов массив, в котором хранятся элементы кучи, и индекс элемента, от которого надо сделать просеивание вверх. Функция должна вернуть индекс, на котором элемент оказался после просеивания. Также необходимо изменить порядок элементов в переданном в функцию массиве. Индексация в массиве, содержащем кучу, начинается с единицы. Таким образом, сыновья вершины на позиции v это 2v и 2v+1. Обратите внимание, что нулевой элемент в передаваемом массиве фиктивный, вершина кучи соответствует 1-му элементу.
Элементы кучи —– целые числа, лежащие в диапазоне от − 10^9 до 10^9. Все элементы кучи уникальны. Передаваемый в функцию индекс лежит в диапазоне от 1 до размера передаваемого массива. В куче содержится от 1 до 10^5 элементов. Замечания про отправку решений По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение.
Пирамидальная сортировка (Финальная)
В данной задаче необходимо реализовать сортировку кучей. При этом кучу необходимо реализовать самостоятельно, использовать имеющиеся в языке реализации нельзя. Сначала рекомендуется решить задачи про просеивание вниз и вверх.
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач Pi и размер штрафа Fi. Штраф начисляется за неудачные попытки и время, затраченное на задачу.
Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.
Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм сортировки кучей (англ. Heapsort) для таблицы результатов.
В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами:
- уникальным логином (строкой из маленьких латинских букв длиной не более 20)
- числом решённых задач Pi
- штрафом Fi
Fi и Pi — целые числа, лежащие в диапазоне от 0 до 10^9.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|
5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
Удали узел (Финальная)
Дано бинарное дерево поиска, в котором хранятся ключи. Ключи — уникальные целые числа. Найдите вершину с заданным ключом и удалите её из дерева так, чтобы дерево осталось корректным бинарным деревом поиска. Если ключа в дереве нет, то изменять дерево не надо. На вход вашей функции подаётся корень дерева и ключ, который надо удалить. Функция должна вернуть корень изменённого дерева. Сложность удаления узла должна составлять O(h), где h –— высота дерева. Создавать новые вершины (вдруг очень захочется) нельзя.
Ключи дерева – натуральные числа, не превышающие 10^9. В итоговом решении не надо определять свою структуру/свой класс, описывающий вершину дерева. Используйте заготовки кода для данной задачи, расположенные по ссылкам:
По умолчанию выбран компилятор Make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение. Ниже приведены сигнатуры функций, которые надо реализовать.
Построить список смежности
Алла пошла на стажировку в студию графического дизайна, где ей дали такое задание: для очень большого числа ориентированных графов преобразовать их список рёбер в список смежности. Чтобы побыстрее решить эту задачу, она решила автоматизировать процесс.
Помогите Алле написать программу, которая по списку рёбер графа будет строить его список смежности.
В первой строке дано число вершин n (1 ≤ n ≤ 100) и число ребер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.
Выведите информацию о рёбрах, исходящих из каждой вершины.
В строке i надо написать число рёбер, исходящих из вершины i, а затем перечислить вершины, в которые ведут эти рёбра –— в порядке возрастания их номеров.
| Ввод | Вывод |
|
5 3 1 3 2 3 5 2 |
1 3 1 3 0 0 1 2 |
Перевести список ребер в матрицу смежности
Алла успешно справилась с предыдущим заданием, и теперь ей дали новое. На этот раз список рёбер ориентированного графа надо переводить в матрицу смежности. Конечно же, Алла попросила вас помочь написать программу для этого.
В первой строке дано число вершин n (1 ≤ n ≤ 100) и число рёбер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.
Выведите матрицу смежности n на n. На пересечении i-й строки и j-го столбца стоит единица, если есть ребро, ведущее из i в j.
| Ввод | Вывод |
|
5 3 1 3 2 3 5 2 |
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 |
DFS
Задан неориентированный граф. Обойдите с помощью DFS все вершины, достижимые из заданной вершины s, и выведите их в порядке обхода, если начинать обход из s.
В первой строке дано количество вершин n (1 ≤ n ≤ 10^5) и рёбер m (0 ≤ m ≤ 10^5). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n). В графе нет петель и кратных рёбер.
Выведите вершины в порядке обхода, считая что при запуске от каждой конкретной вершины её соседи будут рассматриваться в порядке возрастания (то есть если вершина 2 соединена с 1 и 3, то сначала обход пойдёт в 1, а уже потом в 3).
| Ввод | Вывод |
|
4 4 3 2 4 3 1 4 1 2 3 |
3 2 1 4 |
Время выходить
Вам дан ориентированный граф. Известно, что все его вершины достижимы из вершины s=1. Найдите время входа и выхода при обходе в глубину, производя первый запуск из вершины s. Считайте, что время входа в стартовую вершину равно 0. Соседей каждой вершины обходите в порядке увеличения номеров.
В первой строке дано число вершин n (1 ≤ n ≤ 2⋅ 10^5) и рёбер (0 ≤ m ≤ 2 ⋅ 10^5). В каждой из следующих m строк записаны рёбра графа в виде пар (from, to), 1 ≤ from ≤ n — начало ребра, 1 ≤ to ≤ n — его конец. Гарантируется, что в графе нет петель и кратных рёбер.
Выведите n строк, в каждой из которых записана пара чисел tini, touti — время входа и выхода для вершины i.
| Ввод | Вывод |
|
6 8 2 6 1 6 3 1 2 5 4 3 3 2 1 2 1 4 |
0 11 1 6 8 9 7 10 2 3 4 5 |
Топологическая сортировка
Дан ациклический ориентированный граф (так называемый DAG, directed acyclic graph). Найдите его топологическую сортировку, то есть выведите его вершины в таком порядке, что все рёбра графа идут слева направо. У графа может быть несколько подходящих перестановок вершин. Вам надо найти любую топологическую сортировку.
В первой строке даны два числа – количество вершин n (1 ≤ n ≤ 10^5) и количество рёбер m (0 ≤ m ≤ 10^5). В каждой из следующих m строк описаны рёбра по одному на строке. Каждое ребро представлено парой вершин (from, to), 1≤ from, to ≤ n, соответственно номерами вершин начала и конца.
Выведите номера вершин в требуемом порядке.
| Ввод | Вывод |
|
5 3 3 2 3 4 2 5 |
1 3 2 4 5 |
Достопримечательности
Вы приехали на архипелаг Алгосы (наконец-то!). Здесь есть n достопримечательностей. Ваша лодка может высадить вас у одной из них, забрать у какой-то другой, возможно, той же самой достопримечательности и увезти на материк.
Чтобы более тщательно спланировать свой маршрут, вы хотите узнать расстояния между каждой парой достопримечательностей Алгосов. Некоторые из них соединены мостами, по которым вы можете передвигаться в любую сторону. Всего мостов m.
Есть вероятность, что карта архипелага устроена так, что нельзя добраться от какой-то одной достопримечательности до другой без использования лодки.
Найдите кратчайшие расстояния между всеми парами достопримечательностей.
В первой строке даны числа n (1 ≤ n ≤ 100) и m (0 ≤ m ≤ n (n-1)/2). В следующих m строках описаны мосты. Каждый мост задаётся номерами двух достопримечательностей 1 ≤ u, v ≤ n и длиной дороги 1 ≤ L ≤ 10^3.
Выведите матрицу n × n кратчайших расстояний. На пересечении i-й строки и j-го столбца должно стоять расстояние от i-й до j-й достопримечательности. Если между какой-то парой нет пути, то в соответствующей клетке поставьте -1.
| Ввод | Вывод |
|
4 4 1 2 1 2 3 3 3 4 5 1 4 2 |
0 1 4 2 1 0 3 3 4 3 0 5 2 3 5 0 |
Дорогая сеть (Финальная)
Тимофей решил соединить все компьютеры в своей компании в единую сеть. Для этого он придумал построить минимальное остовное дерево, чтобы эффективнее использовать ресурсы.
Но от начальства пришла новость о том, что выделенный на сеть бюджет оказался очень большим и его срочно надо израсходовать. Поэтому Тимофея теперь интересуют не минимальные, а максимальные остовные деревья.
Он поручил вам найти вес такого максимального остовного дерева в неориентированном графе, который задаёт схему офиса.
В первой строке дано количество вершин n и ребер m графа (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100000).
В каждой из следующих m строк заданы рёбра в виде троек чисел u, v, w. u и v — вершины, которые соединяет это ребро. w — его вес ( 1 ≤ u, v ≤ n, 0 ≤ w ≤ 10000). В графе могут быть петли и кратные ребра. Граф может оказаться несвязным.
Если максимальное остовное дерево существует, то выведите его вес. Иначе (если в графе несколько компонент связности) выведите фразу «Oops! I did it again».
| Ввод | Вывод |
|
4 4 1 2 5 1 3 6 2 4 8 3 4 3 |
19 |
Железные дороги (Финальная)
В стране X есть n городов, которым присвоены номера от 1 до n. Столица страны имеет номер n. Между городами проложены железные дороги.
Однако дороги могут быть двух типов по ширине полотна. Любой поезд может ездить только по одному типу полотна. Условно один тип дорог помечают как R, а другой как B. То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет по этому маршруту проехать. От одного города до другого можно проехать только по маршруту, состоящему исключительно из дорог типа R или только из дорог типа B.
Но это ещё не всё. По дорогам страны X можно двигаться только от города с меньшим номером к городу с большим номером. Это объясняет большой приток жителей в столицу, у которой номер n.
Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B. Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бОльшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя. Выясните, является ли данная вам карта оптимальной.
В первой строке дано число n (1 ≤ n ≤ 5000) — количество городов в стране. Далее задана карта железных дорог в следующем формате.
Карта задана n-1 строкой. В i-й строке описаны дороги из города i в города i+1, i+2, ..., n. В строке записано n - i символов, каждый из которых либо R, либо B. Если j-й символ строки i равен «B», то из города i в город i + j идет дорога типа «B». Аналогично для типа «R».
Выведите «YES», если карта оптимальна, и «NO» в противном случае.
| Ввод | Вывод |
|
3 RB R |
NO |
Биржа
Рита хочет попробовать поиграть на бирже. Но для начала она решила потренироваться на исторических данных.
Даны стоимости акций в каждый из n дней. В течение дня цена акции не меняется. Акции можно покупать и продавать, но только по одной штуке в день. В один день нельзя совершать более одной операции (покупки или продажи). Также на руках не может быть более одной акции в каждый момент времени.
Помогите Рите выяснить, какую максимальную прибыль она могла бы получить.
Пояснения к примерам
Пример 1 Рита может купить акцию во 2-й день за 1 франк.
Затем она продаст её на 3-й день за 5 франков.
В 4-й день она снова купит акцию за 3 франка.
На 5-й день Рита продаст эту акцию за 6 франков.
Прибыль составила (5 - 1) + (6 - 3) = 7 франков.
Пример 2 Рите выгодно купить акцию в самый первый день и продать в последний.
Пример 3 Рита покупает акции в дни с номерами 1, 3 и 5. Продаёт в дни 2, 4 и 6. Итоговая прибыль составит (12 - 1) + (16 - 12) + (8 - 1) = 22. Такой же результат можно получить в виде: 22 = (16 - 1) + (8 - 1), если покупать акции в дни 1 и 5, а продавать в дни 4 и 6.
В первой строке записано количество дней n —– целое число в диапазоне от 0 до 10 000.
Во второй строке через пробел записано n целых чисел в диапазоне от 0 до 1000 –— цены акций.
Выведите число, равное максимально возможной прибыли за эти дни.
| Ввод | Вывод |
|
6 7 1 5 3 6 4 |
7 |
Расписание
Дано количество учебных занятий, проходящих в одной аудитории. Для каждого из них указано время начала и конца. Нужно составить расписание, в соответствии с которым в классе можно будет провести как можно больше занятий.
Если возможно несколько оптимальных вариантов, то выведите любой. Возможно одновременное проведение более чем одного занятия нулевой длительности.
В первой строке задано число занятий. Оно не превосходит 1000. Далее для каждого занятия в отдельной строке записано время начала и конца, разделённые пробелом. Время задаётся одним целым числом h, если урок начинается/заканчивается ровно в h часов. Если же урок начинается/заканчивается в h часов m минут, то время записывается как h.m. Гарантируется, что каждое занятие начинается не позже, чем заканчивается. Указываются только значащие цифры.
Выведите в первой строке наибольшее число уроков, которое можно провести в аудитории. Далее выведите время начала и конца каждого урока в отдельной строке в порядке их проведения.
| Ввод | Вывод |
|
5 9 10 9.3 10.3 10 11 10.3 11.3 11 12 |
3 9 10 10 11 11 12 |
Золотая лихорадка
Гуляя по одному из островов Алгосского архипелага, Гоша набрёл на пещеру, в которой лежат кучи золотого песка. К счастью, у Гоши есть с собой рюкзак грузоподъёмностью до M килограмм, поэтому он может унести с собой какое-то ограниченное количество золота.
Всего золотых куч n штук, и все они разные. В куче под номером i содержится mi килограммов золотого песка, а стоимость одного килограмма — ci алгосских франков.
Помогите Гоше наполнить рюкзак так, чтобы общая стоимость золотого песка в пересчёте на алгосские франки была максимальной.
В первой строке задано целое число M — грузоподъёмность рюкзака Гоши (0 ≤ M ≤ 10^8).
Во второй строке дано количество куч с золотым песком — целое число n (1 ≤ n ≤ 10^5).
В каждой из следующих n строк описаны кучи: i-ая куча задаётся двумя целыми числами ci и mi, записанными через пробел (1 ≤ ci ≤ 10^7, 1 ≤ mi ≤ 10^8).
Выведите единственное число —– максимальную сумму (в алгосских франках), которую Гоша сможет вынести из пещеры в своём рюкзаке.
| Ввод | Вывод |
|
10 3 8 1 2 10 4 5 |
36 |
Прыжки по лестнице
Алла хочет доказать, что она умеет прыгать вверх по лестнице быстрее всех. На этот раз соревнования будут проходить на специальной прыгательной лестнице. С каждой её ступеньки можно прыгнуть вверх на любое расстояние от 1 до k. Число k придумывает Алла.
Гоша не хочет проиграть, поэтому просит вас посчитать количество способов допрыгать от первой ступеньки до n-й. Изначально все стоят на первой ступеньке.
В единственной строке даны два числа — n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n).
Выведите количество способов по модулю 10^9 + 7.
| Ввод | Вывод |
| 6 3 | 13 |
Банкомат
Тимофей пошёл снять деньги в банкомат. Ему нужно m франков. В банкомате в бесконечном количестве имеются купюры различных достоинств. Всего различных достоинств n. Купюр каждого достоинства можно взять бесконечно много. Нужно определить число способов, которыми Тимофей сможет набрать нужную сумму.
Пояснения к примерам:
Пример 1 5 франков можно набрать следующими способами: 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 3 1 + 2 + 2 2 + 3
Пример 2 Во втором примере всего две возможности набрать в сумме 3: 1 + 2 1 + 1 + 1
Пример 3 Набрать ровно 8 франков купюрами по 5 франков невозможно. Ответ равен нулю.
В первой строке записано целое число m — сумма, которую нужно набрать. Во второй строке n — количество монет в банкомате. Оба числа не превосходят 300. Далее в третьей строке записано n уникальных натуральных чисел, каждое в диапазоне от 1 до 1000 –– достоинства купюр.
Нужно вывести число способов, которым Тимофей сможет набрать нужную сумму.
| Ввод | Вывод |
|
5 3 3 2 1 |
5 |
Поле с цветочками
Черепаха Кондратина путешествует по клетчатому полю из n строк и m столбцов. В каждой клетке либо растёт цветочек, либо не растёт. Кондратине надо добраться из левого нижнего в правый верхний угол и собрать как можно больше цветочков.
Помогите ей с этой сложной задачей и определите, какое наибольшее число цветочков она сможет собрать при условии, что Кондратина умеет передвигаться только на одну клетку вверх или на одну клетку вправо за ход.
В первой строке даны размеры поля n и m (через пробел). Оба числа лежат в диапазоне от 1 до 1000. В следующих n строках задано поле. Каждая строка состоит из m символов 0 или 1, записанных подряд без пробелов, и завершается переводом строки. Если в клетке записана единица, то в ней растёт цветочек.
Выведите единственное число — максимальное количество цветочков, которое сможет собрать Кондратина.
| Ввод | Вывод |
|
2 3 101 110 |
3 |
Гороскопы
В мире последовательностей нет гороскопов. Поэтому когда две последовательности хотят понять, могут ли они счастливо жить вместе, они оценивают свою совместимость как длину их наибольшей общей подпоследовательности.
Подпоследовательность получается из последовательности удалением некоторого (возможно, нулевого) числа элементов. То есть элементы сохраняют свой относительный порядок, но не обязаны изначально идти подряд.
Найдите наибольшую общую подпоследовательность двух одиноких последовательностей и выведите её!
В первой строке дано число n — количество элементов в первой последовательности (1 ≤ n ≤ 1000). Во второй строке даны n чисел ai (0 ≤ |ai| ≤ 10^9) — элементы первой последовательности. Аналогично в третьей строке дано m (1 ≤ m ≤ 1000) — число элементов второй последовательности. В четвертой строке даны элементы второй последовательности через пробел bi (0 ≤ |bi| ≤ 10^9).
Сначала выведите длину найденной наибольшей общей подпоследовательности, во второй строке выведите индексы элементов первой последовательности, которые в ней участвуют, в третьей строке — индексы элементов второй последовательности. Нумерация индексов с единицы, индексы должны идти в корректном порядке.
Если возможных НОП несколько, то выведите любую.
| Ввод | Вывод |
|
5 4 9 2 4 6 7 9 4 0 0 2 8 4 |
3 1 3 4 2 5 7 |
Золото лепреконов
Лепреконы в данной задаче появились по соображениям общей морали, так как грабить банки — нехорошо.
Вам удалось заключить неплохую сделку с лепреконами, поэтому они пустили вас в своё хранилище золотых слитков. Все слитки имеют единую пробу, то есть стоимость 1 грамма золота в двух разных слитках одинакова. В хранилище есть n слитков, вес i-го слитка равен wi кг. У вас есть рюкзак, вместимость которого M килограмм.
Выясните максимальную суммарную массу золотых слитков, которую вы сможете унести.
В первой строке дано число слитков —– натуральное число n (1 ≤ n ≤ 1000) и вместимость рюкзака –— целое число M (0 ≤ M ≤ 10^4). Во второй строке записано n натуральных чисел wi (1 ≤ wi ≤ 10^4) -— массы слитков.
Выведите единственное число — максимальную массу, которую можно забрать с собой.
| Ввод | Вывод |
|
5 15 3 8 1 2 5 |
15 |
Расстояние по Левенштейну (Финальная)
Расстоянием Левенштейна между двумя строками s и t называется количество атомарных изменений, с помощью которых можно одну строку превратить в другую. Под атомарными изменениями подразумеваются: удаление одного символа, вставка одного символа, замена одного символа на другой.
Найдите расстояние Левенштейна для предложенной пары строк.
Выведите единственное число — расстояние между строками.
В первой строке дана строка s, во второй — строка t. Длины обеих строк не превосходят 1000. Строки состоят из маленьких латинских букв.
| Ввод | Вывод |
|
abacaba abaabc |
2 |
Одинаковые суммы (Финальная)
На Алгосах устроили турнир по настольному теннису. Гоша выиграл n партий, получив при этом некоторое количество очков за каждую из них.
Гоше стало интересно, можно ли разбить все заработанные им во время турнира очки на две части так, чтобы сумма в них была одинаковой.
В первой строке записано целое число n (0 ≤ n ≤ 300) –— количество выигранных партий.
Во второй строке через пробел записано n целых неотрицательных чисел, каждое из которых не превосходит 300 –— заработанные в партиях очки.
Нужно вывести True, если произвести такое разбиение возможно, иначе —– False
| Ввод | Вывод |
|
4 1 5 7 1 |
True |
Разворот строки
В некоторых языках предложения пишутся и читаются не слева направо, а справа налево.
Вам под руку попался странный текст –— в нём обычный (слева направо) порядок букв в словах. А вот сами слова идут в противоположном направлении. Вам надо преобразовать текст так, чтобы слова в нём были написаны слева направо.
На ввод подаётся строка, состоящая из слов, разделённых пробелами (один пробел между соседними словами). Всего слов не более 1000, длина каждого из них —– от 1 до 100 символов. Слова состоят из строчных букв английского алфавита.
Выведите строку с обратным порядком слов в ней.
| Ввод | Вывод |
| one two three | three two one |
Пограничный контроль
Представьте, что вы работаете пограничником и постоянно проверяете документы людей по записи из базы. При этом допустима ситуация, когда имя человека в базе отличается от имени в паспорте на одну замену, одно удаление или одну вставку символа. Если один вариант имени может быть получен из другого удалением одного символа, то человека пропустят через границу. А вот если есть какое-либо второе изменение, то человек грустно поедет домой или в посольство.
Например, если первый вариант —– это «Лена», а второй — «Лера», то девушку пропустят. Также человека пропустят, если в базе записано «Коля», а в паспорте — «оля».
Однако вариант, когда в базе числится «Иннокентий», а в паспорте написано «ннакентий», уже не сработает. Не пропустят также человека, у которого в паспорте записан «Иинннокентий», а вот «Инннокентий» спокойно пересечёт границу.
Напишите программу, которая сравнивает имя в базе с именем в паспорте и решает, пропускать человека или нет. В случае равенства двух строк — путешественника, естественно, пропускают.
В первой строке дано имя из паспорта.
Во второй строке —- имя из базы.
Обе строки состоят из строчных букв английского алфавита. Размер каждой строки не превосходит 100 000 символов.
Выведите «OK», если человека пропустят, или «FAIL» в противном случае.
| Ввод | Вывод |
|
abcdefg abdefg |
OK |
Вставка строк
У Риты была строка s, Гоша подарил ей на 8 марта ещё n других строк ti, 1≤ i≤ n. Теперь Рита думает, куда их лучше поставить. Один из вариантов —– расположить подаренные строки внутри имеющейся строки s, поставив строку ti сразу после символа строки s с номером ki (в частности, если ki=0, то строка вставляется в самое начало s).
Помогите Рите и определите, какая строка получится после вставки в s всех подаренных Гошей строк.
В первой строке дана строка s. Строка состоит из строчных букв английского алфавита, не бывает пустой и её длина не превышает 10^5 символов.
Во второй строке записано количество подаренных строк — натуральное число n, 1 ≤ n ≤ 10^5.
В каждой из следующих n строк через пробел записаны пары ti и ki. Строка ti состоит из маленьких латинских букв и не бывает пустой. ki — целое число, лежащее в диапазоне от 0 до |s|. Все числа ki уникальны. Гарантируется, что суммарная длина всех строк ti не превосходит 10^5.
Выведите получившуюся в результате вставок строку.
| Ввод | Вывод |
|
abacaba 3 queue 2 deque 0 stack 7 |
dequeabqueueacabastack |
Поиск со сдвигом
Гоша измерял температуру воздуха n дней подряд. В результате у него получился некоторый временной ряд. Теперь он хочет посмотреть, как часто встречается некоторый шаблон в получившейся последовательности. Однако температура — вещь относительная, поэтому Гоша решил, что при поиске шаблона длины m (a1, a2, ..., am) стоит также рассматривать сдвинутые на константу вхождения. Это значит, что если для некоторого числа c в исходной последовательности нашёлся участок вида (a1 + c, a2 + c, ... , am + c), то он тоже считается вхождением шаблона (a1, a2, ..., am).
По заданной последовательности измерений X и шаблону A=(a1, a2, ..., am) определите все вхождения A в X, допускающие сдвиг на константу.
Подсказка: если вы пишете на питоне и сталкиваетесь с TL, то попробуйте заменить какие-то из циклов операциями со срезами.
В первой строке дано количество сделанных измерений n — натуральное число, не превышающее 10^4. Во второй строке через пробел записаны n целых чисел xi, 0 ≤ xi ≤ 10^3 –— результаты измерений. В третьей строке дано натуральное число m –— длина искомого шаблона, 1≤ m ≤ n. В четвёртой строке даны m целых чисел ai — элементы шаблона, 0 ≤ ai ≤ 10^3.
Выведите через пробел в порядке возрастания все позиции, на которых начинаются вхождения шаблона A в последовательность X. Нумерация позиций начинается с единицы.
| Ввод | Вывод |
|
9 3 9 1 2 5 10 9 1 7 2 4 10 |
1 8 |
Сравнить две строки
Алла придумала новый способ сравнивать две строки: чтобы сравнить строки a и b, в них надо оставить только те буквы, которые в английском алфавите стоят на четных позициях. Затем полученные строки сравниваются по обычным правилам. Помогите Алле реализовать новое сравнение строк.
На вход подаются строки a и b по одной в строке. Обе строки состоят из маленьких латинских букв, не бывают пустыми и не превосходят 10^5 символов в длину.
Выведите -1, если a < b, 0, если a = b, и 1, если a > b.
| Ввод | Вывод |
|
gggggbbb bbef |
-1 |
Подсчёт префикс-функции
В этой задаче вам необходимо посчитать префикс-функцию для заданной строки.
На вход подаётся строка, состоящая из строчных латинских букв. Длина строки не превосходит 10^6.
Если длина входной строки L, то выведите через пробел L целых неотрицательных чисел —– массив значений префикс-функции исходной строки.
| Ввод | Вывод |
| abracadabra | 0 0 0 1 0 1 0 1 2 3 4 |
Packed Prefix (Финальная)
Вам даны строки в запакованном виде. Определим запакованную строку (ЗС) рекурсивно. Строка, состоящая только из строчных букв английского алфавита является ЗС. Если A и B —– корректные ЗС, то и AB является ЗС. Если A —– ЗС, а n — однозначное натуральное число, то n[A] тоже ЗС. При этом запись n[A] означает, что при распаковке строка A записывается подряд n раз. Найдите наибольший общий префикс распакованных строк и выведите его (в распакованном виде).
Иными словами, пусть сложение —– это конкатенация двух строк, а умножение строки на число — повтор строки соответствующее число раз. Пусть функция f умеет принимать ЗС и распаковывать её. Если ЗС D имеет вид D=AB, где A и B тоже ЗС, то f(D) = f(A) + f(B). Если D=n[A], то f(D) = f(A) × n.
В первой строке записано число n (1 ≤ n ≤ 1000) –— число строк.
Далее в n строках записаны запакованные строки. Гарантируется, что эти строки корректны, то есть удовлетворяют указанному рекурсивному определению. Длина строк после распаковки не превосходит 10^5.
Выведите наибольший общий префикс распакованных строк.
| Ввод | Вывод |
|
3 2[a]2[ab] 3[a]2[r2[t]] a2[aa3[b]] |
aaa |
Шпаргалка (Финальная)
Вася готовится к экзамену по алгоритмам и на всякий случай пишет шпаргалки.
Чтобы уместить на них как можно больше информации, он не разделяет слова пробелами. В итоге получается одна очень длинная строка. Чтобы на самом экзамене из-за нервов не запутаться в прочитанном, он просит вас написать программу, которая по этой длинной строке и набору допустимых слов определит, можно ли разбить текст на отдельные слова из набора.
Более формально: дан текст T и набор строк s1, ... ,sn. Надо определить, представим ли T как sk1sk2...skr, где где ki — индексы строк. Индексы могут повторяться. Строка si может встречаться в разбиении текста T произвольное число раз. Можно использовать не все строки для разбиения. Строки могут идти в любом порядке.
В первой строке дан текст T, который надо разбить на слова. Длина T не превосходит 10^5. Текст состоит из строчных букв английского алфавита.
Во второй строке записано число допустимых к использованию слов 1 ≤ n ≤ 100.
В последующих n строках даны сами слова, состоящие из маленьких латинских букв. Длина каждого слова не превосходит 100.
Выведите «YES», если текст можно разбить на слова из данного словаря, или «NO» в ином случае.
| Ввод | Вывод |
|
examiwillpasstheexam 5 will pass the exam i |
YES |