Решения задач из различных тренировок по алгоритмам.
Задачи разбиты на блоки, к каждому блоку приложены тесты, написанные на pytest.
A. Значения функции
Вася делает тест по математике: вычисляет значение функций в различных точках. Стоит отличная погода, и друзья зовут Васю гулять. Но мальчик решил сначала закончить тест и только после этого идти к друзьям. К сожалению, Вася пока не умеет программировать. Зато вы умеете. Помогите Васе написать код функции, вычисляющей y = a * x^2 + b * x + c. Напишите программу, которая будет по коэффициентам a, b, c и числу x выводить значение функции в точке x.
На вход через пробел подаются целые числа a, x, b, c. В конце ввода находится перенос строки.
Выведите одно число — значение функции в точке x.
| Ввод | Вывод |
|---|---|
| -8 -5 -2 7 | -183 |
| 8 2 9 -10 | 40 |
B. Чётные и нечётные числа
Представьте себе онлайн-игру для поездки в метро: игрок нажимает на кнопку, и на экране появляются три случайных числа. Если все три числа оказываются одной чётности, игрок выигрывает.
Напишите программу, которая по трём числам определяет, выиграл игрок или нет.
В первой строке записаны три случайных целых числа a, b и c. Числа не превосходят 10^9 по модулю.
Выведите «WIN», если игрок выиграл, и «FAIL» в противном случае.
| Ввод | Вывод |
|---|---|
| 1 2 -3 | FAIL |
| 7 11 7 | WIN |
| 6 -2 0 | WIN |
C. Соседи
Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей. Соседним считается элемент, находящийся от текущего на одну ячейку влево, вправо, вверх или вниз. Диагональные элементы соседними не считаются.
Например, в матрице 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 |
| 4 3 1 2 3 0 2 6 7 4 1 2 7 0 0 0 |
0 2 |
D. Хаотичность погоды
Метеорологическая служба вашего города решила исследовать погоду новым способом.
- Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день.
- Под хаотичностью погоды за 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 |
| 5 1 2 5 4 8 |
2 |
E. Самое длинное слово
Чтобы подготовиться к семинару, Гоше надо прочитать статью по эффективному менеджменту. Так как Гоша хочет спланировать день заранее, ему необходимо оценить сложность статьи.
Он придумал такой метод оценки: берётся случайное предложение из текста и в нём ищется самое длинное слово. Его длина и будет условной сложностью статьи.
Помогите Гоше справиться с этой задачей.
В первой строке дана длина текста L (1 ≤ L ≤ 10^5).
В следующей строке записан текст, состоящий из строчных латинских букв и пробелов. Слово —– последовательность букв, не разделённых пробелами. Пробелы могут стоять в самом начале строки и в самом её конце. Текст заканчивается переносом строки, этот символ не включается в число остальных L символов.
В первой строке выведите самое длинное слово. Во второй строке выведите его длину. Если подходящих слов несколько, выведите то, которое встречается раньше.
| Ввод | Вывод |
|---|---|
| 19 i love segment tree |
segment 7 |
| 21 frog jumps from river |
jumps 5 |
F. Палиндром
Помогите Васе понять, будет ли фраза палиндромом. Учитываются только буквы и цифры, заглавные и строчные буквы считаются одинаковыми.
Решение должно работать за O(N), где N — длина строки на входе.
В единственной строке записана фраза или слово. Буквы могут быть только латинские. Длина текста не превосходит 20000 символов.
Фраза может состоять из строчных и прописных латинских букв, цифр, знаков препинания.
Выведите «True», если фраза является палиндромом, и «False», если не является.
| Ввод | Вывод |
|---|---|
| A man, a plan, a canal: Panama | True |
| zo | False |
G. Работа из дома
Вася реализовал функцию, которая переводит целое число из десятичной системы в двоичную. Но, кажется, она получилась не очень оптимальной.
Попробуйте написать более эффективную программу.
Не используйте встроенные средства языка по переводу чисел в бинарное представление.
На вход подаётся целое число в диапазоне от 0 до 10000.
Выведите двоичное представление этого числа.
| Ввод | Вывод |
|---|---|
| 5 | 101 |
| 14 | 1110 |
H. Двоичная система
Тимофей записал два числа в двоичной системе счисления и попросил Гошу вывести их сумму, также в двоичной системе. Встроенную в язык программирования возможность сложения двоичных чисел применять нельзя. Помогите Гоше решить задачу.
Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.
Два числа в двоичной системе счисления, каждое на отдельной строке. Длина каждого числа не превосходит 10 000 символов.
Одно число в двоичной системе счисления.
| Ввод | Вывод |
|---|---|
| 1010 1011 |
10101 |
| 1 1 |
10 |
I. Степень четырёх
Напишите программу, которая определяет, будет ли положительное целое число степенью четвёрки.
Подсказка: степенью четвёрки будут все числа вида 4^n, где n – целое неотрицательное число.
На вход подаётся целое число в диапазоне от 1 до 10000.
Выведите «True», если число является степенью четырёх, «False» –— в обратном случае.
| Ввод | Вывод |
|---|---|
| 15 | False |
| 16 | True |
J. Факторизация
Основная теорема арифметики говорит: любое число раскладывается на произведение простых множителей единственным образом, с точностью до их перестановки. Например:
- Число 8 можно представить как 2 × 2 × 2.
- Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта отличаются лишь порядком следования множителей.
Разложение числа на простые множители называется факторизацией числа.
Напишите программу, которая производит факторизацию переданного числа.
В единственной строке дано число n (2 ≤ n ≤ 10^9), которое нужно факторизовать.
Выведите в порядке неубывания простые множители, на которые раскладывается число n.
| Ввод | Вывод |
|---|---|
| 8 | 2 2 2 |
| 13 | 13 |
| 100 | 2 2 5 5 |
K. Списочная форма
Вася просил Аллу помочь решить задачу. На этот раз по информатике.
Для неотрицательного целого числа X списочная форма –— это массив его цифр слева направо. К примеру, для 1231 списочная форма будет [1,2,3,1]. На вход подается количество цифр числа Х, списочная форма неотрицательного числа Х и неотрицательное число K. Число К не превосходят 10000. Длина числа Х не превосходит 1000.
Нужно вернуть списочную форму числа X + K.
В первой строке — длина списочной формы числа X. На следующей строке — сама списочная форма с цифрами записанными через пробел.
В последней строке записано число K, 0 ≤ K ≤ 10000.
Выведите списочную форму числа X+K.
| Ввод | Вывод |
|---|---|
| 4 1 2 0 0 34 |
1 2 3 4 |
| 2 9 5 17 |
1 1 2 |
L. Лишняя буква
Васе очень нравятся задачи про строки, поэтому он придумал свою. Есть 2 строки s и t, состоящие только из строчных букв. Строка t получена перемешиванием букв строки s и добавлением 1 буквы в случайную позицию. Нужно найти добавленную букву.
На вход подаются строки s и t, разделённые переносом строки. Длины строк не превосходят 1000 символов. Строки не бывают пустыми.
Выведите лишнюю букву.
| Ввод | Вывод |
|---|---|
| abcd abcde |
e |
| go ogg |
g |
| xtkpx xkctpx |
c |
A. Ближайший ноль
Тимофей ищет место, чтобы построить себе дом. Улица, на которой он хочет жить, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. Каждый участок либо пустой, либо на нём уже построен дом.
Общительный Тимофей не хочет жить далеко от других людей на этой улице. Поэтому ему важно для каждого участка знать расстояние до ближайшего пустого участка. Если участок пустой, эта величина будет равна нулю — расстояние до самого себя.
Помогите Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.
В первой строке дана длина улицы —– n (1 ≤ n ≤ 10^6). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 10^9.
Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.
| Ввод | Вывод |
|---|---|
| 5 0 1 4 9 0 |
0 1 2 1 0 |
| 6 0 7 9 4 8 20 |
0 1 2 3 4 5 |
B. Ловкость рук
«Тренажёр для скоростной печати» представляет собой квадратную клавиатуру из шестнадцати клавиш размером 4x4. На каждой клавише может быть изображена либо точка, либо цифра от 1 до 9.
Занятие на тренажёре делится на раунды:
- каждый раунд состоит из нескольких игр;
- в разных раундах число игр может быть разным;
- номер каждой игры в раунде обозначается счётчиком t.
Для каждого раунда на клавишах устанавливаются определённые значения, которые остаются неизменными в течение всех игр раунда.
Значение счётчика игр t не может превысить значение самого большого числа, отображённого на клавиатуре в текущем раунде.
В упражнении на тренажёре принимают участие два игрока, они играют вдвоём на одной клавиатуре. Для каждого раунда устанавливается максимальное число клавиш, которые может нажать один игрок (оно обозначается переменной k и не изменяется в течение раунда).
В каждой отдельной игре участники должны вместе нажать на клавиши, на которых изображена цифра, соответствующая номеру игры t. Например, во второй игре раунда игроки должны нажать все те клавиши, на которых изображена двойка.
В раунде могут быть игры, где не требуется нажимать кнопки: например, в приведённом варианте раунда в играх от t = 4 до t = 8 кнопки нажимать не потребуется: на клавиатуре нет цифр от 4 до 8:
Если в очередной игре у участников есть возможность нажать все необходимые клавиши — они их нажимают и получают 1 балл.
Предположим, что для раунда задан набор кнопок, как на картинке, и k = 3 (каждый из участников может нажать не более трёх кнопок). Тогда во второй игре (t = 2), где должны быть нажаты двойки, игроки вдвоём смогут нажать только 6 клавиш (k * 2 = 6). Но на клавиатуре семь двоек; участники не смогут нажать их все и не получат балл.
Напишите программу, которая будет принимать данные для определённого раунда:
- значение k,
- значения для кнопок,
и вычислит количество баллов, которое будут заработано в этом раунде.
В первой строке дано целое число k (1 ≤ k ≤ 5).
В четырёх следующих строках заданы значения для кнопок –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.
Выведите единственное число –— количество баллов, которое игроки наберут в раунде.
| Ввод | Вывод |
|---|---|
| 3 1231 2..2 2..2 2..2 |
2 |
| 4 1111 9999 1111 9911 |
1 |
| 4 1111 1111 1111 1111 |
0 |
A. Мониторинг
Алла получила задание, связанное с мониторингом работы различных серверов. Требуется понять, сколько времени обрабатываются определённые запросы на конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца соответствуют идентификатору запроса, а номер строки — идентификатору сервера. Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей исправить баг.
Есть матрица размера 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 |
| 9 5 -7 -1 0 -4 -9 5 -1 2 2 9 3 1 -8 -1 -7 9 0 8 -8 -1 2 4 5 2 8 -7 10 0 -4 -8 -3 10 -7 10 3 1 6 -7 -5 9 -1 9 9 1 9 |
-7 5 3 9 2 -7 -3 1 -1 -1 -1 1 0 4 10 10 6 9 0 2 -8 8 5 0 -7 -7 9 -4 2 -1 -8 2 -4 10 -5 1 -9 9 -7 -1 8 -8 3 9 9 |
B. Список дел
Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и печатает его элементы. Ниже дано описание структуры, которая задаёт узел списка.
В качестве ответа сдайте только код функции, которая печатает элементы списка. Длина списка не превосходит 5000 элементов. Список не бывает пустым.
Функция должна напечатать элементы списка по одному в строке.
C. Нелюбимое дело
Вася размышляет, что ему можно не делать из того списка дел, который он составил. Но, кажется, все пункты очень важные! Вася решает загадать число и удалить дело, которое идёт под этим номером. Список дел представлен в виде односвязного списка. Напишите функцию solution, которая принимает на вход голову списка и номер удаляемого дела и возвращает голову обновлённого списка.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и номер удаляемого элемента и возвращает голову обновлённого списка.
Функция принимает голову списка и индекс элемента, который надо удалить (нумерация с нуля). Список содержит не более 5000 элементов. Список не бывает пустым.
Верните голову списка, в котором удален нужный элемент.
D. Заботливая мама
Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей: напишите функцию solution, определяющую индекс первого вхождения передаваемого ей на вход значения в связном списке, если значение присутствует.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и искомый элемент, а возвращает целое число — индекс найденного элемента или -1.
Функция на вход принимает голову односвязного списка и элемент, который нужно найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым.
Функция возвращает индекс первого вхождения искомого элемента в список(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.
E. Всё наоборот
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список в обратном порядке.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову двусвязного списка и возвращает голову перевёрнутого списка. Ниже дано описание структуры, которая задаёт вершину списка.
Функция принимает на вход единственный аргумент — голову двусвязного списка.
Длина списка не превосходит 1000 элементов. Список не бывает пустым.
Функция должна вернуть голову развернутого списка.
F. Стек - 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 |
| 7 get_max pop pop pop push 10 get_max push -9 |
None error error error 10 |
G. Стек - 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 |
| 10 get_max push -6 pop pop get_max push 2 get_max pop push -2 push -6 |
None error None 2 |
H. Скобочная последовательность
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
- пустая строка —– правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
- правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}.
Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.
Выведите «True» или «False».
| Ввод | Вывод |
|---|---|
| {[()]} | True |
| () | True |
I. Ограниченная очередь
Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс 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 |
| 10 1 push 1 size push 3 size push 1 pop push 1 pop push 3 push 3 |
1 error 1 error 1 1 error |
J. Списочная очередь
Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:
- 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 |
| 6 put -66 put 98 size size get get |
2 2 -66 98 |
| 9 get size put 74 get size put 90 size size size |
error 0 74 0 1 1 1 |
K. Рекурсивные числа Фибоначчи
У Тимофея было n (0 ≤ n ≤ 32) стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту.
Пусть F_i —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Тогда выполняется следующее: F_0 = F_1 = 1. Для всех i ≥ 2 выполнено F_i = F_i−1 + F_i−2.
Определите, сколько кода напишет следующий стажёр –— найдите F_n.
Решение должно быть реализовано рекурсивно.
На вход подаётся n — целое число в диапазоне от 0 до 32.
Нужно вывести F_n.
| Ввод | Вывод |
|---|---|
| 3 | 3 |
| 0 | 1 |
L. Фибоначчи по модулю
У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 10^6) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными — они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F_0 = F_1 = 1. Для всех i ≥ 2 выполнено F_i = F_i−1 + F_i−2.
Определите, сколько кода напишет следующий стажёр –— найдите последние k цифр числа F_n.
Как найти k последних цифр
Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток от его деления на число 10^k. Эта операция обозначается как x mod 10^k. Узнайте, как записывается операция взятия остатка по модулю в вашем языке программирования.
Также обратите внимание на возможное переполнение целочисленных типов, если в вашем языке такое случается.
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 10^6) и k (1 ≤ k ≤ 8).
Выведите единственное число – последние k цифр числа F_n.
Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
| Ввод | Вывод |
|---|---|
| 3 1 | 3 |
| 10 1 | 9 |
A. Дек
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы 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 |
| 7 10 push_front -855 push_front 0 pop_back pop_back push_back 844 pop_back push_back 823 |
-855 0 844 |
| 6 6 push_front -201 push_back 959 push_back 102 push_front 20 pop_front pop_back |
20 102 |
B. Калькулятор
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример 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 |
| 7 2 + 4 * 2 + | 38 |
A. Генератор скобок
Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
- (())
- ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
На вход функция принимает n — целое число от 0 до 10.
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
| Ввод | Вывод |
|---|---|
| 3 | ((())) (()()) (())() ()(()) ()()() |
| 2 | (()) ()() |
B. Комбинации
На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так:
- 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 |
| 92 | wa wb wc xa xb xc ya yb yc za zb zc |
C. Подпоследовательность
Гоша любит играть в игру «Подпоследовательность»: даны 2 строки, и нужно понять, является ли первая из них подпоследовательностью второй. Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.
В первой строке записана строка s. Во второй —- строка t.
Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки не могут быть пустыми.
Выведите True, если s является подпоследовательностью t, иначе —– False.
| Ввод | Вывод |
|---|---|
| abc ahbgdcu |
True |
| abcp ahpc |
False |
D. Печеньки
К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.
Но не всё так просто. Печенья могут быть разного размера. А у каждого ребёнка есть фактор жадности —– минимальный размер печенья, которое он возьмёт. Нужно выяснить, сколько ребят останутся довольными в лучшем случае, когда они действуют оптимально.
Каждый ребёнок может взять не больше одного печенья.
В первой строке записано n —– количество детей.
Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.
В следующей строке записано число m –— количество печенек.
Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.
Оба числа n и m не превосходят 10000.
Нужно вывести одно число –— количество детей, которые останутся довольными
| Ввод | Вывод |
|---|---|
| 2 1 2 3 2 1 3 |
2 |
| 3 2 1 3 2 1 1 |
1 |
E. Покупка домов
Тимофей решил купить несколько домов на знаменитом среди разработчиков Алгосском архипелаге. Он нашёл n объявлений о продаже, где указана стоимость каждого дома в алгосских франках. А у Тимофея есть k франков. Помогите ему определить, какое наибольшее количество домов на Алгосах он сможет приобрести за эти деньги.
В первой строке через пробел записаны натуральные числа n и k.
n — количество домов, которые рассматривает Тимофей, оно не превосходит 100000;
k — общий бюджет, не превосходит 100000;
В следующей строке через пробел записано n стоимостей домов. Каждое из чисел не превосходит 100000. Все стоимости — натуральные числа.
Выведите одно число —– наибольшее количество домов, которое может купить Тимофей.
| Ввод | Вывод |
|---|---|
| 3 300 999 999 999 |
0 |
| 3 1000 350 999 200 |
2 |
F. Периметр треугольника
Перед сном Рита решила поиграть в игру на телефоне. Дан массив целых чисел, в котором каждый элемент обозначает длину стороны треугольника. Нужно определить максимально возможный периметр треугольника, составленного из сторон с длинами из заданного массива. Помогите Рите скорее закончить игру и пойти спать.
Напомним, что из трёх отрезков с длинами a ≤ b ≤ c можно составить треугольник, если выполнено неравенство треугольника: c < a + b
Разберём пример:
даны длины сторон 6, 3, 3, 2. Попробуем в качестве наибольшей стороны выбрать 6. Неравенство треугольника не может выполниться, так как остались 3, 3, 2 —– максимальная сумма из них равна 6.
Без шестёрки оставшиеся три отрезка уже образуют треугольник со сторонами 3, 3, 2. Неравенство выполняется: 3 < 3 + 2. Периметр равен 3 + 3 + 2 = 8.
В первой строке записано количество отрезков n, 3 ≤ n ≤ 10000.
Во второй строке записано n неотрицательных чисел, не превосходящих 10 000, –— длины отрезков.
Нужно вывести одно число —– наибольший периметр треугольника.
Гарантируется, что тройка чисел, которая может образовать треугольник, всегда есть.
| Ввод | Вывод |
|---|---|
| 4 6 3 3 2 |
8 |
| 6 5 3 7 2 8 3 |
20 |
G. Гардероб
Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом —– жёлтого, и в конце —– малинового. Помогите Рите справиться с этой задачей.
Примечание: попробуйте решить задачу за один проход по массиву!
В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.
Нужно вывести в строку через пробел цвета предметов в правильном порядке.
| Ввод | Вывод |
|---|---|
| 7 0 2 1 2 0 0 1 |
0 0 0 1 1 2 2 |
| 5 2 1 2 0 1 |
0 1 1 2 2 |
| 6 2 1 1 2 0 2 |
0 1 1 2 2 2 |
H. Большое число
Вечером ребята решили поиграть в игру «Большое число».
Даны числа. Нужно определить, какое самое большое число можно из них составить.
В первой строке записано n — количество чисел. Оно не превосходит 100.
Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
Нужно вывести самое большое число, которое можно составить из данных чисел.
| Ввод | Вывод |
|---|---|
| 3 15 56 2 |
56215 |
| 3 1 783 2 |
78321 |
| 5 2 4 5 2 10 |
542210 |
I. Любители конференций
На IT-конференции присутствовали студенты из разных вузов со всей страны. Для каждого студента известен ID университета, в котором он учится.
Тимофей предложил Рите выяснить, из каких k вузов на конференцию пришло больше всего учащихся.
В первой строке дано количество студентов в списке —– n (1 ≤ n ≤ 15 000).
Во второй строке через пробел записаны n целых чисел —– ID вуза каждого студента. Каждое из чисел находится в диапазоне от 0 до 10 000.
В третьей строке записано одно число k.
Выведите через пробел k ID вузов с максимальным числом участников. Они должны быть отсортированы по убыванию популярности (по количеству гостей от конкретного вуза). Если более одного вуза имеет одно и то же количество учащихся, то выводить их ID нужно в порядке возрастания.
| Ввод | Вывод |
|---|---|
| 7 1 2 3 1 2 3 4 3 |
1 2 3 |
| 6 1 1 1 2 2 3 1 |
1 |
J. Пузырёк
Чтобы выбрать самый лучший алгоритм для решения задачи, Гоша продолжил изучать разные сортировки. На очереди сортировка пузырьком — https://ru.wikipedia.org/wiki/Сортировка_пузырьком
Её алгоритм следующий (сортируем по неубыванию):
- На каждой итерации проходим по массиву, поочередно сравнивая пары соседних элементов. Если элемент на позиции i больше элемента на позиции i + 1, меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива.
- Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован.
- После не более чем n – 1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.
Помогите Гоше написать код алгоритма.
В первой строке на вход подаётся натуральное число n — длина массива, 2 ≤ n ≤ 1000.
Во второй строке через пробел записано n целых чисел.
Каждое из чисел по модулю не превосходит 1000.
Обратите внимание, что считывать нужно только 2 строки: значение n и входной массив.
После каждого прохода по массиву, на котором какие-то элементы меняются местами, выводите его промежуточное состояние.
Таким образом, если сортировка завершена за k меняющих массив итераций, то надо вывести k строк по n чисел в каждой — элементы массива после каждой из итераций.
Если массив был изначально отсортирован, то просто выведите его.
| Ввод | Вывод |
|---|---|
| 5 4 3 9 2 1 |
3 4 2 1 9 3 2 1 4 9 2 1 3 4 9 1 2 3 4 9 |
| 5 12 8 9 10 11 |
8 9 10 11 12 |
K. Сортировка слиянием
Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.
- Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом [left,mid) массива array, а второй – полуинтервалом [mid,right) массива array.
- Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает.
- Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge.
Заметьте, что в функции передаются именно полуинтервалы [begin,end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где arr = [4,5,3,0,1,2], то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как arr = [0,3,4,5,1,2].
Реализуйте эти две функции.
Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 10^9. Длина сортируемого диапазона не превосходит 10^5.
При написании и отправке решений соблюдайте следующие правила:
merge(arr: list, left: int, mid: int, right: int) -> array
merge_sort(arr: list, left: int, right: int) -> None
L. Два велосипеда
Вася решил накопить денег на два одинаковых велосипеда — себе и сестре. У Васи есть копилка, в которую каждый день он может добавлять деньги (если, конечно, у него есть такая финансовая возможность). В процессе накопления Вася не вынимает деньги из копилки.
У вас есть информация о росте Васиных накоплений — сколько у Васи в копилке было денег в каждый из дней.
Ваша задача — по заданной стоимости велосипеда определить
- первый день, в которой Вася смог бы купить один велосипед,
- и первый день, в который Вася смог бы купить два велосипеда.
Подсказка: решение должно работать за O(log n).
В первой строке дано число дней n, по которым велись наблюдения за Васиными накоплениями. 1 ≤ n ≤ 10^6.
В следующей строке записаны n целых неотрицательных чисел. Числа идут в порядке неубывания. Каждое из чисел не превосходит 10^6.
В третьей строке записано целое положительное число s — стоимость велосипеда. Это число не превосходит 10^6.
Нужно вывести два числа — номера дней по условию задачи.
Если необходимой суммы в копилке не нашлось, нужно вернуть -1 вместо номера дня.
| Ввод | Вывод |
|---|---|
| 6 1 2 4 4 6 8 3 |
3 5 |
| 6 1 2 4 4 4 4 3 |
3 -1 |
| 6 1 2 4 4 4 4 10 |
-1 -1 |
M. Золотая середина
Задача повышенной сложности
На каждом острове в архипелаге Алгосы живёт какое-то количество людей или же остров необитаем (тогда на острове живёт 0 людей). Пусть на i-м острове численность населения составляет a_i. Тимофей захотел найти медиану среди всех значений численности населения.
Определение: Медиана (https://ru.wikipedia.org/wiki/Медиана_(статистика)) массива чисел a_i —– это такое число, что половина чисел из массива не больше него, а другая половина не меньше. В общем случае медиану массива можно найти, отсортировав числа и взяв среднее из них. Если количество чисел чётно, то возьмём в качестве медианы полусумму соседних средних чисел, (a[n/2] + a[n/2 + 1])/2.
У Тимофея уже есть отдельно данные по северной части архипелага и по южной, причём значения численности населения в каждой группе отсортированы по неубыванию.
Определите медианную численность населения по всем островам Алгосов.
Подсказка: Если n –— число островов в северной части архипелага, а m –— в южной, то ваше решение должно работать за O(log(n + m)).
В первой строке записано натуральное число n, во второй —– натуральное число m. Они не превосходят 10 000.
Далее в строку через пробел записаны n целых неотрицательных чисел, каждое из которых не превосходит 10 000, –— значения численности населения в северной части Алгосов.
В последней строке через пробел записаны m целых неотрицательных чисел, каждое из которых не превосходит 10 000 –— значения численности населения в южной части Алгосов.
Значения в третьей и четвёртой строках упорядочены по неубыванию.
Нужно вывести одной число — найденную медиану.
| Ввод | Вывод |
|---|---|
| 2 1 1 3 2 |
2 |
| 2 2 1 2 3 4 |
2.5 |
| 8 10 0 0 0 1 3 3 5 10 4 4 5 7 7 7 8 9 9 10 |
5 |
N. Клумбы
Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанам. На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. Для ландшафтных работ было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. Нужно определить границы будущих клумб.
Рассмотрим примеры.
Пример 1:
Даны 4 отрезка: [7,8], [7,8] ,[2,3], [6,10]. Два одинаковых отрезка [7,8] и [7,8] сливаются в один, но потом их накрывает отрезок [6,10]. Таким образом, имеем две клумбы с координатами [2,3] и [6,10].
Пример 2:
Во втором сэмпле опять 4 отрезка: [2,3], [3,4], [3,4], [5,6]. Отрезки [2,3], [3,4] и [3,4] сольются в один отрезок [2,4]. Отрезок [5,6] ни с кем не объединяется, добавляем его в ответ.
В первой строке задано количество садовников n. Число садовников не превосходит 100000.
В следующих n строках через пробел записаны координаты клумб в формате: start end, где start —– координата начала, end —– координата конца. Оба числа целые, неотрицательные и не превосходят 10^7. start строго меньше, чем end.
Нужно вывести координаты каждой из получившихся клумб в отдельных строках. Данные должны выводиться в отсортированном порядке —– сначала клумбы с меньшими координатами, затем —– с бОльшими.
| Ввод | Вывод |
|---|---|
| 4 7 8 7 8 2 3 6 10 |
2 3 6 10 |
| 4 2 3 5 6 3 4 3 4 |
2 4 5 6 |
| 6 1 3 3 5 4 6 5 6 2 4 7 10 |
1 6 7 10 |
O. Разность треш-индексов
Гоша долго путешествовал и измерил площадь каждого из n островов Алгосов, но ему этого мало! Теперь он захотел оценить, насколько разнообразными являются острова в составе архипелага.
Для этого Гоша рассмотрел все пары островов (таких пар, напомним, n * (n-1) / 2) и посчитал попарно разницу площадей между всеми островами. Теперь он собирается упорядочить полученные разницы, чтобы взять k-ую по порядку из них.
Помоги Гоше найти k-ю минимальную разницу между площадями эффективно.
Пояснения к примерам
Пример 1
Выпишем все пары площадей и найдём соответствующие разницы
- |2 - 3| = 1
- |3 - 4| = 1
- |2 - 4| = 2
Так как нам нужна 2-я по величине разница, то ответ будет 1.
Пример 2
У нас есть два одинаковых элемента в массиве —– две единицы, поэтому минимальная (первая) разница равна нулю.
В первой строке записано натуральное число n –— количество островов в архипелаге (2 ≤ n ≤ 100 000).
В следующей строке через пробел записаны n площадей островов — n натуральных чисел, каждое из которых не превосходит 1 000 000.
В последней строке задано число k. Оно находится в диапазоне от 1 до n(n - 1) / 2.
Выведите одно число –— k-ую минимальную разницу.
| Ввод | Вывод |
|---|---|
| 3 2 3 4 2 |
1 |
| 3 1 3 1 1 |
0 |
| 3 1 3 5 3 |
4 |
P. Частичная сортировка
После того, как Гоша узнал про сортировку слиянием и быструю сортировку, он решил придумать свой метод сортировки, который предполагал бы разделение данных на части.
Назвал он свою сортировку Частичной.
Этим методом можно отсортировать n уникальных чисел a_1, a_2, … , a_n, находящихся в диапазоне от 0 до n - 1.
Алгоритм сортировки состоит из трёх шагов:
- Разбить исходную последовательность на k блоков B_1, …, B_k. Блоки могут иметь разные размеры. Если размер блока i равен s_i, то B_1 ={ a_1, …, a_s1 }, B_2 = { a_s1 + 1, … , a_s1 + s2 } и так далее.
- Отсортировать каждый из блоков.
- Объединить блоки — записать сначала отсортированный блок B_1, потом B_2, … , B_k
Частичная сортировка лучше обычной в том случае, если в первом пункте у нас получится разбить последовательность на большое число блоков. Однако далеко не каждое такое разбиение подходит. Определите максимальное число блоков, на которое можно разбить исходную последовательность, чтобы сортировка отработала корректно.
Рассмотрим пример: a = [3, 2, 0, 1, 4, 6, 5].
Минимальный размер первого блока B_1 равен 4. Если взять лишь первые два элемента, то отсортированная последовательность будет начинаться с двойки, что неправильно. Если взять первые три элемента, то последовательность будет начинаться с нуля, но после него сразу же пойдёт двойка. Первые четыре элемента уже гарантируют корректный префикс после объединения блоков. Четвёрку можно взять как самостоятельный блок из одного элемента. Последние два элемента надо объединить в третий блок. Таким образом:
B_1 = { 3, 2, 0, 1 }
B_2 = { 4 }
B_3 = { 6, 5 }
В данном примере ответ равен 3. Максимальное число блоков равно трём.
В первой строке задано n — количество чисел для сортировки (n ≤ 1000).
В следующей строке записаны числа от 0 до n - 1, которые надо разбить на блоки.
Выведите максимальное количество блоков, на которое можно разбить данные при использовании метода Частичной сортировки.
| Ввод | Вывод |
|---|---|
| 4 0 1 3 2 |
3 |
| 8 3 6 7 4 1 5 0 2 |
1 |
| 5 1 0 2 3 4 |
4 |
A. Поиск в сломанном массиве
Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее, нужно обеспечить возможность находить в нем элемент за O(log n).
Можно предполагать, что в массиве только уникальные элементы.
От вас требуется реализовать функцию, осуществляющую поиск в сломанном массиве.
Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.
В примерах:
В первой строке записано число n –— длина массива.
Во второй строке записано положительное число k –— искомый элемент.
Далее в строку через пробел записано n натуральных чисел – элементы массива.
Функция должна вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть −1.
Изменять массив нельзя.
Для отсечения неэффективных решений ваша функция будет запускаться от 100000 до 1000000 раз.
| Ввод | Вывод |
|---|---|
| 9 5 19 21 100 101 1 4 5 7 12 |
6 |
| 2 1 5 1 |
1 |
B. Эффективная быстрая сортировка
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач P_i и размер штрафа F_i. Штраф начисляется за неудачные попытки и время, затраченное на задачу.
Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.
Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. 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)
- числом решённых задач P_i
- штрафом F_i
F_i и P_i — целые числа, лежащие в диапазоне от 0 до 10^9.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|---|---|
| 5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
| 5 alla 0 0 gena 0 0 gosha 0 0 rita 0 0 timofey 0 0 |
alla gena gosha rita timofey |
A. Полиномиальный хеш
Алле очень понравился алгоритм вычисления полиномиального хеша. Помогите ей написать функцию, вычисляющую хеш строки s. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
Полиномиальный хеш считается по формуле:
h(s) = (s_1 * a^n-1 + s_2 * a^n-2 + ... + s_n-1 * a + s_n) mod m
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.
Во второй строке дано число m (1 ≤ m ≤ 10^9) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 10^6), состоящая из больших и маленьких латинских букв.
Выведите целое неотрицательное число –— хеш заданной строки.
| Ввод | Вывод |
|---|---|
| 123 100003 a |
97 |
| 123 100003 hash |
6080 |
| 123 100003 HaSH |
56156 |
B. Сломай меня
Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было.
В этой задаче вам надо будет лишь найти две различные строки, которые для заданной хеш-функции будут давать одинаковое значение.
Гоша использует следующую хеш-функцию:
h(s) = (s_1 * a^n-1 + s_2 * a^n-2 + ... + s_n-1 * a + s_n) mod m
для a = 1000 и m = 123 987 123.
В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В задаче единственный тест без ввода
Отправьте две строки, по одной в строке. Строки могут состоять только из маленьких латинских букв и не должны превышать в длину 1000 знаков каждая. Код отправлять не требуется. Строки из примера использовать нельзя.
Пример вывода:
ezhgeljkablzwnvuwqvp
gbpdcvkumyfxillgnqrv
C. Префиксные хеши
Алла не остановилась на достигнутом –— теперь она хочет научиться быстро вычислять хеши произвольных подстрок данной строки. Помогите ей!
На вход поступают запросы на подсчёт хешей разных подстрок. Ответ на каждый запрос должен выполняться за O(1). Допустимо в начале работы программы сделать предподсчёт для дальнейшей работы со строкой.
Напомним, что полиномиальный хеш считается по формуле
h(s) = (s_1 * a^n-1 + s_2 * a^n-2 + ... + s_n-1 * a + s_n) mod m
В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш. Во второй строке дано число m (1 ≤ m ≤ 10^7) –— модуль. В третьей строке дана строка s (0 ≤ |s| ≤ 10^6), состоящая из больших и маленьких латинских букв.
В четвертой строке дано число запросов t –— натуральное число от 1 до 10^5. В каждой из следующих t строк записаны через пробел два числа l и r –— индексы начала и конца очередной подстроки. (1 ≤ l ≤ r ≤ |s|).
Для каждого запроса выведите на отдельной строке хеш заданной в запросе подстроки.
| Ввод | Вывод |
|---|---|
| 1000 1000009 abcdefgh 7 1 1 1 5 2 3 3 4 4 4 1 8 5 8 |
97 225076 98099 99100 100 436420 193195 |
| 100 10 a 1 1 1 |
7 |
D. Кружки
В компании, где работает Тимофей, заботятся о досуге сотрудников и устраивают различные кружки по интересам. Когда кто-то записывается на занятие, в лог вносится название кружка.
По записям в логе составьте список всех кружков, в которые ходит хотя бы один человек.
В первой строке даётся натуральное число n, не превосходящее 10 000 –— количество записей в логе.
В следующих n строках —– названия кружков.
Выведите уникальные названия кружков по одному на строке, в порядке появления во входных данных.
| Ввод | Вывод |
|---|---|
| 8 вышивание крестиком рисование мелками на парте настольный керлинг настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение таракановедение |
вышивание крестиком рисование мелками на парте настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение |
E. Подстроки
На вход подается строка. Нужно определить длину наибольшей подстроки, которая не содержит повторяющиеся символы.
Одна строка, состоящая из строчных латинских букв. Длина строки не превосходит 10 000.
Выведите натуральное число —– ответ на задачу.
| Ввод | Вывод |
|---|---|
| abcabcbb | 3 |
| bbbbb | 1 |
F. Анаграммная группировка
Вася решил избавиться от проблем с произношением и стать певцом. Он обратился за помощью к логопеду. Тот посоветовал Васе выполнять упражнение, которое называется анаграммная группировка. В качестве подготовительного этапа нужно выбрать из множества строк анаграммы.
Анаграммы –— это строки, которые получаются друг из друга перестановкой символов. Например, строки «SILENT» и «LISTEN» являются анаграммами.
Помогите Васе найти анаграммы.
В первой строке записано число n —– количество строк.
Далее в строку через пробел записаны n строк.
n не превосходит 6000. Длина каждой строки не более 100 символов.
Нужно вывести в отсортированном порядке индексы строк, которые являются анаграммами.
Каждая группа индексов должна быть выведена в отдельной строке. Индексы внутри одной группы должны быть отсортированы по возрастанию. Группы между собой должны быть отсортированы по возрастанию первого индекса.
Обратите внимание, что группа анаграмм может состоять и из одной строки. Например, если в исходном наборе нет анаграмм, то надо вывести n групп, каждая из которых состоит из одного индекса.
| Ввод | Вывод |
|---|---|
| 6 tan eat tea ate nat bat |
0 4 1 2 3 5 |
G. Соревнование
Жители Алгосов любят устраивать турниры по спортивному программированию. Все участники разбиваются на пары и соревнуются друг с другом. А потом два самых сильных программиста встречаются в финальной схватке, которая состоит из нескольких раундов. Если в очередном раунде выигрывает первый участник, в таблицу с результатами записывается 0, если второй, то 1. Ничьей в раунде быть не может.
Нужно определить наибольший по длине непрерывный отрезок раундов, по результатам которого суммарно получается ничья. Например, если дана последовательность 0 0 1 0 1 1 1 0 0 0, то раунды с 2-го по 9-й (нумерация начинается с единицы) дают ничью.
В первой строке задаётся n (0 ≤ n ≤ 10^5) –— количество раундов. Во второй строке через пробел записано n чисел –— результаты раундов. Каждое число равно либо 0, либо 1.
Выведите длину найденного отрезка.
| Ввод | Вывод |
|---|---|
| 2 0 1 |
2 |
| 3 0 1 0 |
2 |
H. Странное сравнение
Жители Алгосского архипелага придумали новый способ сравнения строк. Две строки считаются равными, если символы одной из них можно заменить на символы другой так, что первая строка станет точной копией второй строки. При этом необходимо соблюдение двух условий:
- Порядок вхождения символов должен быть сохранён.
- Одинаковым символам первой строки должны соответствовать одинаковые символы второй строки. Разным символам —– разные.
Например, если строка s = «abacaba», то ей будет равна строка t = «xhxixhx», так как все вхождения «a» заменены на «x», «b» –— на «h», а «c» –— на «i». Если же первая строка s=«abc», а вторая t=«aaa», то строки уже не будут равны, так как разные буквы первой строки соответствуют одинаковым буквам второй.
В первой строке записана строка s, во второй –— строка t. Длины обеих строк не превосходят 106. Обе строки содержат хотя бы по одному символу и состоят только из маленьких латинских букв.
Строки могут быть разной длины.
Выведите «YES», если строки равны (согласно вышеописанным правилам), и «NO» в ином случае.
| Ввод | Вывод |
|---|---|
| mxyskaoghi qodfrgmslc |
YES |
| agg xdd |
YES |
| agg xda |
NO |
I. Общий подмассив
Гоша увлёкся хоккеем и часто смотрит трансляции матчей. Чтобы более-менее разумно оценивать силы команд, он сравнивает очки, набранные во всех матчах каждой командой.
Гоша попросил вас написать программу, которая по результатам игр двух выбранных команд найдёт наибольший по длине отрезок матчей, когда эти команды зарабатывали одинаковые очки.
Рассмотрим первый пример:
Результаты первой команды: [1 2 3 2 1].
Результаты второй команды: [3 2 1 5 6].
Наиболее продолжительный общий отрезок этих массивов имеет длину 3 –— это [3 2 1].
В первой строке находится число n (1 ≤ n ≤ 10^5) –— количество матчей, которые были сыграны первой командой.
Во второй строке записано n целых чисел –— очки в этих играх.
В третьей строке дано число m (1 ≤ m ≤ 10^5) —– количество матчей, которые сыграла вторая команда.
В четвертой строке заданы m целых чисел —– результаты второй команды.
Число очков, заработанных в одной игре, лежит в диапазоне от 0 до 255.
Выведите целое неотрицательное число —– максимальное количество матчей подряд, в которых команды зарабатывали одинаковые очки.
| Ввод | Вывод |
|---|---|
| 5 1 2 3 2 1 5 3 2 1 5 6 |
3 |
| 5 1 2 3 4 5 3 4 5 9 |
2 |
J. Сумма четвёрок
У Гоши есть любимое число S. Помогите ему найти все уникальные четвёрки чисел в массиве, которые в сумме дают заданное число S.
В первой строке дано общее количество элементов массива n (0 ≤ n ≤ 1000).
Во второй строке дано целое число S: |S| ≤ 10^9.
В третьей строке задан сам массив. Каждое число является целым и не превосходит по модулю 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 |
| 6 0 1 0 -1 0 2 -2 |
3 -2 -1 1 2 -2 0 0 2 -1 0 0 1 |
| 5 4 1 1 1 1 1 |
1 1 1 1 1 |
K. Ближайшая остановка
Гоша едет в гости к друзьям. Ему придётся сначала ехать на метро, а потом пересаживаться на автобус. Гоша не любит долго ждать, поэтому хочет выбрать такую станцию метро, рядом с которой расположено как можно больше остановок автобуса. Гоша считает, что остановка находится рядом с метро, если расстояние между ними не превосходит 20 метров. Обратите внимание, что в одной точке могут располагаться несколько остановок.
Гоше известны все координаты автобусных остановок и координаты выходов из метро. Помогите ему найти выход из метро, рядом с которым расположено больше всего остановок.
Напомним, что расстояние между двумя точками с координатами x_1, y_1 и x_2, y_2 вычисляется по формуле sqrt((x_1 - x_2)^2 + (y_1 - y_2)^2).
Пояснение к примеру 1:
Рядом с 1-м выходом (-1, 0) находится только остановка с координатами (10, 0).
Рядом со 2-м выходом (1, 0) находятся уже две остановки —– (10, 0) и (20, 0).
Рядом с 3-м выходом (2, 5) расположены все три остановки –— (22, 5), (20, 0) и (10, 0)
Пояснение к примеру 2:
Третий выход теперь находится в точке (0, 5). Он рядом только с двумя остановками — (20, 5) и (10, 0).
Рядом с 2-м и 3-м выходом одинаковое число остановок, поэтому в ответ идет 2-й выход, так как он раньше во входных данных.
В первой строке дано количество выходов из метро –— натуральное число n (1 ≤ n ≤ 10^4). В следующих n строках даны координаты выходов из метро. Каждый выход описывается двумя координатами x и y, записанными через пробел.
В следующей строке дано количество автобусных остановок —– натуральное число m (1 ≤ m ≤ 10^6). В следующих m строках заданы координаты остановок. Каждая остановка описывается двумя числами —– своими x и y координатами, записанными через пробел.
Все координаты —– целые числа, не превосходящие 109 по модулю. Единицы измерения —– метры.
Выведите единственное число –— номер того выхода из метро, рядом с которым расположено больше всего остановок. Номер выхода –— его порядковый номер во входных данных (нумерация с единицы).
Если подходящих выходов из метро несколько, выведите тот, который встречается раньше во входных данных.
| Ввод | Вывод |
|---|---|
| 3 -1 0 1 0 2 5 3 10 0 20 0 22 5 |
3 |
| 3 -1 0 1 0 0 5 3 10 0 20 0 20 5 |
2 |
L. МногоГоша
Дана длинная строка, состоящая из маленьких латинских букв. Нужно найти все её подстроки длины n, которые встречаются хотя бы k раз.
В первой строчке через пробел записаны два натуральных числа n и k.
Во второй строчке записана строка, состоящая из маленьких латинских букв. Длина строки 1 ≤ L ≤ 10^6.
n ≤ L, k ≤ L.
Для каждой найденной подстроки выведите индекс начала её первого вхождения (нумерация в строке начинается с нуля).
Выводите индексы в любом порядке, в одну строку, через пробел.
| Ввод | Вывод |
|---|---|
| 10 2 gggggooooogggggoooooogggggssshaa |
0 5 |
| 3 4 allallallallalla |
0 1 2 |
A. Лампочки
Гоша повесил на стену гирлянду в виде бинарного дерева, в узлах которого находятся лампочки. У каждой лампочки есть своя яркость. Уровень яркости лампочки соответствует числу, расположенному в узле дерева. Помогите Гоше найти самую яркую лампочку в гирлянде, то есть такую, у которой яркость наибольшая.
На вход подается корень дерева.
Функция должна вернуть максимальное значение яркости в узле дерева.
B. Сбалансированное дерево
Гоше очень понравилось слушать рассказ Тимофея про деревья. Особенно часть про сбалансированные деревья. Он решил написать функцию, которая определяет, сбалансировано ли дерево.
Дерево считается сбалансированным, если левое и правое поддеревья каждой вершины отличаются по высоте не больше, чем на единицу.
На вход функции подаётся корень бинарного дерева.
Функция должна вернуть True, если дерево сбалансировано в соответствии с критерием из условия, иначе - False.
C. Дерево - анаграмма
Гоша и Алла играют в игру «Удивительные деревья». Помогите ребятам определить, является ли дерево, которое им встретилось, деревом-анаграммой?
Дерево называется анаграммой, если оно симметрично относительно своего центра.
Напишите функцию, которая определяет, является ли дерево анаграммой.
На вход подаётся корень дерева.
Функция должна вернуть True если дерево является анаграммой. Иначе - False.
D. Деревья - близнецы
Гоше на день рождения подарили два дерева. Тимофей сказал, что они совершенно одинаковые. Но, по мнению Гоши, они отличаются.
Помогите разрешить этот философский спор!
На вход подаются корни двух деревьев.
Функция должна вернуть True если деревья являются близнецами. Иначе - False.
E. Дерево поиска
Гоша понял, что такое дерево поиска, и захотел написать функцию, которая определяет, является ли заданное дерево деревом поиска. Значения в левом поддереве должны быть строго меньше, в правом —- строго больше значения в узле.
Помогите Гоше с реализацией этого алгоритма.
На вход функции подается корень бинарного дерева.
Функция должна вернуть True, если дерево является деревом поиска, иначе - False.
F. Максимальная глубина
Алла хочет побывать на разных островах архипелага Алгосы. Она составила карту. Карта представлена в виде дерева: корень обозначает центр архипелага, узлы –— другие острова. А листья —– это дальние острова, на которые Алла хочет попасть.
Помогите Алле определить максимальное число островов, через которые ей нужно пройти для совершения одной поездки от стартового острова до места назначения, включая начальный и конечный пункты.
На вход подается корень дерева.
Функция должна вернуть число, равное максимальному числу островов в пути (включая начальный и конечный пункты).
G. Максимальный путь в дереве
Тимофей устраивает соревнования по спортивному ориентированию в своём офисе. Схема офиса представлена в виде дерева. Посещая каждый пункт, можно зарабатывать или терять очки. Если в узле записано положительное число, это значение добавляется к текущему количеству очков участника. Если отрицательное —– очки вычитаются. Если 0 –— их количество не меняется.
Нужно определить, какое максимальное число очков можно заработать, пройдя по пути из какого-то пункта A в какой-то (возможно, тот же) пункт B.
Путь не обязательно должен проходить через корень или содержать лист. Путь должен содержать по крайней мере один узел.
Пример 1:
В дереве всего три вершины, во всех вершинах записаны положительные числа, поэтому объединим все три вершины в один путь. В ответе получим: 1+1+2=4.
Пример 2:
Теперь в дереве есть вершина с отрицательным весом, через неё в данном случае проходить будет невыгодно. Оптимальный путь: 2+7+3=12.
Пример 3:
Оптимальный путь: 7+2+3+9=21.
Пример 4:
В этот раз имеет смысл пройти через вершину с отрицательным весом, так как в левом поддереве вершины −3 лежит 5. Оптимальный путь: 2+2−3+5=6.
Требования к решению: передаваемое в качестве аргумента дерево нельзя менять. Не храните вспомогательную информацию в вершинах.
На вход подается корень дерева.
Функция должна вернуть число, равное максимальному количеству очков, которое можно заработать, попав из пункта А в пункт В.
H. Числовые пути
Вася и его друзья решили поиграть в игру. Дано дерево, в узлах которого записаны цифры от 0 до 9. Таким образом, каждый путь от корня до листа содержит число, получившееся конкатенацией цифр пути (склеиванием цифр пути в одно число). Нужно найти сумму всех таких чисел в дереве.
Гарантируется, что ответ не превосходит 20 000.
На вход подается корень дерева.
Функция должна вернуть число, равное сумме чисел всех путей в дереве.
I. Разные деревья поиска
Ребятам стало интересно, сколько может быть различных деревьев поиска, содержащих в своих узлах все уникальные числа от 1 до n. Помогите им найти ответ на этот вопрос.
В единственной строке задано число n. Оно не превосходит 20.
Нужно вывести число, равное количеству различных деревьев поиска, в узлах которых могут быть размещены числа от 1 до n включительно.
| Ввод | Вывод |
|---|---|
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
J. Добавь узел
Дано BST. Надо вставить узел с заданным ключом. Ключи в дереве могут повторяться.
На вход функции подаётся корень корректного бинарного дерева поиска и ключ, который надо вставить в дерево. Осуществите вставку этого ключа. Если ключ уже есть в дереве, то его дубликаты уходят в правого сына. Таким образом вид дерева после вставки определяется однозначно. Функция должна вернуть корень дерева после вставки вершины.
Ваше решение должно работать за O(h), где h –— высота дерева.
На рисунках ниже даны два примера вставки вершин в дерево.
Ключи дерева – натуральные числа, не превосходящие 10^9. Число вершин в дереве не превосходит 10^5.
K. Выведи диапазон
Напишите функцию, которая будет выводить по неубыванию все ключи от L до R включительно в заданном бинарном дереве поиска.
Ключи в дереве могут повторяться. Решение должно иметь сложность O(h+k), где h –— глубина дерева, k — число элементов в ответе.
В данной задаче если в узле содержится ключ x, то другие ключи, равные x, могут быть как в правом, так и в левом поддереве данного узла. (Дерево строил стажёр, так что ничего страшного).
На вход функции подаётся корень дерева и искомый ключ. Число вершин в дереве не превосходит 10^5. Ключи – натуральные числа, не превосходящие 10^9. Гарантируется, что L ≤ R.
В итоговом решении не надо определять свою структуру / свой класс, описывающий вершину дерева.
Функция должна напечатать по неубыванию все ключи от L до R по одному в строке.
L. Просеивание вниз
Напишите функцию, совершающую просеивание вниз в куче на максимум. Гарантируется, что порядок элементов в куче может быть нарушен только элементом, от которого запускается просеивание.
Функция принимает в качестве аргументов массив, в котором хранятся элементы кучи, и индекс элемента, от которого надо сделать просеивание вниз. Функция должна вернуть индекс, на котором элемент оказался после просеивания. Также необходимо изменить порядок элементов в переданном в функцию массиве.
Индексация в массиве, содержащем кучу, начинается с единицы. Таким образом, сыновья вершины на позиции v это 2v и 2v+1. Обратите внимание, что нулевой элемент в передаваемом массиве фиктивный, вершина кучи соответствует 1-му элементу.
Элементы кучи —– целые числа, лежащие в диапазоне от −10^9 до 10^9. Все элементы кучи уникальны. Передаваемый в функцию индекс лежит в диапазоне от 1 до размера передаваемого массива. В куче содержится от 1 до 10^5 элементов.
M. Просеивание вверх
Напишите функцию, совершающую просеивание вверх в куче на максимум. Гарантируется, что порядок элементов в куче может быть нарушен только элементом, от которого запускается просеивание.
Функция принимает в качестве аргументов массив, в котором хранятся элементы кучи, и индекс элемента, от которого надо сделать просеивание вверх. Функция должна вернуть индекс, на котором элемент оказался после просеивания. Также необходимо изменить порядок элементов в переданном в функцию массиве.
Индексация в массиве, содержащем кучу, начинается с единицы. Таким образом, сыновья вершины на позиции v это 2v и 2v+1. Обратите внимание, что нулевой элемент в передаваемом массиве фиктивный, вершина кучи соответствует 1-му элементу.
Элементы кучи —– целые числа, лежащие в диапазоне от −10^9 до 10^9. Все элементы кучи уникальны. Передаваемый в функцию индекс лежит в диапазоне от 1 до размера передаваемого массива. В куче содержится от 1 до 10^5 элементов.
N. Разбиение дерева
Дано бинарное дерево поиска, в котором хранятся целые числа. От этого дерева надо отделить k самых маленьких элементов.
Реализуйте функцию, которая принимает корень дерева и число k, а возвращает два BST — в первом k наименьших элементов из исходного дерева, а во втором — оставшиеся вершины BST.
В вершинах дерева уже записаны корректные размеры поддеревьев (точное название поля смотрите в заготовках кода). После разбиения размеры должны остаться корректными — вам придётся пересчитывать их на ходу.
Ваше решение должно иметь асимптотику O(h), где h — высота исходного дерева.
Числа, записанные в вершинах дерева, лежат в диапазоне от 0 до 10^9. Дерево не содержит одинаковых ключей.
Число вершин в дереве не превосходит 10^5.
A. Строительство лесенок
Вася занимается строительством лесенок из блоков. Лесенка состоит из ступенек, при этом i-ая ступенька должна состоять ровно из i блоков.
По заданному числу блоков n определите максимальное количество ступенек в лесенке, которую можно построить из этих блоков.
Ввводится одно число n (1 ≤ n ≤ 2^31 - 1).
Выведите одно число — количество ступенек в лесенке.
| Ввод | Вывод |
|---|---|
| 5 | 2 |
| 8 | 3 |
Рисунок соответствует примерам. На рисунке черным показаны блоки, использованные при строительстве лестницы, а красным — оставшиеся лишними блоки, которых недостаточно для строительства очередной ступеньки.
B. Канонический путь
По заданной строке, являющейся абсолютным адресом в Unix-системе, вам необходимо получить канонический адрес.
В Unix-системе "." соответсвутет текущей директории, ".." — родительской директории, при этом будем считать, что любое количество точек подряд, большее двух, соответствует директории с таким названием (состоящем из точек). "/" является разделителем вложенных директорий, причем несколько "/" подряд должны интерпретироваться как один "/".
Канонический путь должен обладать следующими свойствами:
- всегда начинаться с одного "/"
- любые две вложенные директории разделяются ровно одним знаком "/"
- путь не заканчивается "/" (за исключением корневой директории, состоящего только из символа "/")
- в каноническом пути есть только директории, т.е. нет ни одного вхождения "." или ".." как соответствия текущей или родительской директории
Вводится строка с абсолютным адресом, её длина не превосходит 100.
Выведите канонический путь.
| Ввод | Вывод |
|---|---|
| /home/ | /home |
| /../ | / |
| /home//foo/ | /home/foo |
C. Купить и продать
У вас есть 1000$, которую вы планируете эффективно вложить. Вам даны цены за 1000 кубометров газа за n дней. Можно один раз купить газ на все деньги в день i и продать его в один из последующих дней j, i < j.
Определите номера дней для покупки и продажи газа для получения максимальной прибыли.
В первой строке вводится число дней n (1 ≤ n ≤ 100000).
Во второй строке вводится n чисел — цены за 1000 кубометров газа в каждый из дней. Цена — целое число от 1 до 5000. Дни нумеруются с единицы.
Выведите два числа i и j — номера дней для покупки и продажи газа. Если прибыль получить невозможно, выведите два нуля.
| Ввод | Вывод |
|---|---|
| 6 10 3 5 3 11 9 |
2 5 |
| 4 5 5 5 5 |
0 0 |
D. Разница во времени
Каждые сутки на вокзал прибывает n электричек. По заданному расписанию прибытия электричек определите минимальное время между прибытием двух разных электричек.
В первой строке задано число n (1 ≤ n ≤ 2 × 10^4) — количество электричек.
Во второй строке задано n моментов времени в формате HH:MM (0 ≤ HH ≤ 23, 0 ≤ MM ≤ 59) через пробел.
Выведите одно число — минимальное время в минутах между прибытием двух электричек.
| Ввод | Вывод |
|---|---|
| 2 23:59 00:00 |
1 |
| 3 00:00 23:59 00:00 |
0 |
E. Сломай палиндром
Палиндромом называется строка, которая читается одинаково слева-направо и справа-налево.
В заданной строке-палиндроме необходимо заменить один символ, чтобы она перестала быть палиндромом. При этом полученная строка должна быть лексикографически минимальной.
Строка A лексикографически меньше строки B (той же длины), если на первой различающейся позиции в строке A стоит меньший символ, чем в B. Например, строка adbc меньше строки adca, т.к. первые два символа в строках совпадают, а на третьем месте в строке adbc стоит символ b, который меньше символа c, стоящего на третьей позиции в строке adca.
Вводится строка-палиндром, состоящая из маленьких букв латинского алфавита. Длина строки не превосходит 1000.
Выведите лексикографически минимальную строку, не являющуюяся палиндромом, полученную из исходной строки заменой одного символа.
Если получить такую строку невозможно - выведите пустую строку.
| Ввод | Вывод |
|---|---|
| abba | aaba |
| a |
A. Повторяющееся число
Вам дана последовательность измерений некоторой величины. Требуется определить, повторялась ли какое-либо число, причём расстояние между повторами не превосходило k.
В первой строке задаются два числа n и k (1 ≤ n, k ≤ 10^5).
Во второй строке задаются n чисел, по модулю не превосходящих 10^9.
Выведите YES, если найдется повторяющееся число и расстояние между повторами не превосходит k и NO в противном случае.
| Ввод | Вывод |
|---|---|
| 4 2 1 2 3 1 |
NO |
| 4 1 1 0 1 1 |
YES |
| 6 2 1 2 3 1 2 3 |
NO |
B. Разноцветные палочки
Есть 10 вертикальных палочек, пронумерованных от 0 до 9 и n колец трёх цветов красного «R», зеленого «G» и голубого «B», которые на надеты на палочки. Ваша задача по строке s, кодирующей, где находится каждое из колец определить количество палочек, на которое надеты кольца всех трёх цветов.
Строка представляет из себя последовательность чётной длины, где на нечётных позициях (1, 3, 5 и т.д.) написан цвет кольца, а на чётных позициях (2, 4, 6 и т.д.) — номер палочки, на которую надето кольцо. Таким образом, кольцо номер i имеет цвет s_2i−1 и находится на палочке номер s_2i.
Например, строка «R2G1R1B2G2» кодирует 5 колец:
- Первое кольцо имеет красный цвет и находится на палочке 2;
- Второе кольцо имеет зеленый цвет и находится на палочке 1;
- Третье кольцо имеет красный цвет и находится на палочке 1;
- Четвертое кольцо имеет синий цвет и находится на палочке 2;
- Пятое кольцо имеет зеленый цвет и находится на палочке 2;
Первая строка входных данных — это непустая строка четной длины s (1 ≤ |s| ≤ 1000), состоящая из символов «R», «G» или «B» и цифр от 0 до 9.
Выведите единственное целое число — количество палочек, на которых имеются кольца всех трёх цветов.
| Ввод | Вывод |
|---|---|
| R2G1R1B2G2 | 1 |
| R9G1B0 | 0 |
C. Замена слов
С целью экономии чернил в картридже принтера было принято решение укоротить некоторые слова в тексте. Для этого был составлен словарь слов, до которых можно сокращать более длинные слова. Слово из текста можно сократить, если в словаре найдется слово, являющееся началом слова из текста. Например, если в списке есть слово "лом", то слова из текста "ломбард", "ломоносов" и другие слова, начинающиеся на "лом", можно сократить до "лом".
Если слово из текста можно сократить до нескольких слов из словаря, то следует сокращать его до самого короткого слова.
В первой строке через пробел вводятся слова из словаря, слова состоят из маленьких латинских букв. Гарантируется, что словарь не пуст и количество слов в словаре не превышет 1000, а длина слов — 100 символов.
Во второй строке через пробел вводятся слова текста (они также состоят только из маленьких латинских букв). Количество слов в тексте не превосходит 10^5, а суммарное количество букв в них — 10^6.
Выведите текст, в котором осуществлены замены.
| Ввод | Вывод |
|---|---|
| a b abdafb basrt casds dsasa a |
a b casds dsasa a |
| aa bc aaa a aa aaa bcd abcd |
a aa aa bc abcd |
D. Majority
Majority (в дословном переводе "большинство") — это значение элемента, который в массиве длиной n встречается более чем n / 2 раз. Определите majority массива, если гарантируется, что такой элемент существует.
В первой строке вводится число n (1 ≤ n ≤ 5 × 10^4).
Во второй строке вводится n чисел через пробел, числа не превосходят 10^9 по модулю.
Выведите majority массива.
| Ввод | Вывод |
|---|---|
| 3 1 2 1 |
1 |
| 7 7 5 5 5 5 4 5 |
5 |
| 4 3 3 3 1 |
3 |
E. Удаление чисел
Дан массив a из n чисел. Найдите минимальное количество чисел, после удаления которых попарная разность оставшихся чисел по модулю не будет превышать 1, то есть после удаления ни одно число не должно отличаться от какого-либо другого более чем на 1.
Первая строка содержит одно целое число n (1 ≤ n ≤ 2 * 10^5) — количество элементов массива a.
Вторая строка содержит n целых чисел a_1,a_2,…,a_n (0 ≤ a_i ≤ 10^5) — элементы массива a.
Выведите одно число — ответ на задачу.
| Ввод | Вывод |
|---|---|
| 5 1 2 3 4 5 |
3 |
| 10 1 1 2 3 5 5 2 2 1 5 |
4 |
A. Количество положительных на отрезке
Дана последовательность чисел и запросы вида "определите сколько положительных чисел на отрезке с индексами от L до R".
В первой строке вводится число n (1 ≤ n ≤ 100000) — длина последовательности.
Во второй строке вводится последовательность из n целых чисел, все числа по модулю не превосходят 100000. Нумерация в последовательности начинается с единицы.
В первой строке вводится число q (1 ≤ q ≤ 100000) — количество запросов.
В каждой из следующих q строк вводятся запросы — два индекса l и r (1 ≤ l ≤ r ≤ n)
Для каждого запроса выведите количество положительных на отрезке.
| Ввод | Вывод |
|---|---|
| 5 2 -1 2 -2 3 4 1 1 1 3 2 4 1 5 |
1 2 1 3 |
B. Бумеры и зумеры
Площадка для выгула собак — место, где собираются и общаются люди разных возрастов. На одной из площадок Восточного Бирюлева хозяева собак очень дружны и приглашают друг-друга на день рождения.
Человек x не приглашает на день рождения человека y если выполнено хотя бы одно из условий:
- (Возраст человека y) <= 0.5 * (Возраст человека x) + 7
- (Возраст человека y) > (Возраст человека x)
- (Возраст человека y) > 100 и одновременно с этим (Возраст человека x) < 100
Во всех остальных случаях человек x приглашает человека y на день рождения.
Определите суммарное количество приглашений на день рождения.
В первой строке вводится число n (1 ≤ n ≤ 100000).
Во второй строке вводится n чисел — возраст людей. Возраст находится в промежутке от 1 до 120.
Выведите одно число — суммарное количество приглашений.
| Ввод | Вывод |
|---|---|
| 2 16 16 |
2 |
| 3 17 16 18 |
2 |
| 5 120 25 30 100 105 |
4 |
C. Гирлянды
На завод по изготовлению гирлянд пришел срочный заказ: изготовить как можно больше одинаковых гирлянд, состоящих из n лампочек. На складе завода есть лампочки k различных цветов, цвета занумерованы от 1 до k. Определите, сколько гирлянд сможет изготовить завод и из каких лампочек должна состоять каждая гирлянда.
В первой строке задаются два числа n (1 ≤ n ≤ 40000) и k (1 ≤ k ≤ 50000).
В следующих k строках задается количество лампочек каждого из k цветов. Суммарное количество лампочек на складе не превосходит 2 × 10^9.
В первой строке выведите максимальное количество гирлянд. В следующих n строках выведите описание гирлянды: в каждой строке выведите номер цвета лампочки, находящейся в гирлянде на очередном месте. Если возможных ответов несколько — выведите любой из них.
| Ввод | Вывод |
|---|---|
| 3 4 3 3 2 1 |
2 1 2 3 |
D. Коровы в стойла
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.
В первой строке вводятся числа N (2 < N < 10001) – количество стойл и K (1 < K < N) – количество коров. Во второй строке задаются N натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят 10^9)
Выведите одно число – наибольшее возможное допустимое расстояние.
| Ввод | Вывод |
|---|---|
| 6 3 2 5 7 11 15 20 |
9 |
E. Варим зелья
Богдан учится в Хогвартсе на факультете зельеварения. Завтра ему сдавать свой выпускной проект, но он ничего не успел подготовить. У него есть n ингредиентов, из которых можно сварить зелья. Зелье может состоять либо из одного ингредиента, либо из двух различных. Каждое зелье характеризуется его полезностью. Полезность — это целое число от −10^6 до 10^6. Богдану нужно сварить k зелий так, чтобы их суммарная полезность была максимальной (полезность зелья — это сумма полезностей ингредиентов, из которых оно состоит). Очень важно, чтобы все зелья в проекте были различны. Два зелья считаются различными, если найдется хотя бы один ингредиент, который отсутствует в одном зелье, но присутствует в другом. Помогите Богдану с проектом и подсчитайте максимальную суммарную полезность зелий, которую он может получить.
В первой строке записано два числа n и k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ n*(n+1)/2) - количество ингредиентов и количество зелий, которые нужно приготовить.
В следующей строке заданы n целых чисел ai (−10^6 ≤ a_i ≤ 10^6) — полезность ингредиентов.
Выведите одно целое число — максимальную суммарную полезность зелий.
| Ввод | Вывод |
|---|---|
| 5 5 -2 3 -5 5 1 |
26 |
| 2 1 -1 1 |
1 |
A. Группы и аудитории
В университете есть n аудиторий и m учебных групп. Для каждой аудитории задана её вместимость, а для каждой группы — численность. Группа может заниматься в аудитории только если её численность не превосходит размера аудитории. Определите максимальное количество групп, которые можно рассадить по аудиториям.
В первой строке вводится число n (1 ≤ n ≤ 100000).
Во второй строке вводится n чисел — численность групп. Численность не превосходит 100000.
В третьей строке вводится число m (1 ≤ m ≤ 100000).
В четвертой строке вводится m чисел — вместимость аудиторий. Вместимость не превосходит 100000.
Выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
| 3 3 1 2 2 1 1 |
1 |
| 2 1 2 3 3 2 1 |
2 |
B. Гости
Вася переехал из своего родного города и очень скучает по старым друзьям. К сожалению, Вася снимает маленькую квартиру и одновременно в гости к нему может приехать только один друг.
Каждый друг сказал Васе два числа A и B — с какого по какой день он может приехать в гости. Каждый друг приезжает и уезжает в полдень. Каждый друг может приехать к Васе только один раз и остаться у него на несколько дней. Вася хотел бы, чтобы суммарное количество дней, когда у него в гостях есть кто-нибудь из друзей, было максимальным. Помогите ему определить даты приезда для каждого из друзей так, чтобы они не пересекались (допустима ситуация, что в один день один из друзей приезжает, а другой — уезжает) и суммарное время, когда у Васи в гостях есть кто-то из друзей, было максимальным.
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи.
В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10^9) — возможное время приезда i-го друга.
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.
| Ввод | Вывод |
|---|---|
| 3 1 2 2 4 3 5 |
1 2 3 4 5 5 |
| 3 2 3 1 4 3 5 |
-1 -1 1 4 5 5 |
C. Носки
Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васька, который хочет замерить толщину покрытия стола носками в M точках.
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000).
Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков.
Затем идут M чисел от 1 до L интересующие Васька точки.
Все числа целые.
Выведите M чисел – толщину носкового покрытия в каждой точке.
| Ввод | Вывод |
|---|---|
| 22 18 8 6 11 10 15 3 18 1 19 10 17 1 10 6 16 20 21 1 1 12 21 5 9 1 10 5 10 6 11 5 6 7 11 1 19 13 15 5 22 19 3 8 16 16 21 |
8 0 3 5 11 6 6 2 |
D. Размер поддеревьев
Дано неориентированное дерево, подвешенное за вершину 1. Для каждой вершины подсчитайте, сколько вершин содержится в поддереве, подвешенном за данную вершину.
В первой строке вводится число V — количество вершин (3 ≤ V ≤ 100000)
В следующих V-1 строках записано по два числа: номера соединенных ребром вершин
Выведите V чисел — размеры поддеревьев для каждой из вершин
| Ввод | Вывод |
|---|---|
| 4 1 2 1 3 1 4 |
4 1 1 1 |
| 7 1 2 1 3 1 4 5 1 5 6 5 7 |
7 1 1 1 3 1 1 |
E. Путь к файлу
В операционной системе Xunil информация обо всех файлах и директориях хранится в специальном файле в следующем формате:
emoh
vonavi
a.doc
b.doc
vortep
.bashrc
vorodis
onrop
1.avi
2.avi
rav
bil
Имена файлов, и только они, содержат точку.
Требуется по данному имени файла найти путь к нему. Если таких файлов несколько, вывести путь к файлу, который записан выше.
В первой строке вводится имя искомого файла. Во второй строке вводится общее количество файлов и директорий. В остальных строках вводится информация о файлах и директориях в указанном выше формате (директория или файл, находящиеся внутри другой директории, отделяются одним дополнительным пробелом в начале строки). Количество строк в файле и количество символов в каждой строке не превосходит 100.
Выведите путь к файлу в формате /директория/директория/…/файл
Гарантируется, что такой файл есть.
Гарантируется, что длина строки ответа не превосходит 255.
| Ввод | Вывод |
|---|---|
| 1.avi 12 emoh vonavi a.doc b.doc vortep .bashrc vorodis onrop 1.avi 2.avi rav bil |
/emoh/vorodis/onrop/1.avi |
A. Быки и коровы
Вася и Петя играют в игру «Быки и коровы».
Вася загадал число состоящее из N цифр, а Петя пытается его отгадать. Петя называет число из N цифр, а Вася отвечает, сколько в нем «быков» и «коров».
Количество «быков» вычисляется как количество цифр, стоящих на своем месте.
Количество «коров» вычисляется как количество цифр, которые есть и загаданном Васей числе и в названном Петей, но стоят на разных местах. То есть эти цифры могут быть переставлены таким образом, чтобы стать «Быками».
По загаданному Васей и названному Петей числам определите количество «быков» и «коров».
Загаданное Васей и Петей числа положительные и вводятся по одному в строке. Количество цифр в числах не превосходит 1000. Числа не имеют ведущих нулей.
В первой строке выведите количество «быков», а во второй — «коров».
| Ввод | Вывод |
|---|---|
| 1370 7311 |
1 2 |
В числах 1370 и 7311 есть один «бык» (цифра 3), а также две «коровы» — одна из цифр 1 и цифра 7.
B. Наибольшая подстрока
Дана строка s и число k.
В строке s требуется найти подстроку максимальной длины, в которой все различные символы встречаются не менее k раз.
Первая строка содержит через пробел два целых числа n и k (1 ≤ n, k ≤ 2 * 10^5) — длину строки s и минимальное количество каждого из символов в искомой подстроке.
Вторая строка содержит строку s (|s| = n), состоящую из строчных латинских букв.
Выведите одно число — максимальную длину подстроки, в которой все различные символы встречаются не менее k раз.
| Ввод | Вывод |
|---|---|
| 5 3 aaabb |
3 |
| 6 2 ababbc |
5 |
C. Горы
Недавно Глеб катался в горах. Как известно, горный хребет - такой набор гор с высотами h1…hn, что в нем больше 3 гор и существует такая основная гора с индексом i, что 1 < i < n и h_1 < h_2 < ⋯ < h_i > h_i+1 > ⋯ > h_n. Глеб помнит высоты всех гор, более того он даже помнит, что это был горный хребет, вам требуется вывести индекс любой основной горы.
В первой строчке дается одно число n - количество гор. Затем в следующей строчке дается n чисел: высоты гор h_i. 3 ≤ n ≤ 10_4, 1 ≤ h_I ≤ 10^9.
Вам требуется вывести одно число - индекс любой основной горы.
| Ввод | Вывод |
|---|---|
| 3 1 2 1 |
2 |
| 4 1 2 3 1 |
3 |
D. Удали строку
Дана изначальная строка s. За одну операцию можно:
- Взять непустой префикс строки состоящий из одинаковых букв.
- Взять непустой суффикс строки состоящий из одинаковых букв.
- И префикс, и суффикс должны состоять из одних и тех же букв.
- Префикс и суффикс не должны пересекаться по символам.
- Префикс и суффикс не обязательно равной длины.
- Удалить полученные префикс и суффикс из строки.
Посчитайте длину минимальной строки, которую можно получить из изначальной, после применения некоторого числа данных операций (возможно нуля).
В единственной строке вводится изначальная строка s (1 ≤ ∣s∣ ≤ 10^5). Строка состоит из строчных букв латинского алфавита.
В качестве ответа выведите единственное число — минимальную возможную длину строки после применения некоторого числа операций.
| Ввод | Вывод |
|---|---|
| abba | 0 |
| aboba | 1 |
| zzzaabxxxcazz | 5 |
В первом примере мы сначала выбираем префикс и суффикс "a" и удаляем их, получив строку "bb". Затем выбираем префикс и суффикс "b" и также удаляем их, удалив всю строку.
Во втором примере мы выбираем такие же суффиксы и префиксы: "aboba"→ "bob"→ "o". Можно показать, что единственный символ "o"никак нельзя удалить.
В третьем примере в качестве первой операции можно выбрать например префикс "zz" и суффикс "z".
E. PitCraft
Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.
Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем.
Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. По ландшафту острова определите, сколько блоков воды осталось после дождя в низинах на острове.
В первой строке записано натуральное число N (1 ≤ N ≤ 100000) — количество столбцов, задающих ландшафт острова.
Во второй строке записано N натуральных чисел H_i (1 ≤ H_i ≤ 10^9) — высоты столбцов.
Выведите одно число — количество блоков занятых водой.
| Ввод | Вывод |
|---|---|
| 11 2 5 2 3 6 9 3 1 3 4 6 |
18 |
Пример соответствует рисунку. Черным цветом обозначен камень, серым — вода.
A. USB-порты
Вася подсчитал, что у него есть m гаджетов, которые нужно подключить к USB и всего n USB-портов на компьютере. В ближайшем интернет-магазине продаются разветвители с одного USB на два за c2 рублей и USB-хабы с одного USB на 5 по c5 рублей.
Разветвители и хабы можно подключать друг к другу и к USB-портам компьютера. Определите, какое минимальное количество рублей нужно потратить Васе, чтобы подключить все USB устройства. При этом можно обеспечить возможность подключить и больше m гаджетов, главное минимизировать цену.
В первой строке входных данных записано число n (1 ≤ n ≤ 10^15) — количество USB-портов у компьютера. Во второй строке записано число m (1 ≤ m ≤ 10^15) — количество USB-гаджетов.
В следующих двух строках записаны целые числа c2 и c5 (1 ≤ c2, c5 ≤ 1000)
Выведите одно целое число — минимальное количество рублей, которое надо потратить для покупки необходимого количества разветвителей и хабов.
| Ввод | Вывод |
|---|---|
| 1 3 1 10 |
2 |
| 2 4 9 10 |
10 |
| 3 8 9 10 |
19 |
B. Ровный забор
Вася разобрал на даче старый сарай на n досок одинаковой ширины и толщины, но разной длины. Он решил построить из них забор. Высота забора не имеет для Васи особого значения, главное чтобы он был как можно более ровным. Неровность забора определяется как разница высот между самой короткой и самой длинной доской, использованной для постройки забора. После тщательного измерения оказалось, что k из n досок лишние и их можно не использовать для строительства забора.
Определите минимальную неровность забора, который можно построить из n−k досок.
В первой строке входных данных записаны два числа n и k (0 ≤ k < n ≤ 200000) — количество досок от разбора сарая и количество лишних досок.
Во второй строке записаны n целых чисел l_i (1 ≤ l_i ≤ 10^9) — длины досок.
Выведите единственное целое число — минимальную неровность забора.
| Ввод | Вывод |
|---|---|
| 2 0 15 19 |
4 |
| 7 2 1 11 6 41 15 13 14 |
9 |
В первом примере нет лишних досок, поэтому неровность равна 19−15=4.
Во втором примере можно не использовать первую и четвертую доску для строительства забора.
C. Наследование репозиториев
В системе контроля версий SEHR GUT можно наследовать репозиторий и вносить изменения кода в какую либо версию кода. При этом изменение, внесенное в версию кода, автоматически вносится во все репозитории, из которых был наследован код.
Исходно в системе есть только репозиторий 0. Если от него были пронаследованы репозитории 1 и 2, а от репозитория 1 был наследован репозиторий 3 и изменения были внесены в репозиторий 3, то они также внесутся в репозитории 1 и 0 (но не в репозиторий 2).
Вася хочет внести изменение в один репозиторий таким образом, чтобы они оказались в как можно большем количестве репозиториев.
Во входном файле записано число N — общее количество наследованных репозиториев (1 ≤ N ≤ 100000). Затем следует описание наследования репозиториев: в i-ой строке записано число R_i — номер репозитория, наследником которого является i-ый репозиторий (0 ≤ R_i < i). Начальный репозиторий имеет номер 0.
Выведите номер репозитория, в который нужно внести изменения Васе. Если правильных ответов несколько — выведите любой из них.
| Ввод | Вывод |
|---|---|
| 3 0 0 1 |
3 |
| 8 0 1 2 0 4 5 6 4 |
7 |
Первый пример соответствует ситуации, описанной в условии. Репозитории номер 1 и 2 пронаследованы от репозитория с номером 0. Репозиторий номер 3 пронаследован от репозитория номер 1. Если внести изменение в репозиторий номер 3, то это изменение окажется в репозиториях с номерами 3, 1 и 0.
D. Раскопки и плитка
В городе М есть два любимых занятия: укладывать плитку и проводить непонятные раскопки тротуара. До начала очередного сезона ремонтов на всех тротуарах была уложена плитка. После проведения раскопок тротуар непригоден для использования, пока на нем не уложат плитку. Всего в городе М k тротуаров.
От каждого тротуара без плитки жители города М ежедневно получают одну единицу печали. Если тротуар был раскопан в день a, а плитка на нём была уложена в день b, то жители города получат b−a единиц печали. Плитку можно уложить и в день раскопок, тогда жители получат 0 единиц печали. Тротуар, на котором проводились раскопки может быть снова раскопан и, если на нем была плитка, то она будет сломана.
Все раскопки и укладки плитки должны завершиться до выборов мэра города М, при этом на всех раскопанных тротуарах перед выборами должна быть уложена плитка. Всего работ по раскопкам тротуаров планируется n.
Руководителю компании-подрядчика по укладке плитки попал в руке план раскопок тротуаров с указанием номера тротуара и номера дня, когда тротуар будет раскопан. К сожалению, в бюджете выделены средства только для m укладок плитки на тротуарах. Зато в компании достаточно трудолюбивых работников чтобы уложить любое количество плитки в любой из дней.
Определите, какое наименьшее суммарное количество единиц печали получат жители города М до выборов мэра.
В первой строке вводятся числа k, n и m (1 ≤ k ≤ 1000, 1 ≤ n, m ≤ 100000) — количество тротуаров, количество раскопок и количество укладок плитки, на которые выделены средства в бюджете.
В следующих n строках заданы пары чисел d_i, w_i (1 ≤ d_i ≤ 10^9, 1 ≤ w_i ≤ K) — день, в который будут проведены раскопки и номер тротуара, на которых они будут проводиться. Эти пары заданы в порядке неубывания d_i.
Выведите одно число — минимальное суммарное количество единиц печали. Если до выборов останутся раскопанные тротуары — выведите −1, как признак бесконечной печали жителей.
| Ввод | Вывод |
|---|---|
| 5 4 3 1 2 2 3 2 1 6 2 |
5 |
| 2 4 2 1 1 1 2 3 1 4 2 |
5 |
В первом примере на тротуарах 1 и 3 нужно уложить плитку в день раскопок, а тротуар 2 ремонтируется на шестой день, сразу после проведения раскопок.
E. Поступление с приоритетами
При поступлении в университет абитуриенты указывают список приоритетов образовательных программ, на которые они хотели бы попасть. Все абитуриенты университета были ранжированы и выстроены по рейтингу (рейтинг некоторых абитуриентов может совпадать). На каждой образовательной программе есть контрольные цифры приёма — сколько абитуриентов может быть зачислено на это программу.
Вам необходимо справедливо распределить абитуриентов по программам. Для каждого абитуриента должно выполняться следующее: все места на более желаемых им программах, чем та, на которую он поступил (или на всех программах из списка абитуриента, если он не поступил никуда), заняты людьми с рейтингом выше чем у этого абитуриента.
В первой строке задается два числа: n и k (1 ≤ n, k ≤ 100000) — количество абитуриентов и образовательных программ соответственно.
В следующей строке задается k чисел p_i (1 ≤ p_i ≤ 100000), где p_i — количество мест на программе номер i.
В следующих n строках записаны приоритеты для каждого абитуриента. Описание списка приоритетов состоит из числа r (1 ≤ r ≤ n) — позиции абитуриента в общем рейтинге, числа s (1 ≤ s ≤ N) — количества образовательных программ, на которые хочет поступить абитуриент, и s чисел от 1 до k — номера желаемых для поступления образовательных программ в порядке убывания приоритета. Номера образовательных программ в списке различны. Сумма s для всех абитуриентов не превосходит 10^6.
Для каждого из n абитуриентов выведите номер образовательной программы, на которую он поступит. Если абитуриент не поступит никуда, выведите -1. Если правильных ответов несколько — выведите любой из них.
| Ввод | Вывод |
|---|---|
| 4 2 1 5 3 1 1 1 1 2 2 2 1 2 3 2 1 2 |
-1 2 1 2 |