Skip to content

LarisaKukarskaya/algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Базовые алгоритмы

Решение задач по алгоритмам на языке Python


1. Введение в алгоритмы

contest.yandex.ru


Застежка-молния (zipper.py)

Условие

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

Формат ввода

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

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

Выведите 2n чисел из объединённого массива через пробел.

Пример 1

Ввод Вывод
3
1 2 3
4 5 6
1 4 2 5 3 6

Пример 2

Ввод Вывод
1
1
2
1 2

Пример 3

Ввод Вывод
3
1 8 9
2 3 1
1 2 8 3 9 1

Скользящее среднее (moving_average.py)

Условие

Вам дана статистика по числу запросов в секунду к вашему любимому рекомендательному сервису. Измерения велись n секунд. В секунду i поступает qi запросов. Примените метод скользящего среднего с длиной окна k к этим данным и выведите результат.

Формат ввода

В первой строке передаётся натуральное число n, количество секунд, в течение которых велись измерения. 1 ≤ n ≤ 105 Во второй строке через пробел записаны n целых неотрицательных чисел qi, каждое лежит в диапазоне от 0 до 103. В третьей строке записано натуральное число k (1 ≤ k ≤ n) – окно сглаживания. Примечание для Go: Заметьте, что в данной задаче достаточно большой размер ввода. Поэтому необходимо задавать размер буфера для сканнера хотя бы 600 Кб.

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

Выведите через пробел результат применения метода скользящего среднего к серии измерений. Должно быть выведено n - k + 1 элементов, каждый элемент — вещественное (дробное) число.

Пример 1

Ввод Вывод
7
1 2 3 4 5 6 7
4
2.5 3.5 4.5 5.5

Пример 2

Ввод Вывод
9
9 3 2 0 1 5 1 0 0
3
4.6666666667 1.666666667 1 2 2.333333335 2 0.3333333

Пример 3

Ввод Вывод
5
1 2 3 4 5
5
3

Две фишки (two_chips.py)

Условие

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

Формат ввода

В первой строке записано количество фишек n, 2 ≤ n ≤ 104. Во второй строке записано n целых чисел —– очки на фишках Риты в диапазоне от -105 до 105. В третьей строке —– загаданное Гошей целое число k, -105 ≤ k ≤ 105.

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

Нужно вывести два числа —– очки на двух фишках, в сумме дающие k. Если таких пар несколько, то можно вывести любую из них. Если таких пар не существует, то вывести «None».

Пример 1

Ввод Вывод
6
-1 -1 -9 -7 3 -6
2
-1 3

Пример 2

Ввод Вывод
8
6 2 8 -3 1 1 6 10
100
None

Соседи (neighbours.py)

Условие

Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей. Соседним считается элемент, находящийся от текущего на одну ячейку влево, вправо, вверх или вниз. Диагональные элементы соседними не считаются. Например, в матрице A соседними элементами для (0, 0) будут 2 и 0. А для (2, 1) –— 1, 2, 7, 7.

Формат ввода

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

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

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

Пример 1

Ввод Вывод
4
3
1 2 3
0 2 6
7 4 1
2 7 0
3
0
7 7

Пример 2

Ввод Вывод
4
3
1 2 3
0 2 6
7 4 1
2 7 0
0
0
0 2

Хаотичность погоды (random_weather.py)

Условие

Метеорологическая служба вашего города решила исследовать погоду новым способом. Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день. Под хаотичностью погоды за n дней служба понимает количество дней, в которые температура строго больше, чем в день до (если такой существует) и в день после текущего (если такой существует). Например, если за 5 дней максимальная температура воздуха составляла [1, 2, 5, 4, 8] градусов, то хаотичность за этот период равна 2: в 3-й и 5-й дни выполнялись описанные условия. Определите по ежедневным показаниям температуры хаотичность погоды за этот период. Заметим, что если число показаний n=1, то единственный день будет хаотичным.

Формат ввода

В первой строке дано число n –— длина периода измерений в днях, 1 ≤ n≤ 105. Во второй строке даны n целых чисел –— значения температуры в каждый из n дней. Значения температуры не превосходят 273 по модулю.

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

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

Пример 1

Ввод Вывод
7
-1 -10 -8 0 2 0 5
3

Пример 2

Ввод Вывод
5
1 2 5 4 8
2

Самое длинное слово (longest_word.py)

Условие

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

Формат ввода

В первой строке дана длина текста L (1 ≤ L ≤ 105). В следующей строке записан текст, состоящий из строчных латинских букв и пробелов. Слово —– последовательность букв, не разделённых пробелами. Пробелы могут стоять в самом начале строки и в самом её конце. Текст заканчивается переносом строки, этот символ не включается в число остальных L символов.

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

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

Пример 1

Ввод Вывод
19
i love segment tree
segment
7

Пример 2

Ввод Вывод
21
frog jumps from river
jumps
5

Палиндром (palindrom.py)

Условие

Помогите Васе понять, будет ли фраза палиндромом. Учитываются только буквы и цифры, заглавные и строчные буквы считаются одинаковыми. Решение должно работать за O(N), где N — длина строки на входе.

Формат ввода

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

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

Выведите «True», если фраза является палиндромом, и «False», если не является.

Пример 1

Ввод Вывод
A man, a plan, a canal: Panama
True

Пример 2

Ввод Вывод
zo
False

Двоичная система (binary_system.py)

Условие

Тимофей записал два числа в двоичной системе счисления и попросил Гошу вывести их сумму, также в двоичной системе. Встроенную в язык программирования возможность сложения двоичных чисел применять нельзя. Помогите Гоше решить задачу. Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.

Формат ввода

Два числа в двоичной системе счисления, каждое на отдельной строке. Длина каждого числа не превосходит 10 000 символов.

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

Одно число в двоичной системе счисления.

Пример 1

Ввод Вывод
1010
1011
10101

Пример 2

Ввод Вывод
1
1
10

Степень четырех (degree_of_four.py)

Условие

Напишите программу, которая определяет, будет ли положительное целое число степенью четвёрки. Подсказка: степенью четвёрки будут все числа вида 4n, где n – целое неотрицательное число.

Формат ввода

На вход подаётся целое число в диапазоне от 1 до 10000.

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

Выведите «True», если число является степенью четырёх, «False» –— в обратном случае.

Пример 1

Ввод Вывод
15
False

Пример 2

Ввод Вывод
16
True

Ближайший ноль (nearest_zero.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
5
0 1 4 9 0 0
0 1 2 1 0

Пример 2

Ввод Вывод
6
0 7 9 4 8 20
0 1 2 3 4 5

Ловкость рук (sleight_of_hands.py)

Условие

«Тренажёр для скоростной печати» представляет собой квадратную клавиатуру из шестнадцати клавиш размером 4x4. На каждой клавише может быть изображена либо точка, либо цифра от 1 до 9. Занятие на тренажёре делится на раунды : каждый раунд состоит из нескольких игр; в разных раундах число игр может быть разным; номер каждой игры в раунде обозначается счётчиком t. Для каждого раунда на клавишах устанавливаются определённые значения, которые остаются неизменными в течение всех игр раунда. Значение счётчика игр t не может превысить значение самого большого числа, отображённого на клавиатуре в текущем раунде. В упражнении на тренажёре принимают участие два игрока, они играют вдвоём на одной клавиатуре. Для каждого раунда устанавливается максимальное число клавиш, которые может нажать один игрок (оно обозначается переменной k и не изменяется в течение раунда). В каждой отдельной игре участники должны вместе нажать на клавиши, на которых изображена цифра, соответствующая номеру игры t. Например, во второй игре раунда игроки должны нажать все те клавиши, на которых изображена двойка. В раунде могут быть игры, где не требуется нажимать кнопки: например, в приведённом варианте раунда в играх от t = 4 до t = 8 кнопки нажимать не потребуется: на клавиатуре нет цифр от 4 до 8. Если в очередной игре у участников есть возможность нажать все необходимые клавиши — они их нажимают и получают 1 балл. Предположим, что для раунда задан набор кнопок, как на картинке, и k = 3 (каждый из участников может нажать не более трёх кнопок). Тогда во второй игре (t = 2), где должны быть нажаты двойки, игроки вдвоём смогут нажать только 6 клавиш (k * 2 = 6). Но на клавиатуре семь двоек; участники не смогут нажать их все и не получат балл.

Напишите программу, которая будет принимать данные для определённого раунда: значение k, значения для кнопок и вычислит количество баллов, которое будут заработано в этом раунде.

Формат ввода

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

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

Выведите единственное число –— количество баллов, которое игроки наберут в раунде.

Пример 1

Ввод Вывод
3
1231
2..2
2..2
2..2
2

Пример 2

Ввод Вывод
4
1111
9999
1111
9911
1

Пример 3

Ввод Вывод
4
1111
1111
1111
1111
0

2. Основные структуры данных

contest.yandex.ru


Список дел (business_list.py)

Условие

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

  • c++
  • Java
  • js
  • Python
  • C#
  • go

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

Формат ввода

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

  • По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен.
  • Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования.
  • Для Java файл должен называться Solution.java, для C# – Solution.cs
  • Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже).
  • Для Go укажите package main.

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

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


Нелюбимое дело (unloved_business.py)

Условие

Вася размышляет, что ему можно не делать из того списка дел, который он составил. Но, кажется, все пункты очень важные! Вася решает загадать число и удалить дело, которое идёт под этим номером. Список дел представлен в виде односвязного списка. Напишите функцию solution, которая принимает на вход голову списка и номер удаляемого дела и возвращает голову обновлённого списка. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и номер удаляемого элемента и возвращает голову обновлённого списка. Используйте заготовки кода для данной задачи, расположенные по ссылкам:

  • c++
  • Java
  • js
  • Python
  • C#
  • go

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

Формат ввода

Функция принимает голову списка и индекс элемента, который надо удалить (нумерация с нуля). Список содержит не более 5000 элементов. Список не бывает пустым. Следуйте следующим правилам при отправке решений:

  • По умолчанию выбран компилятор Make, выбор компилятора в данной задаче недоступен.
  • Решение нужно отправлять в виде файла с расширением соответствующем вашему языку программирования.
  • Для Java файл должен называться Solution.java, для C# – Solution.cs
  • Для остальных языков программирования это имя использовать нельзя (имя «solution» тоже).
  • Для Go укажите package main.

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

Верните голову списка, в котором удален нужный элемент.


Заботливая мама (caring_mother.py)

Условие

Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей: напишите функцию solution, определяющую индекс первого вхождения передаваемого ей на вход значения в связном списке, если значение присутствует. Внимание: в этой задаче не нужно считывать входные данные. Нужно написать только функцию, которая принимает на вход голову списка и искомый элемент, а возвращает целое число — индекс найденного элемента или -1. Используйте заготовки кода для данной задачи, расположенные по ссылкам:

  • c++
  • Java
  • js
  • Python
  • C#
  • go
  • Kotlin
  • Swift

Формат ввода

Функция на вход принимает голову односвязного списка и элемент, который нужно найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым.

Инструкцию по работе с Make вы можете найти в конце этого урока

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

Функция возвращает индекс первого вхождения искомого элемента в список(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.


Всё наоборот (vice_versa.py)

Условие

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

  • c++
  • Java
  • js
  • Python
  • C#
  • go
  • Kotlin
  • Swift

Формат ввода

Функция принимает на вход единственный аргумент — голову двусвязного списка. Длина списка не превосходит 1000 элементов. Список не бывает пустым.

Инструкцию по работе с Make вы можете найти в конце этого урока

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

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


Скобочная последовательность (brackets.py)

Условие

Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная. Дана скобочная последовательность. Нужно определить, правильная ли она. Будем придерживаться такого определения: пустая строка —– правильная скобочная последовательность; правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность; правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная. На вход подаётся последовательность из скобок трёх видов: [], (), {}. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.

Формат ввода

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

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

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

Пример 1

Ввод Вывод
{[()]}
{}
True
True

Дек (deque.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) ничего выводить не надо.

Пример 1

Ввод Вывод
4
4
push_front 861
push_front -819
pop_back
pop_back
861
-819

Калькулятор (calculator.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

3. Рекурсии и сортировки

contest.yandex.ru


Большое число (big_number.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
3
15 56 2
56215

Пример 2

Ввод Вывод
3
1 783 2
78321

Пример 3

Ввод Вывод
5
2 4 5 2 10
542210

Генератор скобок (bracket_generator.py)

Условие

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

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

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

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
3



((()))
(()())
(())()
()(())
()()()

Пример 2

Ввод Вывод
2


(())
()()

Комбинации (combinations.py)

Условие

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

2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
23
ad ae af bd be bf cd ce cf

Пример 2

Ввод Вывод
92
wa wb wc xa xb xc ya yb yc za zb zc

Подпоследовательность (subsequence.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
abc
ahbgdcu
True

Пример 2

Ввод Вывод
abcp
ahpc
False

Гардероб (wardrobe.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
7
0 2 1 2 0 0 1
0 0 0 1 1 2 2

Пример 2

Ввод Вывод
5
2 1 2 0 1
0 1 1 2 2

Пример 3

Ввод Вывод
6
2 1 1 2 0 2
0 1 1 2 2 2

Пузырёк (bubble.py)

Условие

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

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

Формат ввода

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

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

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

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

Пример 1

Ввод Вывод
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

Пример 2

Ввод Вывод
5
12 8 9 10 11
8 9 10 11 12

Сортировка слиянием (merge_sort.py)

Условие

Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort. Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом [left,mid) массива array, а второй – полуинтервалом [mid,right) массива array. Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает. Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge. Заметьте, что в функции передаются именно полуинтервалы [bein,end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где arr=[4,5,3,0,1,2], то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как arr=[0,34,5,1,2]. Реализуйте эти две функции. Используйте заготовки кода для данной задачи, расположенные по ссылкам: c++ Java js Python C# go Kotlin Swift

Формат ввода

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

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

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

Передаваемый в функции массив состоит из целых чисел, не превосходящих по модулю 109. Длина сортируемого диапазона не превосходит 105.

Инструкцию по работе с Make вы можете найти в конце этого урока


Два велосипеда (two_bicycles.py)

Условие

Вася решил накопить денег на два одинаковых велосипеда — себе и сестре. У Васи есть копилка, в которую каждый день он может добавлять деньги (если, конечно, у него есть такая финансовая возможность). В процессе накопления Вася не вынимает деньги из копилки. У вас есть информация о росте Васиных накоплений — сколько у Васи в копилке было денег в каждый из дней. Ваша задача — по заданной стоимости велосипеда определить первый день, в которой Вася смог бы купить один велосипед, и первый день, в который Вася смог бы купить два велосипеда. Подсказка: решение должно работать за O(log n).

Формат ввода

В первой строке дано число дней n, по которым велись наблюдения за Васиными накоплениями. 1 ≤ n ≤ 106. В следующей строке записаны n целых неотрицательных чисел. Числа идут в порядке неубывания. Каждое из чисел не превосходит 106. В третьей строке записано целое положительное число s — стоимость велосипеда. Это число не превосходит 106. Обратите внимание, что считывать нужно только 2 строки: значение n и входной массив.

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

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

Пример 1

Ввод Вывод
6
1 2 4 4 6 8 3
3 5

Пример 2

Ввод Вывод
6
1 2 4 4 4 4
3
3 -1

Пример 3

Ввод Вывод
6
1 2 4 4 4 4
10
-1 -1

Клумбы (flowerbeds.py)

Условие

Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанам. На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. Для ландшафтных работ было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. Нужно определить границы будущих клумб. Рассмотрим примеры. Пример 1: Даны 4 отрезка: [7,8],[7,8],[2,3],[6,10]. Два одинаковых отрезка [7,8] и [7,8] сливаются в один, но потом их накрывает отрезок [6,10] Таким образом, имеем две клумбы с координатами [2, 3] и [6,10]. Пример 2 Во втором сэмпле опять 4 отрезка: [2,3], [3,4],[3,4],[5,6]. Отрезки [2,3],[3,4] и [3,4] сольются в один отрезок [2,4]. Отрезок [5,6] ни с кем не объединяется, добавляем его в ответ.

Формат ввода

В первой строке задано количество садовников n. Число садовников не превосходит 100000. В следующих n строках через пробел записаны координаты клумб в формате: start end, где start —– координата начала, end —– координата конца. Оба числа целые, неотрицательные и не превосходят 10 в 7 степени. start строго меньше, чем end.

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

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

Пример 1

Ввод Вывод
4
7 8
7 8
2 3
6 10
2 3
6 10

Пример 2

Ввод Вывод
4
2 3
5 6
3 4
3 4
2 4
5 6

Пример 3

Ввод Вывод
6
1 3
3 5
4 6
5 6
2 4
7 10
1 6
7 10

4. Хеш-функции

contest.yandex.ru


Полиномиальный хеш (polynomial_hash.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
123
100003
a
97

Пример 2

Ввод Вывод
123
100003
hash
6080

Пример 3

Ввод Вывод
123
100003
HaSH
56156

Сломай меня (break_me.py)

Условие

Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было. В этой задаче вам надо будет лишь найти две различные строки, которые для заданной хеш-функции будут давать одинаковое значение. a = 1000 и m = 123 987 123. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.

Формат ввода

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

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

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

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


Префиксные хеши (prefix_hashes.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|).

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

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

Пример 1

Ввод Вывод
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

Пример 2

Ввод Вывод
100
10
a
1
1 1
7

Кружки (interest_groups.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
8
вышивание крестиком
рисование мелками на парте
настольный керлинг
настольный керлинг
кухня африканского племени ужасмай
тяжелая атлетика
таракановедение
таракановедение
вышивание крестиком
рисование мелками на парте
настольный керлинг
кухня африканского племени ужасмай
тяжелая атлетика
таракановедение

Подстроки (substrings.py)

Условие

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

Формат ввода

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

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

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

Пример 1

Ввод Вывод
abcabcbb
3

Пример 2

Ввод Вывод
bbbbb
1