Условие

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

Чтобы оптимально выбрать место для строительства, Тимофей хочет для каждого участка знать расстояние до ближайшего пустого участка. (Для пустого участка эта величина будет равна нулю –— расстояние до самого себя).

Ваша задача –— помочь Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.

Формат ввода

В первой строке дана длина улицы —– n (1 ≤ n ≤ 106). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один нуль. Номера домов (положительные числа) уникальны и не превосходят 10^9.

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

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

Пример

Условие

Гоша и Тимофей нашли необычный тренажёр для скоростной печати и хотят освоить его. Тренажёр представляет собой поле из клавиш 4× 4, в котором на каждом раунде появляется конфигурация цифр и точек. На клавише написана либо точка, либо цифра от 1 до 9. В момент времени t игрок должен одновременно нажать на все клавиши, на которых написана цифра t. Гоша и Тимофей могут нажать в один момент времени на k клавиш каждый. Если в момент времени t были нажаты все нужные клавиши, то игроки получают 1 балл.

Найдите число баллов, которое смогут заработать Гоша и Тимофей, если будут нажимать на клавиши вдвоём.

Формат ввода

В первой строке дано целое число k (1 ≤ k ≤ 5).

В четырёх следующих строках задан вид тренажёра –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.

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

Выведите единственное число –— максимальное количество баллов, которое смогут набрать Гоша и Тимофей.

Пример

Условие

Даны два списка, нужно вернуть элементы, которые есть в 1-ом списке, но нет во 2-ом. Оценить эффективность своего решения.

Условие

Дан массив целых чисел. Нужно удалить из него нули. Можно использовать только О(1) дополнительной памяти.

Условие

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

Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.

Транспонированная матрица получается из исходной заменой строк на столбцы.

Формат ввода

В первой строке задано число n — количество строк матрицы. Во второй строке задано m — число столбцов, m и n не превосходят 1000. В следующих n строках задана матрица. Числа в ней не превосходят по модулю 1000.

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

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

Пример

Условие

Реализуйте класс 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»

Пример

Условие

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

Дана скобочная последовательность. Нужно определить, правильная ли она.

Будем придерживаться такого определения:

• пустая строка —– правильная скобочная последовательность;
• правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
• правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.

На вход подаётся последовательность из скобок трёх видов: [], (), {}. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.

Формат ввода

На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.

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

Выведите «True» или «False».

Пример

Условие

Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди.

Помогите ему —– реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо поддержать, описаны в формате ввода.

Формат ввода

В первой строке записано одно число — количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:

• push(x) — добавить число x в очередь;
• pop() — удалить число из очереди и вывести на печать;
• peek() — напечатать первое число в очереди;
• size() — вернуть размер очереди; При превышении допустимого размера очереди нужно вывести «error». При вызове операций pop() или peek() для пустой очереди нужно вывести «None».

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

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

Пример

Условие

Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:

• get() — вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести «error».
• put(x) — добавить число x в очередь
• size() — вывести текущий размер очереди

Формат ввода

В первой строке записано количество команд n — целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.

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

Выведите ответ на каждый запрос по одному в строке.

Пример

Условие

У Тимофея было n стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту.

Определите, сколько кода напишет следующий стажёр. Решение должно быть реализовано рекурсивно.

Формат ввода

На вход подаётся n — целое число в диапазоне от 0 до 32.

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

Нужно вывести, сколько кода напишет следующий стажёр.

Пример

Условие

Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы 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) ничего выводить не надо.

Пример

Условие

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

В постфиксной нотации операнды расположены перед знаками операций.

Пример:

10 2 4 *

означает 10 - 2 * 4 и равно 2

Разберём последний пример подробнее:

Знак * стоит сразу после чисел 2 и 4, значит к ним нужно применить операцию, которую этот знак обозначает, то есть перемножить эти два числа. В результате получим 8.

После этого выражение приобретёт вид:

10 8 -

Операцию «минус» нужно применить к двум идущим перед ней числам, то есть 10 и 8. В итоге получаем 2.

Рассмотрим алгоритм более подробно. Для его реализации будем использовать стек.

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

1. Обработка входного символа: Если на вход подан операнд, он помещается на вершину стека. Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека.
2. Если входной набор символов обработан не полностью, перейти к шагу 1.
3. После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент.

Замечание про отрицательные числа и деление: в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.

Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.

В текущей задаче гарантируется, что деления на отрицательное число нет.

Формат ввода

В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.

На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.

Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.

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

Выведите единственное число — значение выражения.

Пример

Условие

Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.

Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.

Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:

• (())
• ()()

(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).

Формат ввода

На вход функция принимает n — целое число от 0 до 10.

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

Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.

Пример

Условие

На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв.

Примерно так: 2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'

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

Формат ввода

На вход подается строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.

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

Выведите все возможные комбинации букв через пробел.

Пример

Условие

Гоша любит играть в игру «Подпоследовательность»: даны 2 строки, и нужно понять, является ли первая из них подпоследовательностью второй.

Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.

Формат ввода

В первой строке записана строка s.

Во второй —- строка t.

Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки могут быть пустыми.

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

Выведите True, если s является подпоследовательностью t, иначе —– False.

Пример

Условие

К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.

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

Каждый ребёнок может взять не больше одного печенья.

Формат ввода

В первой строке записано n —– количество детей.

Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.

В следующей строке записано число m –— количество печенек.

Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.

Оба числа n и m не превосходят 10000.

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

Нужно вывести одно число –— количество детей, которые останутся довольными

Пример

Условие

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

Напомним, что из трёх отрезков с длинами 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, –— длины отрезков.

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

Нужно вывести одно число —– наибольший периметр треугольника.

Пример

Условие

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

Примечание: попробуйте решить задачу за один проход по массиву!

Формат ввода

В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.

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

Нужно вывести в строку через пробел цвета предметов в правильном порядке.

Пример

Условие

Вечером ребята решили поиграть в игру «Большое число».

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

Формат ввода

В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.

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

Нужно вывести самое большое число, которое можно составить из данных чисел.

Пример

Условие

Чтобы выбрать самый лучший алгоритм для решения задачи, Гоша продолжил изучать разные сортировки. На очереди сортировка пузырьком — https://ru.wikipedia.org/wiki/Сортировка_пузырьком

Её алгоритм следующий (сортируем по неубыванию):

На каждой итерации проходим по массиву, поочередно сравнивая пары соседних элементов. Если элемент на позиции i больше элемента на позиции i + 1, меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива. Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован. После не более чем n – 1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.

Помогите Гоше написать код алгоритма.

Формат ввода

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

Обратите внимание, что считывать нужно только 2 строки: значение n и входной массив.

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

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

Пример

Условие

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

Формат ввода

Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.

В примерах: В первой строке записано число n — длина массива. Во второй строке записано положительное число k — искомый элемент. Далее в строку через пробел записано n натуральных чисел – элементы массива.

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

Функция должна вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть − 1. Изменять массив нельзя.

Пример

Условие

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

Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач P_i и размер штрафа F_i. Штраф начисляется за неудачные попытки и время, затраченное на задачу.

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

Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").

Как работает in-place quick sort

Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.

Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.

Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся.

Формат ввода

В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами:

• уникальным логином (строкой из маленьких латинских букв длиной не более 20)
• числом решённых задач P_i
• штрафом Fi

Fi и Pi — целые числа, лежащие в диапазоне от 0 до 10^9.

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

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

Пример

Условие

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

Формат ввода

В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.

Во второй строке дано число m (1 ≤ m ≤ 109) –— модуль.

В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.

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

Выведите целое неотрицательное число –— хеш заданной строки.

Пример

Условие

Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было.

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

Формат ввода

В задаче единственный тест без ввода

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

Отправьте две строки, по одной в строке. Строки могут состоять только из маленьких латинских букв и не должны превышать в длину 1000 знаков каждая. Код отправлять не требуется. Строки из примера использовать нельзя.

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

• ezhgeljkablzwnvuwqvp
• gbpdcvkumyfxillgnqrv

Условие

Алла не остановилась на достигнутом –— теперь она хочет научиться быстро вычислять хеши произвольных подстрок данной строки. Помогите ей!

На вход поступают запросы на подсчёт хешей разных подстрок. Ответ на каждый запрос должен выполняться за O(1). Допустимо в начале работы программы сделать предподсчёт для дальнейшей работы со строкой.

В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.

Формат ввода

В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш. Во второй строке дано число m (1 ≤ m ≤ 107) –— модуль. В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.

В четвертой строке дано число запросов t –— натуральное число от 1 до 105. В каждой из следующих t строк записаны через пробел два числа l и r –— индексы начала и конца очередной подстроки. (1 ≤ l ≤ r ≤ |s|).

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

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

Пример

Условие

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

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

Формат ввода

В первой строке даётся натуральное число n, не превосходящее 10 000 –— количество записей в логе.

В следующих n строках —– названия кружков.

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

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

Пример

Условие

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

Формат ввода

Одна строка, состоящая из строчных латинских букв. Длина строки не превосходит 10 000.

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

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

Пример

Условие

Тимофей пишет свою поисковую систему.

Имеется n документов, каждый из которых представляет собой текст из слов. По этим документам требуется построить поисковый индекс. На вход системе будут подаваться запросы. Запрос —– некоторый набор слов. По запросу надо вывести 5 самых релевантных документов.

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

Сортировка документов на выдаче производится по убыванию релевантности. Если релевантности документов совпадают —– то по возрастанию их порядковых номеров в базе (то есть во входных данных).

Формат ввода

В первой строке дано натуральное число n —– количество документов в базе (1 ≤ n ≤ 104).

Далее в n строках даны документы по одному в строке. Каждый документ состоит из нескольких слов, слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Длина одного текста не превосходит 1000 символов. Текст не бывает пустым.

В следующей строке дано число запросов —– натуральное число m (1 ≤ m ≤ 104). В следующих m строках даны запросы по одному в строке. Каждый запрос состоит из одного или нескольких слов. Запрос не бывает пустым. Слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Число символов в запросе не превосходит 100.

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

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

Пример

Условие

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

Хеш-таблица должна поддерживать следующие операции:

• put key value —– добавление пары ключ-значение. Если заданный ключ уже есть в таблице, то соответствующее ему значение обновляется.
• get key –— получение значения по ключу. Если ключа нет в таблице, то вывести «None». Иначе вывести найденное значение.
• delete key –— удаление ключа из таблицы. Если такого ключа нет, то вывести «None», иначе вывести хранимое по данному ключу значение и удалить ключ.

В таблице хранятся уникальные ключи.

Требования к реализации:

• Нельзя использовать имеющиеся в языках программирования реализации хеш-таблиц (std::unordered_map в С++, dict в Python, HashMap в Java, и т. д.)
• Число хранимых в таблице ключей не превосходит 10^5.
• Разрешать коллизии следует с помощью метода цепочек или с помощью открытой адресации.
• Все операции должны выполняться за O(1) в среднем.
• Поддерживать рехеширование и масштабирование хеш-таблицы не требуется.
• Ключи и значения, id сотрудников и их зарплата, —– целые числа. Поддерживать произвольные хешируемые типы не требуется.

Формат ввода

В первой строке задано общее число запросов к таблице n (1≤ n≤ 106).

В следующих n строках записаны запросы, которые бывают трех видов –— get, put, delete —– как описано в условии.

Все ключи и значения –— целые неотрицательные числа, не превосходящие 10^9.

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

На каждый запрос вида get и delete выведите ответ на него в отдельной строке.

Пример

Условие

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

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть максимальное значение яркости в узле дерева.

Условие

Гоша повесил на стену гирлянду в виде бинарного дерева, в узлах которого находятся лампочки. У каждой лампочки есть своя яркость. Уровень яркости лампочки соответствует числу, расположенному в узле дерева. Помогите Гоше найти самую яркую лампочку в гирлянде, то есть такую, у которой яркость наибольшая.

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть True, если дерево сбалансировано в соответствии с критерием из условия, иначе - False.

Условие

Гоша и Алла играют в игру «Удивительные деревья». Помогите ребятам определить, является ли дерево, которое им встретилось, деревом-анаграммой? Дерево называется анаграммой, если оно симметрично относительно своего центра

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть True если дерево является анаграммой. Иначе - False.

Условие

Гоше на день рождения подарили два дерева. Тимофей сказал, что они совершенно одинаковые. Но, по мнению Гоши, они отличаются. Помогите разрешить этот философский спор!

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть True если деревья являются близнецами. Иначе - False.

Условие

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

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть True, если дерево является деревом поиска, иначе - False.

Условие

Алла хочет побывать на разных островах архипелага Алгосы. Она составила карту. Карта представлена в виде дерева: корень обозначает центр архипелага, узлы –— другие острова. А листья —– это дальние острова, на которые Алла хочет попасть. Помогите Алле определить максимальное число островов, через которые ей нужно пройти для совершения одной поездки от стартового острова до места назначения, включая начальный и конечный пункты.

Формат ввода

На вход подается корень дерева.

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

Функция должна вернуть число, равное максимальному числу островов в пути (включая начальный и конечный пункты).

Условие

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

Формат ввода

В единственной строке задано число n. Оно не превосходит 20.

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

Нужно вывести число, равное количеству различных деревьев поиска, в узлах которых могут быть размещены числа от 1 до n включительно.

Условие

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

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

Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач P_i и размер штрафа F_i. Штраф начисляется за неудачные попытки и время, затраченное на задачу.

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

Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").

Как работает in-place quick sort

Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.

Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.

Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся.

Формат ввода

В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами:

• уникальным логином (строкой из маленьких латинских букв длиной не более 20)
• числом решённых задач P_i
• штрафом Fi

Fi и Pi — целые числа, лежащие в диапазоне от 0 до 10^9.

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

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

Пример

Условие

Дано бинарное дерево поиска, в котором хранятся ключи. Ключи — уникальные целые числа. Найдите вершину с заданным ключом и удалите её из дерева так, чтобы дерево осталось корректным бинарным деревом поиска. Если ключа в дереве нет, то изменять дерево не надо. На вход вашей функции подаётся корень дерева и ключ, который надо удалить. Функция должна вернуть корень изменённого дерева. Сложность удаления узла должна составлять O(h), где h –— высота дерева. Создавать новые вершины (вдруг очень захочется) нельзя.

Формат ввода

Ключи дерева – натуральные числа. В итоговом решении не надо определять свою структуру/свой класс, описывающий вершину дерева.

Условие

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

Помогите Алле написать программу, которая по списку рёбер графа будет строить его список смежности.

Формат ввода

В первой строке дано число вершин n (1 ≤ n ≤ 100) и число ребер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.

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

Выведите информацию о рёбрах, исходящих из каждой вершины.

В строке i надо написать число рёбер, исходящих из вершины i, а затем перечислить вершины, в которые ведут эти рёбра –— в порядке возрастания их номеров.

Пример

Условие

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

Формат ввода

В первой строке дано число вершин n (1 ≤ n ≤ 100) и число ребер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.

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

Выведите матрицу смежности n на n. На пересечении i-й строки и j-го столбца стоит единица, если есть ребро, ведущее из i в j.

Пример

Условие

Задан неориентированный граф. Обойдите с помощью DFS все вершины, достижимые из заданной вершины s, и выведите их в порядке обхода, если начинать обход из s.

Формат ввода

В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (0 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n). В графе нет петель и кратных рёбер.

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

Выведите вершины в порядке обхода, считая что при запуске от каждой конкретной вершины её соседи будут рассматриваться в порядке возрастания (то есть если вершина 2 соединена с 1 и 3, то сначала обход пойдёт в 1, а уже потом в 3).

Пример

Условие

Задан неориентированный граф. Обойдите с помощью BFS все вершины, достижимые из заданной вершины s, и выведите их в порядке обхода, если начинать обход из s.

Формат ввода

В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (0 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n). В графе нет петель и кратных рёбер.

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

Выведите вершины в порядке обхода, считая что при запуске от каждой конкретной вершины её соседи будут рассматриваться в порядке возрастания (то есть если вершина 2 соединена с 1 и 3, то сначала обход пойдёт в 1, а уже потом в 3).

Пример

Условие

Вам дан неориентированный граф. Найдите его компоненты связности.

Формат ввода

В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (0 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n). В графе нет петель и кратных рёбер.

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

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

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

Пример

Условие

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

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

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

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

Формат ввода

В первой строке даны числа n (1 ≤ n ≤ 100) и m (0 ≤ m ≤ n (n-1)/2). В следующих m строках описаны мосты. Каждый мост задаётся номерами двух достопримечательностей 1 ≤ u, v ≤ n и длиной дороги 1 ≤ L ≤ 103.

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

Выведите матрицу n × n кратчайших расстояний. На пересечении i-й строки и j-го столбца должно стоять расстояние от i-й до j-й достопримечательности. Если между какой-то парой нет пути, то в соответствующей клетке поставьте -1.

Пример

Условие

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

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

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

Формат ввода

В первой строке дано количество вершин n и ребер m графа (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100000).

В каждой из следующих m строк заданы рёбра в виде троек чисел u, v, w. u и v — вершины, которые соединяет это ребро. w — его вес ( 1 ≤ u, v ≤ n, 0 ≤ w ≤ 10000). В графе могут быть петли и кратные ребра. Граф может оказаться несвязным.

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

Если максимальное остовное дерево существует, то выведите его вес. Иначе (если в графе несколько компонент связности) выведите фразу «Oops! I did it again».

Пример

Условие

В стране X есть n городов, которым присвоены номера от 1 до n. Столица страны имеет номер n. Между городами проложены железные дороги.

Однако дороги могут быть двух типов по ширине полотна. Любой поезд может ездить только по одному типу полотна. Условно один тип дорог помечают как R, а другой как B. То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет по этому маршруту проехать. От одного города до другого можно проехать только по маршруту, состоящему исключительно из дорог типа R или только из дорог типа B.

Но это ещё не всё. По дорогам страны X можно двигаться только от города с меньшим номером к городу с большим номером. Это объясняет большой приток жителей в столицу, у которой номер n.

Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B. Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бОльшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя. Выясните, является ли данная вам карта оптимальной.

Формат ввода

В первой строке дано число n (1 ≤ n ≤ 5000) — количество городов в стране. Далее задана карта железных дорог в следующей формате.

Карта задана n-1 строкой. В i-й строке описаны дороги из города i в города i+1, i+2, ..., n. В строке записано n - i символов, каждый из которых либо R, либо B. Если j-й символ строки i равен «B», то из города i в город i + j идет дорога типа «B». Аналогично для типа «R».

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

Выведите «YES», если карта оптимальна, и «NO» в противном случае.

Пример

Условие

Рита хочет попробовать поиграть на бирже. Но для начала она решила потренироваться на исторических данных.

Даны стоимости акций в каждый из n дней. В течение дня цена акции не меняется. Акции можно покупать и продавать, но только по одной штуке в день. В один день нельзя совершать более одной операции (покупки или продажи). Также на руках не может быть более одной акции в каждый момент времени.

Помогите Рите выяснить, какую максимальную прибыль она могла бы получить.

Формат ввода

В первой строке записано количество дней n —– целое число в диапазоне от 0 до 10 000.

Во второй строке через пробел записано n целых чисел в диапазоне от 0 до 1000 –— цены акций.

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

Выведите число, равное максимально возможной прибыли за эти дни.

Пример

Условие

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

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

Формат ввода

В первой строке задано число занятий. Оно не превосходит 1000. Далее для каждого занятия в отдельной строке записано время начала и конца, разделённые пробелом. Время задаётся одним целым числом h, если урок начинается/заканчивается ровно в h часов. Если же урок начинается/заканчивается в h часов m минут, то время записывается как h.m. Гарантируется, что каждое занятие начинается не позже, чем заканчивается. Указываются только значащие цифры.

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

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

Пример

Условие

Гуляя по одному из островов Алгосского архипелага, Гоша набрёл на пещеру, в которой лежат кучи золотого песка. К счастью, у Гоши есть с собой рюкзак грузоподъёмностью до M килограмм, поэтому он может унести с собой какое-то ограниченное количество золота.

Всего золотых куч n штук, и все они разные. В куче под номером i содержится mi килограммов золотого песка, а стоимость одного килограмма — ci алгосских франков.

Помогите Гоше наполнить рюкзак так, чтобы общая стоимость золотого песка в пересчёте на алгосские франки была максимальной.

Формат ввода

В первой строке задано целое число M — грузоподъёмность рюкзака Гоши (0 ≤ M ≤ 108). Во второй строке дано количество куч с золотым песком — целое число n (1 ≤ n ≤ 105).

В каждой из следующих n строк описаны кучи: i-ая куча задаётся двумя целыми числами ci и mi, записанными через пробел (1 ≤ ci ≤ 107, 1 ≤ mi ≤ 108).

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

Выведите единственное число —– максимальную сумму (в алгосских франках), которую Гоша сможет вынести из пещеры в своём рюкзаке.

Пример

Условие

Гоша практикуется в динамическом программировании — он хочет быстро считать числа Фибоначчи.

Формат ввода

В единственной строке дано целое число n (0 ≤ n ≤ 106).

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

Вычислите значение Fn по модулю 10^9 + 7 и выведите его.

Пример

Условие

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

Гоша не хочет проиграть, поэтому просит вас посчитать количество способов допрыгать от первой ступеньки до n-й. Изначально все стоят на первой ступеньке.

Формат ввода

В единственной строке даны два числа — n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n).

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

Выведите количество способов по модулю 10^9 + 7.

Пример

Условие

Тимофей пошёл снять деньги в банкомат. Ему нужно m франков. В банкомате в бесконечном количестве имеются купюры различных достоинств. Всего различных достоинств n. Купюр каждого достоинства можно взять бесконечно много. Нужно определить число способов, которыми Тимофей сможет набрать нужную сумму.

Формат ввода

В первой строке записано целое число m — сумма, которую нужно набрать. Во второй строке n — количество монет в банкомате. Оба числа не превосходят 300. Далее в третьей строке записано n уникальных натуральных чисел, каждое в диапазоне от 1 до 1000 –– достоинства купюр.

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

Нужно вывести число способов, которым Тимофей сможет набрать нужную сумму.

Пример

Условие

Расстоянием Левенштейна между двумя строками s и t называется количество атомарных изменений, с помощью которых можно одну строку превратить в другую. Под атомарными изменениями подразумеваются: удаление одного символа, вставка одного символа, замена одного символа на другой.

Найдите расстояние Левенштейна для предложенной пары строк.

Выведите единственное число — расстояние между строками.

Формат ввода

В первой строке дана строка s, во второй — строка t. Длины обеих строк не превосходят 1000. Строки состоят из маленьких латинских букв.

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

Выведите единственное число — расстояние между строками.

Пример

Условие

На Алгосах устроили турнир по настольному теннису. Гоша выиграл n партий, получив при этом некоторое количество очков за каждую из них.

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

Формат ввода

В первой строке записано целое число n (0 ≤ n ≤ 300) –— количество выигранных партий.

Во второй строке через пробел записано n целых неотрицательных чисел, каждое из которых не превосходит 300 –— заработанные в партиях очки.

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

Нужно вывести True, если произвести такое разбиение возможно, иначе —– False

Пример

Условие

В некоторых языках предложения пишутся и читаются не слева направо, а справа налево.

Вам под руку попался странный текст –— в нём обычный (слева направо) порядок букв в словах. А вот сами слова идут в противоположном направлении. Вам надо преобразовать текст так, чтобы слова в нём были написаны слева направо.

Формат ввода

На ввод подаётся строка, состоящая из слов, разделённых пробелами (один пробел между соседними словами). Всего слов не более 1000, длина каждого из них —– от 1 до 100 символов. Слова состоят из строчных букв английского алфавита.

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

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

Пример

Условие

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

Из данной строки s путём удаления и перестановки букв надо получить палиндром максимальной длины. Среди всех таких палиндромов надо получить лексикографически минимальный. Количество удалений и перестановок символов может быть любым.

Формат ввода

В единственной строке дана строка s. Длина строки |s| ≤ 105. Строка состоит из строчных букв английского алфавита.

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

Выведите полученный палиндром. Заметьте, что ответ определяется однозначно.

Пример

Условие

Найдите наибольший по длине общий префикс нескольких строк.

Формат ввода

В первой строке дано число n (1 ≤ n ≤ 105). Затем по одной на строке даны n строк, каждая не превышает 105 в длину. Суммарная длина всех строк не превосходит 107.

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

Выведите единственное число — длину наибольшего префикса всех данных строк.

Пример

Условие

Напишите программу, которая будет заменять в тексте все вхождения строки s на строку t. Гарантируется, что никакие два вхождения шаблона s не пересекаются друг с другом.

Формат ввода

В первой строке дан текст —– это строка из строчных букв английского алфавита, длина которой не превышает 106.

Во второй строке записан шаблон s, вхождения которого будут заменены.

В третьей строке дана строка t, которая будет заменять вхождения.

Обе строки s и t состоят из строчных букв английского алфавита, длина каждой строки не превосходит 105. Размер итоговой строки не превосходит 2⋅ 106.

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

В единственной строке выведите результат всех замен — текст, в котором все вхождения s заменены на t.

Пример

Условие

Вам даны строки в запакованном виде. Определим запакованную строку (ЗС) рекурсивно. Строка, состоящая только из строчных букв английского алфавита является ЗС. Если A и B —– корректные ЗС, то и AB является ЗС. Если A —– ЗС, а n — однозначное натуральное число, то n[A] тоже ЗС. При этом запись n[A] означает, что при распаковке строка A записывается подряд n раз. Найдите наибольший общий префикс распакованных строк и выведите его (в распакованном виде).

Иными словами, пусть сложение —– это конкатенация двух строк, а умножение строки на число — повтор строки соответствующее число раз. Пусть функция f умеет принимать ЗС и распаковывать её. Если ЗС D имеет вид D=AB, где A и B тоже ЗС, то f(D) = f(A) + f(B). Если D=n[A], то f(D) = f(A) × n.

Формат ввода

В первой строке записано число n (1 ≤ n ≤ 1000) –— число строк.

Далее в n строках записаны запакованные строки. Гарантируется, что эти строки корректны, то есть удовлетворяют указанному рекурсивному определению. Длина строк после распаковки не превосходит 10^5.

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

Выведите наибольший общий префикс распакованных строк.

Пример

Условие

Вася готовится к экзамену по алгоритмам и на всякий случай пишет шпаргалки.

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

Более формально: дан текст T и набор строк s1, ... ,sn. Надо определить, представим ли T как sk1sk2...skr, где где ki — индексы строк. Индексы могут повторяться. Строка si может встречаться в разбиении текста T произвольное число раз. Можно использовать не все строки для разбиения. Строки могут идти в любом порядке.

Формат ввода

В первой строке дан текст T, который надо разбить на слова. Длина T не превосходит 10^5. Текст состоит из строчных букв английского алфавита.

Во второй строке записано число допустимых к использованию слов 1 ≤ n ≤ 100.

В последующих n строках даны сами слова, состоящие из маленьких латинских букв. Длина каждого слова не превосходит 100.

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

Выведите «YES», если текст можно разбить на слова из данного словаря, или «NO» в ином случае.

Пример

1. LeetCode — самый большой банк задач с собеседований. Любая задача, которая когда-либо задавалась на алгоритмическом собеседовании, наверняка есть тут. Задачи можно фильтровать по компаниям, тегам и сложности. Советуем заходить сюда регулярно — и чтобы готовиться к интервью, и чтобы поддерживать навык решения задач.
   
2. Видеолекции Павла Маврина - Подойдут как для лучшего понимания тем из курса, так и для изучения новых, в том числе весьма продвинутых.

1. Книга «Карьера программиста» или в оригинале “Cracking the Coding Interview”. Содержит много советов про подготовку к алгоритмическим собеседованиям. Будет полезна в дополнение к урокам 1 спринта нашего курса.
   
2. InterviewBit — другой хороший ресурс с задачами для собеседований. Не нужно возиться с фильтрами, можно пройти по всем интересующим темам.
   
3. Pramp — сервис для проведения peer-to-peer пробных интервью на английском языке. Вам назначается случайный человек в пару и вы собеседуете его, а потом он — вас. Очень полезно попробовать себя в роли не только собеседуемого, но и собеседущего — это поможет вам лучше почувствовать, как интервьюер оценивает кандидата. Очень рекомендуем в процессе подготовки к алгоритмическим интервью на английском языке.
   
4. Как проходят алгоритмические секции на собеседованиях в Яндекс — статья про подготовку к собеседованиям от Яндекса.
   
5. Вебинар «Открытое алгоритмическое собеседование». Можно посмотреть перед тем, как вы пойдёте на первое пробное интервью, чтобы прочувствовать формат в динамике.
   
6. Coding Interview University — самый полный гайд по подготовке к собеседованиям. Настолько полный, что на его прохождение потребуется очень много времени: автор говорит о 8–12 часов в день в течение 8 месяцев. Поэтому оставляем его тут на случай, если вы настроены максимально решительно.
   

1. Книга «Алгоритмы. Построение и анализ» — классический труд по теории алгоритмов и структур данных. Много тем, включая математику, но большой объём и академический стиль изложения.
   
2. Codeforces — портал, посвящённый спортивному программированию. Мы рекомендуем его в контексте предыдущего пункта: тут вы сможете найти задачи на отработку тем, изученных в учебниках.
   

1. Google Code Jam — ежегодное соревнование от Google, проходит в несколько этапов от простых отборочных до финала с очень сложными задачами. Попадание в Round 2 даёт хорошие шансы на то, чтобы с вами связался рекрутер Google. Если вы студент, то рекомендуем также поучаствовать в более простом Kick Start.
   
2. Facebook Hacker Cup — аналогичное соревнование от Facebook.
   
3. Yandex Cup — соревнование от Яндекса. В отличие от вышеперечисленных, проводится не только по алгоритмам, но и по другим направлениям.
   
4. Advent of Code — это не столько соревнование, сколько возможность порешать и обсудить задачи с друзьями или коллегами.