Решение задач по алгоритмам на языках Python и Go.
Ближайший ноль (nearest_zero.py)
Улица, на которой хочет жить Тимофей, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке либо уже построен дом, либо участок пустой. Тимофей ищет место для строительства своего дома. Он очень общителен и не хочет жить далеко от других людей, живущих на этой улице.
Чтобы оптимально выбрать место для строительства, Тимофей хочет для каждого участка знать расстояние до ближайшего пустого участка. (Для пустого участка эта величина будет равна нулю –— расстояние до самого себя).
Ваша задача –— помочь Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.
В первой строке дана длина улицы —– n (1 ≤ n ≤ 106). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один нуль. Номера домов (положительные числа) уникальны и не превосходят 10^9.
Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.
| Ввод | Вывод |
|
5 0 1 4 9 0 |
0 1 2 1 0 |
Ловкость рук (juggle.py)
Гоша и Тимофей нашли необычный тренажёр для скоростной печати и хотят освоить его. Тренажёр представляет собой поле из клавиш 4× 4, в котором на каждом раунде появляется конфигурация цифр и точек. На клавише написана либо точка, либо цифра от 1 до 9. В момент времени t игрок должен одновременно нажать на все клавиши, на которых написана цифра t. Гоша и Тимофей могут нажать в один момент времени на k клавиш каждый. Если в момент времени t были нажаты все нужные клавиши, то игроки получают 1 балл.
Найдите число баллов, которое смогут заработать Гоша и Тимофей, если будут нажимать на клавиши вдвоём.
В первой строке дано целое число k (1 ≤ k ≤ 5).
В четырёх следующих строках задан вид тренажёра –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.
Выведите единственное число –— максимальное количество баллов, которое смогут набрать Гоша и Тимофей.
| Ввод | Вывод |
|
3 1231 2..2 2..2 2..2 |
2 |
Разница списков (find_missing.py)
Даны два списка, нужно вернуть элементы, которые есть в 1-ом списке, но нет во 2-ом. Оценить эффективность своего решения.
Удаляем нули (delete_zero.py)
Дан массив целых чисел. Нужно удалить из него нули. Можно использовать только О(1) дополнительной памяти.
Мониторинг (monitoring.py)
Алла получила задание, связанное с мониторингом работы различных серверов. Требуется понять, сколько времени обрабатываются определённые запросы на конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца соответствуют идентификатору запроса, а номер строки — идентификатору сервера. Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей исправить баг.
Есть матрица размера 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 |
Стек - MaxEffective (stack_max_effective.py)
Реализуйте класс 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 |
Скобочная последовательность (brackets.py)
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
- пустая строка —– правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
- правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}.
Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True,
если последовательность правильная, а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.
Выведите «True» или «False».
| Ввод | Вывод |
| {[()]} | True |
| {} | True |
Ограниченная очередь (queue_sized.py)
Астрологи объявили день очередей ограниченного размера.
Тимофею нужно написать класс 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 |
Списочная очередь (queue_list.py)
Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:
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 |
Рекурсивные числа Фибоначчи (fibonacci.py)
У Тимофея было n стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту.
Определите, сколько кода напишет следующий стажёр. Решение должно быть реализовано рекурсивно.
На вход подаётся n — целое число в диапазоне от 0 до 32.
Нужно вывести, сколько кода напишет следующий стажёр.
| Ввод | Вывод |
| 3 | 3 |
| 0 | 1 |
| 1 | 1 |
Дек (deck.py)
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом.
Методы 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 |
Калькулятор (polsk_calc.py)
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример:
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 |
Генератор скобок (brackets_generator.py)
Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
- (())
- ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
На вход функция принимает n — целое число от 0 до 10.
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
| Ввод | Вывод |
|
3 |
((())) (()()) (())() ()(()) ()()() |
Комбинации (combinations.py)
На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв.
Примерно так: 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 |
Подпоследовательность (subsequence.py)
Гоша любит играть в игру «Подпоследовательность»: даны 2 строки, и нужно понять, является ли первая из них подпоследовательностью второй.
Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.
В первой строке записана строка s.
Во второй —- строка t.
Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки могут быть пустыми.
Выведите True, если s является подпоследовательностью t, иначе —– False.
| Ввод | Вывод |
|
abc ahbgdcu |
True |
Печеньки (crackers.py)
К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.
Но не всё так просто. Печенья могут быть разного размера. А у каждого ребёнка есть фактор жадности —– минимальный размер печенья, которое он возьмёт. Нужно выяснить, сколько ребят останутся довольными в лучшем случае, когда они действуют оптимально.
Каждый ребёнок может взять не больше одного печенья.
В первой строке записано n —– количество детей.
Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.
В следующей строке записано число m –— количество печенек.
Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.
Оба числа n и m не превосходят 10000.
Нужно вывести одно число –— количество детей, которые останутся довольными
| Ввод | Вывод |
|
2 1 2 3 2 1 3 |
2 |
Периметр треугольника (triangles.py)
Перед сном Рита решила поиграть в игру на телефоне. Дан массив целых чисел, в котором каждый элемент обозначает длину стороны треугольника. Нужно определить максимально возможный периметр треугольника, составленного из сторон с длинами из заданного массива. Помогите Рите скорее закончить игру и пойти спать.
Напомним, что из трёх отрезков с длинами 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 |
Гардероб (closet.py)
Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом —– жёлтого, и в конце —– малинового. Помогите Рите справиться с этой задачей.
Примечание: попробуйте решить задачу за один проход по массиву!
В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.
Нужно вывести в строку через пробел цвета предметов в правильном порядке.
| Ввод | Вывод |
|
7 0 2 1 2 0 0 1 |
0 0 0 1 1 2 2 |
Большое число (big_number.py)
Вечером ребята решили поиграть в игру «Большое число».
Даны числа. Нужно определить, какое самое большое число можно из них составить.
В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.
Нужно вывести самое большое число, которое можно составить из данных чисел.
| Ввод | Вывод |
|
3 15 56 2 |
56215 |
Пузырёк (bubble.py)
Чтобы выбрать самый лучший алгоритм для решения задачи, Гоша продолжил изучать разные сортировки. На очереди сортировка пузырьком — 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 |
Поиск в сломанном массиве (broken_search.py)
Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее нужно обеспечить возможность находить в нем элемент за O(log n). Можно предполагать, что в массиве только уникальные элементы.
Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.
В примерах: В первой строке записано число n — длина массива. Во второй строке записано положительное число k — искомый элемент. Далее в строку через пробел записано n натуральных чисел – элементы массива.
Функция должна вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть − 1. Изменять массив нельзя.
| Ввод | Вывод |
|
9 5 19 21 100 101 1 4 5 7 12 |
6 |
Эффективная быстрая сортировка (efficient_quick_sort.py)
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач 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.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|
5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
Полиномиальный хеш (polynomial_hash.py)
Алле очень понравился алгоритм вычисления полиномиального хеша. Помогите ей написать функцию, вычисляющую хеш строки s. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.
Во второй строке дано число m (1 ≤ m ≤ 109) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.
Выведите целое неотрицательное число –— хеш заданной строки.
| Ввод | Вывод |
|
123 100003 a |
97 |
Сломай меня (crash_polynomial_hash.py)
Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было.
В этой задаче вам надо будет лишь найти две различные строки, которые для заданной хеш-функции будут давать одинаковое значение.
В задаче единственный тест без ввода
Отправьте две строки, по одной в строке. Строки могут состоять только из маленьких латинских букв и не должны превышать в длину 1000 знаков каждая. Код отправлять не требуется. Строки из примера использовать нельзя.
Пример вывода:
- ezhgeljkablzwnvuwqvp
- gbpdcvkumyfxillgnqrv
Префиксные хеши (prefix_hash.py)
Алла не остановилась на достигнутом –— теперь она хочет научиться быстро вычислять хеши произвольных подстрок данной строки. Помогите ей!
На вход поступают запросы на подсчёт хешей разных подстрок. Ответ на каждый запрос должен выполняться за 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|).
Для каждого запроса выведите на отдельной строке хеш заданной в запросе подстроки.
| Ввод | Вывод |
|
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 |
Кружки (bocals.py)
В компании, где работает Тимофей, заботятся о досуге сотрудников и устраивают различные кружки по интересам. Когда кто-то записывается на занятие, в лог вносится название кружка.
По записям в логе составьте список всех кружков, в которые ходит хотя бы один человек.
В первой строке даётся натуральное число n, не превосходящее 10 000 –— количество записей в логе.
В следующих n строках —– названия кружков.
Выведите уникальные названия кружков по одному на строке, в порядке появления во входных данных.
| Ввод | Вывод |
|
8 вышивание крестиком рисование мелками на парте настольный керлинг настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение таракановедение |
вышивание крестиком рисование мелками на парте настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение |
Подстроки (substrings.py)
На вход подается строка. Нужно определить длину наибольшей подстроки, которая не содержит повторяющиеся символы.
Одна строка, состоящая из строчных латинских букв. Длина строки не превосходит 10 000.
Выведите натуральное число —– ответ на задачу.
| Ввод | Вывод |
|
abcabcbb |
3 |
Поисковая система (search_system.py)
Тимофей пишет свою поисковую систему.
Имеется n документов, каждый из которых представляет собой текст из слов. По этим документам требуется построить поисковый индекс. На вход системе будут подаваться запросы. Запрос —– некоторый набор слов. По запросу надо вывести 5 самых релевантных документов.
Релевантность документа оценивается следующим образом: для каждого уникального слова из запроса берётся число его вхождений в документ, полученные числа для всех слов из запроса суммируются. Итоговая сумма и является релевантностью документа. Чем больше сумма, тем больше документ подходит под запрос.
Сортировка документов на выдаче производится по убыванию релевантности. Если релевантности документов совпадают —– то по возрастанию их порядковых номеров в базе (то есть во входных данных).
В первой строке дано натуральное число n —– количество документов в базе (1 ≤ n ≤ 104).
Далее в n строках даны документы по одному в строке. Каждый документ состоит из нескольких слов, слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Длина одного текста не превосходит 1000 символов. Текст не бывает пустым.
В следующей строке дано число запросов —– натуральное число m (1 ≤ m ≤ 104). В следующих m строках даны запросы по одному в строке. Каждый запрос состоит из одного или нескольких слов. Запрос не бывает пустым. Слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Число символов в запросе не превосходит 100.
Для каждого запроса выведите на одной строке номера пяти самых релевантных документов. Если нашлось менее пяти документов, то выведите столько, сколько нашлось. Документы с релевантностью 0 выдавать не нужно.
| Ввод | Вывод |
|
3 i love coffee coffee with milk and sugar free tea for everyone 3 i like black coffee without milk everyone loves new year mary likes black coffee without milk |
1 2 3 2 1 |
Хеш-таблица (hash_table.py)
Тимофей, как хороший руководитель, хранит информацию о зарплатах своих сотрудников в базе данных и постоянно её обновляет. Он поручил вам написать реализацию хеш-таблицы, чтобы хранить в ней базу данных с зарплатами сотрудников.
Хеш-таблица должна поддерживать следующие операции:
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 выведите ответ на него в отдельной строке.
| Ввод | Вывод |
|
10 get 1 put 1 10 put 2 4 get 1 get 2 delete 2 get 2 put 1 5 get 1 delete 2 |
None 10 4 4 None 5 None |
Сбалансированное дерево (balanced_tree.py)
Гоше очень понравилось слушать рассказ Тимофея про деревья. Особенно часть про сбалансированные деревья. Он решил написать функцию, которая определяет, сбалансировано ли дерево. Дерево считается сбалансированным, если левое и правое поддеревья каждой вершины отличаются по высоте не больше, чем на единицу.
На вход подается корень дерева.
Функция должна вернуть максимальное значение яркости в узле дерева.
Лампочки (lamps.py)
Гоша повесил на стену гирлянду в виде бинарного дерева, в узлах которого находятся лампочки. У каждой лампочки есть своя яркость. Уровень яркости лампочки соответствует числу, расположенному в узле дерева. Помогите Гоше найти самую яркую лампочку в гирлянде, то есть такую, у которой яркость наибольшая.
На вход подается корень дерева.
Функция должна вернуть True, если дерево сбалансировано в соответствии с критерием из условия, иначе - False.
Дерево - анаграмма (anagram.py)
Гоша и Алла играют в игру «Удивительные деревья». Помогите ребятам определить, является ли дерево, которое им встретилось, деревом-анаграммой? Дерево называется анаграммой, если оно симметрично относительно своего центра
На вход подается корень дерева.
Функция должна вернуть True если дерево является анаграммой. Иначе - False.
Дерево - близнецы (twins.py)
Гоше на день рождения подарили два дерева. Тимофей сказал, что они совершенно одинаковые. Но, по мнению Гоши, они отличаются. Помогите разрешить этот философский спор!
На вход подается корень дерева.
Функция должна вернуть True если деревья являются близнецами. Иначе - False.
Дерево поиска (bst.py)
Гоша понял, что такое дерево поиска, и захотел написать функцию, которая определяет, является ли заданное дерево деревом поиска. Значения в левом поддереве должны быть строго меньше, в правом —- строго больше значения в узле. Помогите Гоше с реализацией этого алгоритма.
На вход подается корень дерева.
Функция должна вернуть True, если дерево является деревом поиска, иначе - False.
Максимальная глубина (max_depth.py)
Алла хочет побывать на разных островах архипелага Алгосы. Она составила карту. Карта представлена в виде дерева: корень обозначает центр архипелага, узлы –— другие острова. А листья —– это дальние острова, на которые Алла хочет попасть. Помогите Алле определить максимальное число островов, через которые ей нужно пройти для совершения одной поездки от стартового острова до места назначения, включая начальный и конечный пункты.
На вход подается корень дерева.
Функция должна вернуть число, равное максимальному числу островов в пути (включая начальный и конечный пункты).
Разные деревья поиска (number_bst.py)
Ребятам стало интересно, сколько может быть различных деревьев поиска, содержащих в своих узлах все уникальные числа от 1 до n. Помогите им найти ответ на этот вопрос.
В единственной строке задано число n. Оно не превосходит 20.
Нужно вывести число, равное количеству различных деревьев поиска, в узлах которых могут быть размещены числа от 1 до n включительно.
Пирамидальная сортировка (heap_sort.py)
В данной задаче необходимо реализовать сортировку кучей. При этом кучу необходимо реализовать самостоятельно, использовать имеющиеся в языке реализации нельзя. Сначала рекомендуется решить задачи про просеивание вниз и вверх.
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач 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.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|
5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
Удали узел (remove_node.py)
Дано бинарное дерево поиска, в котором хранятся ключи. Ключи — уникальные целые числа. Найдите вершину с заданным ключом и удалите её из дерева так, чтобы дерево осталось корректным бинарным деревом поиска. Если ключа в дереве нет, то изменять дерево не надо. На вход вашей функции подаётся корень дерева и ключ, который надо удалить. Функция должна вернуть корень изменённого дерева. Сложность удаления узла должна составлять O(h), где h –— высота дерева. Создавать новые вершины (вдруг очень захочется) нельзя.
Ключи дерева – натуральные числа. В итоговом решении не надо определять свою структуру/свой класс, описывающий вершину дерева.
Построить список смежности (adjacency_list.py)
Алла пошла на стажировку в студию графического дизайна, где ей дали такое задание: для очень большого числа ориентированных графов преобразовать их список рёбер в список смежности. Чтобы побыстрее решить эту задачу, она решила автоматизировать процесс.
Помогите Алле написать программу, которая по списку рёбер графа будет строить его список смежности.
В первой строке дано число вершин n (1 ≤ n ≤ 100) и число ребер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.
Выведите информацию о рёбрах, исходящих из каждой вершины.
В строке i надо написать число рёбер, исходящих из вершины i, а затем перечислить вершины, в которые ведут эти рёбра –— в порядке возрастания их номеров.
| Ввод | Вывод |
|
5 3 1 3 2 3 5 2 |
1 3 1 3 0 0 1 2 |
Перевести список ребер в матрицу смежности (adjacency_matrix.py)
Алла успешно справилась с предыдущим заданием, и теперь ей дали новое. На этот раз список рёбер ориентированного графа надо переводить в матрицу смежности. Конечно же, Алла попросила вас помочь написать программу для этого.
В первой строке дано число вершин n (1 ≤ n ≤ 100) и число ребер m (1 ≤ m ≤ n(n-1)). В следующих m строках заданы ребра в виде пар вершин (u,v), если ребро ведет от u к v.
Выведите матрицу смежности n на n. На пересечении i-й строки и j-го столбца стоит единица, если есть ребро, ведущее из i в j.
| Ввод | Вывод |
|
5 3 1 3 2 3 5 2 |
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 |
DFS (dfs.py)
Задан неориентированный граф. Обойдите с помощью 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).
| Ввод | Вывод |
|
4 4 3 2 4 3 1 4 1 2 3 |
3 2 1 4 |
BFS (bfs.py)
Задан неориентированный граф. Обойдите с помощью 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).
| Ввод | Вывод |
|
4 4 3 2 4 3 1 4 1 2 3 |
3 2 4 1 |
Компоненты связности (connectivity.py)
Вам дан неориентированный граф. Найдите его компоненты связности.
В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (0 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n). В графе нет петель и кратных рёбер.
Выведите все компоненты связности в следующем формате: в первой строке выведите общее количество компонент.
Затем на отдельных строках выведите вершины каждой компоненты, отсортированные по возрастанию номеров. Компоненты между собой упорядочивайте по номеру первой вершины.
| Ввод | Вывод |
|
6 3 1 2 6 5 2 3 |
3 1 2 3 4 5 6 |
Компоненты связности (attractions.py)
Вы приехали на архипелаг Алгосы (наконец-то!). Здесь есть 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.
| Ввод | Вывод |
|
4 4 1 2 1 2 3 3 3 4 5 1 4 2 |
0 1 4 2 1 0 3 3 4 3 0 5 2 3 5 0 |
Дорогая сеть (expensive_network.py)
Тимофей решил соединить все компьютеры в своей компании в единую сеть. Для этого он придумал построить минимальное остовное дерево, чтобы эффективнее использовать ресурсы.
Но от начальства пришла новость о том, что выделенный на сеть бюджет оказался очень большим и его срочно надо израсходовать. Поэтому Тимофея теперь интересуют не минимальные, а максимальные остовные деревья.
Он поручил вам найти вес такого максимального остовного дерева в неориентированном графе, который задаёт схему офиса.
В первой строке дано количество вершин n и ребер m графа (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100000).
В каждой из следующих m строк заданы рёбра в виде троек чисел u, v, w. u и v — вершины, которые соединяет это ребро. w — его вес ( 1 ≤ u, v ≤ n, 0 ≤ w ≤ 10000). В графе могут быть петли и кратные ребра. Граф может оказаться несвязным.
Если максимальное остовное дерево существует, то выведите его вес. Иначе (если в графе несколько компонент связности) выведите фразу «Oops! I did it again».
| Ввод | Вывод |
|
4 4 1 2 5 1 3 6 2 4 8 3 4 3 |
19 |
Железные дороги (railroads.py)
В стране X есть n городов, которым присвоены номера от 1 до n. Столица страны имеет номер n. Между городами проложены железные дороги.
Однако дороги могут быть двух типов по ширине полотна. Любой поезд может ездить только по одному типу полотна. Условно один тип дорог помечают как R, а другой как B. То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет по этому маршруту проехать. От одного города до другого можно проехать только по маршруту, состоящему исключительно из дорог типа R или только из дорог типа B.
Но это ещё не всё. По дорогам страны X можно двигаться только от города с меньшим номером к городу с большим номером. Это объясняет большой приток жителей в столицу, у которой номер n.
Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B. Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бОльшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя. Выясните, является ли данная вам карта оптимальной.
В первой строке дано число n (1 ≤ n ≤ 5000) — количество городов в стране. Далее задана карта железных дорог в следующей формате.
Карта задана n-1 строкой. В i-й строке описаны дороги из города i в города i+1, i+2, ..., n. В строке записано n - i символов, каждый из которых либо R, либо B. Если j-й символ строки i равен «B», то из города i в город i + j идет дорога типа «B». Аналогично для типа «R».
Выведите «YES», если карта оптимальна, и «NO» в противном случае.
| Ввод | Вывод |
|
3 RB R |
NO |
Биржа (exchange.go)
Рита хочет попробовать поиграть на бирже. Но для начала она решила потренироваться на исторических данных.
Даны стоимости акций в каждый из n дней. В течение дня цена акции не меняется. Акции можно покупать и продавать, но только по одной штуке в день. В один день нельзя совершать более одной операции (покупки или продажи). Также на руках не может быть более одной акции в каждый момент времени.
Помогите Рите выяснить, какую максимальную прибыль она могла бы получить.
В первой строке записано количество дней n —– целое число в диапазоне от 0 до 10 000.
Во второй строке через пробел записано n целых чисел в диапазоне от 0 до 1000 –— цены акций.
Выведите число, равное максимально возможной прибыли за эти дни.
| Ввод | Вывод |
|
6 7 1 5 3 6 4 |
7 |
Расписание (schedule.go)
Дано количество учебных занятий, проходящих в одной аудитории. Для каждого из них указано время начала и конца. Нужно составить расписание, в соответствии с которым в классе можно будет провести как можно больше занятий.
Если возможно несколько оптимальных вариантов, то выведите любой. Возможно одновременное проведение более чем одного занятия нулевой длительности.
В первой строке задано число занятий. Оно не превосходит 1000. Далее для каждого занятия в отдельной строке записано время начала и конца, разделённые пробелом. Время задаётся одним целым числом h, если урок начинается/заканчивается ровно в h часов. Если же урок начинается/заканчивается в h часов m минут, то время записывается как h.m. Гарантируется, что каждое занятие начинается не позже, чем заканчивается. Указываются только значащие цифры.
Выведите в первой строке наибольшее число уроков, которое можно провести в аудитории. Далее выведите время начала и конца каждого урока в отдельной строке в порядке их проведения.
| Ввод | Вывод |
|
5 9 10 9.3 10.3 10 11 10.3 11.3 11 12 |
3 9 10 10 11 11 12 |
Золотая лихорадка (fever.go)
Гуляя по одному из островов Алгосского архипелага, Гоша набрёл на пещеру, в которой лежат кучи золотого песка. К счастью, у Гоши есть с собой рюкзак грузоподъёмностью до M килограмм, поэтому он может унести с собой какое-то ограниченное количество золота.
Всего золотых куч n штук, и все они разные. В куче под номером i содержится mi килограммов золотого песка, а стоимость одного килограмма — ci алгосских франков.
Помогите Гоше наполнить рюкзак так, чтобы общая стоимость золотого песка в пересчёте на алгосские франки была максимальной.
В первой строке задано целое число M — грузоподъёмность рюкзака Гоши (0 ≤ M ≤ 108). Во второй строке дано количество куч с золотым песком — целое число n (1 ≤ n ≤ 105).
В каждой из следующих n строк описаны кучи: i-ая куча задаётся двумя целыми числами ci и mi, записанными через пробел (1 ≤ ci ≤ 107, 1 ≤ mi ≤ 108).
Выведите единственное число —– максимальную сумму (в алгосских франках), которую Гоша сможет вынести из пещеры в своём рюкзаке.
| Ввод | Вывод |
|
10 3 8 1 2 10 4 5 |
36 |
Числа Фибоначчи для взрослых (fibonacci.go)
Гоша практикуется в динамическом программировании — он хочет быстро считать числа Фибоначчи.
В единственной строке дано целое число n (0 ≤ n ≤ 106).
Вычислите значение Fn по модулю 10^9 + 7 и выведите его.
| Ввод | Вывод |
|
5 |
8 |
Прыжки по лестнице (jumps.go)
Алла хочет доказать, что она умеет прыгать вверх по лестнице быстрее всех. На этот раз соревнования будут проходить на специальной прыгательной лестнице. С каждой её ступеньки можно прыгнуть вверх на любое расстояние от 1 до k. Число k придумывает Алла.
Гоша не хочет проиграть, поэтому просит вас посчитать количество способов допрыгать от первой ступеньки до n-й. Изначально все стоят на первой ступеньке.
В единственной строке даны два числа — n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n).
Выведите количество способов по модулю 10^9 + 7.
| Ввод | Вывод |
|
6 3 |
13 |
Банкомат (atm.go)
Тимофей пошёл снять деньги в банкомат. Ему нужно m франков. В банкомате в бесконечном количестве имеются купюры различных достоинств. Всего различных достоинств n. Купюр каждого достоинства можно взять бесконечно много. Нужно определить число способов, которыми Тимофей сможет набрать нужную сумму.
В первой строке записано целое число m — сумма, которую нужно набрать. Во второй строке n — количество монет в банкомате. Оба числа не превосходят 300. Далее в третьей строке записано n уникальных натуральных чисел, каждое в диапазоне от 1 до 1000 –– достоинства купюр.
Нужно вывести число способов, которым Тимофей сможет набрать нужную сумму.
| Ввод | Вывод |
|
5 3 3 2 1 |
5 |
Расстояние по Левенштейну (levenshtein_distance.py)
Расстоянием Левенштейна между двумя строками s и t называется количество атомарных изменений, с помощью которых можно одну строку превратить в другую. Под атомарными изменениями подразумеваются: удаление одного символа, вставка одного символа, замена одного символа на другой.
Найдите расстояние Левенштейна для предложенной пары строк.
Выведите единственное число — расстояние между строками.
В первой строке дана строка s, во второй — строка t. Длины обеих строк не превосходят 1000. Строки состоят из маленьких латинских букв.
Выведите единственное число — расстояние между строками.
| Ввод | Вывод |
|
abacaba abaabc |
2 |
Одинаковые суммы (is_same_amounts.py)
На Алгосах устроили турнир по настольному теннису. Гоша выиграл n партий, получив при этом некоторое количество очков за каждую из них.
Гоше стало интересно, можно ли разбить все заработанные им во время турнира очки на две части так, чтобы сумма в них была одинаковой.
В первой строке записано целое число n (0 ≤ n ≤ 300) –— количество выигранных партий.
Во второй строке через пробел записано n целых неотрицательных чисел, каждое из которых не превосходит 300 –— заработанные в партиях очки.
Нужно вывести True, если произвести такое разбиение возможно, иначе —– False
| Ввод | Вывод |
|
4 1 5 7 1 |
True |
Разворот строки (reversal_string.go)
В некоторых языках предложения пишутся и читаются не слева направо, а справа налево.
Вам под руку попался странный текст –— в нём обычный (слева направо) порядок букв в словах. А вот сами слова идут в противоположном направлении. Вам надо преобразовать текст так, чтобы слова в нём были написаны слева направо.
На ввод подаётся строка, состоящая из слов, разделённых пробелами (один пробел между соседними словами). Всего слов не более 1000, длина каждого из них —– от 1 до 100 символов. Слова состоят из строчных букв английского алфавита.
Выведите строку с обратным порядком слов в ней.
| Ввод | Вывод |
|
one two three |
three two one |
Самый длинный палиндром (longest_palindrome.go)
Палиндром —– это строка, которая одинаково читается как слева направо, так и справа налево.
Из данной строки s путём удаления и перестановки букв надо получить палиндром максимальной длины. Среди всех таких палиндромов надо получить лексикографически минимальный. Количество удалений и перестановок символов может быть любым.
В единственной строке дана строка s. Длина строки |s| ≤ 105. Строка состоит из строчных букв английского алфавита.
Выведите полученный палиндром. Заметьте, что ответ определяется однозначно.
| Ввод | Вывод |
|
aaaabb |
aabbaa |
Общий префикс (general_prefix.go)
Найдите наибольший по длине общий префикс нескольких строк.
В первой строке дано число n (1 ≤ n ≤ 105). Затем по одной на строке даны n строк, каждая не превышает 105 в длину. Суммарная длина всех строк не превосходит 107.
Выведите единственное число — длину наибольшего префикса всех данных строк.
| Ввод | Вывод |
|
3 abacaba abudabi abcdefg |
2 |
Глобальная замена (global_replace.go)
Напишите программу, которая будет заменять в тексте все вхождения строки s на строку t. Гарантируется, что никакие два вхождения шаблона s не пересекаются друг с другом.
В первой строке дан текст —– это строка из строчных букв английского алфавита, длина которой не превышает 106.
Во второй строке записан шаблон s, вхождения которого будут заменены.
В третьей строке дана строка t, которая будет заменять вхождения.
Обе строки s и t состоят из строчных букв английского алфавита, длина каждой строки не превосходит 105. Размер итоговой строки не превосходит 2⋅ 106.
В единственной строке выведите результат всех замен — текст, в котором все вхождения s заменены на t.
| Ввод | Вывод |
|
pingpong ng mpi |
pimpipompi |
Packed Prefix (packed_prefix.py)
Вам даны строки в запакованном виде. Определим запакованную строку (ЗС) рекурсивно. Строка, состоящая только из строчных букв английского алфавита является ЗС. Если A и B —– корректные ЗС, то и AB является ЗС. Если A —– ЗС, а n — однозначное натуральное число, то n[A] тоже ЗС. При этом запись n[A] означает, что при распаковке строка A записывается подряд n раз. Найдите наибольший общий префикс распакованных строк и выведите его (в распакованном виде).
Иными словами, пусть сложение —– это конкатенация двух строк, а умножение строки на число — повтор строки соответствующее число раз. Пусть функция f умеет принимать ЗС и распаковывать её. Если ЗС D имеет вид D=AB, где A и B тоже ЗС, то f(D) = f(A) + f(B). Если D=n[A], то f(D) = f(A) × n.
В первой строке записано число n (1 ≤ n ≤ 1000) –— число строк.
Далее в n строках записаны запакованные строки. Гарантируется, что эти строки корректны, то есть удовлетворяют указанному рекурсивному определению. Длина строк после распаковки не превосходит 10^5.
Выведите наибольший общий префикс распакованных строк.
| Ввод | Вывод |
|
3 2[a]2[ab] 3[a]2[r2[t]] a2[aa3[b]] |
aaa |
Шпаргалка (сheat_sheet.py)
Вася готовится к экзамену по алгоритмам и на всякий случай пишет шпаргалки.
Чтобы уместить на них как можно больше информации, он не разделяет слова пробелами. В итоге получается одна очень длинная строка. Чтобы на самом экзамене из-за нервов не запутаться в прочитанном, он просит вас написать программу, которая по этой длинной строке и набору допустимых слов определит, можно ли разбить текст на отдельные слова из набора.
Более формально: дан текст T и набор строк s1, ... ,sn. Надо определить, представим ли T как sk1sk2...skr, где где ki — индексы строк. Индексы могут повторяться. Строка si может встречаться в разбиении текста T произвольное число раз. Можно использовать не все строки для разбиения. Строки могут идти в любом порядке.
В первой строке дан текст T, который надо разбить на слова. Длина T не превосходит 10^5. Текст состоит из строчных букв английского алфавита.
Во второй строке записано число допустимых к использованию слов 1 ≤ n ≤ 100.
В последующих n строках даны сами слова, состоящие из маленьких латинских букв. Длина каждого слова не превосходит 100.
Выведите «YES», если текст можно разбить на слова из данного словаря, или «NO» в ином случае.
| Ввод | Вывод |
|
examiwillpasstheexam 5 will pass the exam i |
YES |
Ресурсы для самостоятельного изучения. В основном они на английском, но есть и материалы, переведённые на русский язык.
Самое необходимое
- LeetCode — самый большой банк задач с собеседований. Любая задача, которая когда-либо задавалась на алгоритмическом собеседовании, наверняка есть тут. Задачи можно фильтровать по компаниям, тегам и сложности. Советуем заходить сюда регулярно — и чтобы готовиться к интервью, и чтобы поддерживать навык решения задач.
- Видеолекции Павла Маврина - Подойдут как для лучшего понимания тем из курса, так и для изучения новых, в том числе весьма продвинутых.
Подготовка к интервью
- Книга «Карьера программиста» или в оригинале “Cracking the Coding Interview”. Содержит много советов про подготовку к алгоритмическим собеседованиям. Будет полезна в дополнение к урокам 1 спринта нашего курса.
- InterviewBit — другой хороший ресурс с задачами для собеседований. Не нужно возиться с фильтрами, можно пройти по всем интересующим темам.
- Pramp — сервис для проведения peer-to-peer пробных интервью на английском языке. Вам назначается случайный человек в пару и вы собеседуете его, а потом он — вас. Очень полезно попробовать себя в роли не только собеседуемого, но и собеседущего — это поможет вам лучше почувствовать, как интервьюер оценивает кандидата. Очень рекомендуем в процессе подготовки к алгоритмическим интервью на английском языке.
- Как проходят алгоритмические секции на собеседованиях в Яндекс — статья про подготовку к собеседованиям от Яндекса.
- Вебинар «Открытое алгоритмическое собеседование». Можно посмотреть перед тем, как вы пойдёте на первое пробное интервью, чтобы прочувствовать формат в динамике.
- Coding Interview University — самый полный гайд по подготовке к собеседованиям. Настолько полный, что на его прохождение потребуется очень много времени: автор говорит о 8–12 часов в день в течение 8 месяцев. Поэтому оставляем его тут на случай, если вы настроены максимально решительно.
Более академическое изучение
- Книга «Алгоритмы. Построение и анализ» — классический труд по теории алгоритмов и структур данных. Много тем, включая математику, но большой объём и академический стиль изложения.
- Codeforces — портал, посвящённый спортивному программированию. Мы рекомендуем его в контексте предыдущего пункта: тут вы сможете найти задачи на отработку тем, изученных в учебниках.
Где можно проявить себя
- Google Code Jam — ежегодное соревнование от Google, проходит в несколько этапов от простых отборочных до финала с очень сложными задачами. Попадание в Round 2 даёт хорошие шансы на то, чтобы с вами связался рекрутер Google. Если вы студент, то рекомендуем также поучаствовать в более простом Kick Start.
- Facebook Hacker Cup — аналогичное соревнование от Facebook.
- Yandex Cup — соревнование от Яндекса. В отличие от вышеперечисленных, проводится не только по алгоритмам, но и по другим направлениям.
- Advent of Code — это не столько соревнование, сколько возможность порешать и обсудить задачи с друзьями или коллегами.
