Задача 00A. Hello, world! ≡

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)

Задача 00B. Радуга ≡

Условие

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

Цвета должны быть выведены в кодировке WINDOWS-1251.

Примеры тестов

Красный
Оранжевый
Желтый
Зеленый
Голубой
Синий
Фиолетовый

Задача 01A. Солнечный день ≡

Условие

Ваша лодка потерпела крушение! Но вы и не против, сидите себе спокойно и каждые 10 минут выливаете за борт X литров воды. При этом каждую минуту через пробоину поступает Y литров воды. При условии, что в таком темпе вы никогда не вычерпаете воду полностью, сколько литров воды будет в вашей лодке через T минут?

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

Входные данные содержат целые числа X, Y и T, по одному числу в строке.

Примеры тестов

10
1
15

5

1000
9
9

81

Задача 01B. Олины торты ≡

Условие

Сегодня к Оле в гости придет N одногруппников, из-за чего она решила приготовить N тортов. В ее распоряжении есть M грамм сахара. Поскольку Оля не хочет никого обидеть, в каждом торте должно быть одинаковое количество сахара. Какое максимальное количество сахара может содержать каждый торт?

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

Входные данные содержат числа M и N, каждое на новой строке.

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

Примеры тестов

10
2

5

6
4

1.5

Задача 01C. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

Примеры тестов

23

25

Buzz

30

FizzBuzz

Задача 02A. Вынутый разворот ≡

Условие

Брошюра составлена из листов. На каждой стороне листа напечатано по две страницы. Страницы пронумерованы начиная с первой. Из брошюры был вынут один лист. Требуется по двум номерам страниц, напечатанным на одной из сторон этого листа, определить общее количество страниц в брошюре.

Формат входного файла

Во входном файле содержатся два целых числа A и B — номера страниц на стороне листа, в произвольном порядке

Формат выходного файла

В выходном файле должно содержаться единственное число:

• 0 — если такой брошюры не существует
• Число страниц в брошюры — в противном случае

Ограничения

1 ≤ A, B ≤ 10⁶

Примеры тестов

3 14

16

9 1

0

Задача 02B. Время в пути ≡

Условие

Время отправления и время прибытия поезда задаются в виде Ч М, где Ч - час от 0 до 23, М - минута от 0 до 59. Время в пути задаётся аналогично в формате Ч М, где Ч - количество часов от 0 до 999, а М - количество минут от 0 до 59.

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

Формат входного файла

Формат выходного файла

Примеры тестов

18 25
7 37

2 2

Задача 02C. Вася и мысли ≡

Условие

Юный программист Вася любит прогуливаться по тропинке длиной D метров, проходящей неподалёку от его школы, и размышлять о том о сём.

В начале прогулки Вася размышляет о Важных Вещах, и ноги несут его с постоянной скоростью, равной либо v₁, либо v₂ м/c. Затем Вася отвлекается и начинает думать о Всякой Ерунде. В этот момент его скорость становится равной либо w₁, либо w₂ м/c.

Если Вася затратил на прогулку T секунд, каково максимальное возможное расстояние, пройденное им с Важными Вещами в голове?

Формат входного файла

Первая строка входного файла содержит числа D T. Во второй строке записаны числа v₁ v₂. В третьей строке записаны числа w₁ w₂. Каждое число имеет не более трёх знаков после десятичной точки.

Формат выходного файла

Выходной файл должен содержать одно вещественное число d — максимальное возможное расстояние с точностью не менее 3 десятичных знаков.

Входные данные таковы, что решение всегда существует.

Ограничения

1 ≤ D, T ≤ 1000

10^− 3 ≤ v₁ < v₂ ≤ 10²

10^− 3 ≤ w₁ < w₂ ≤ 10²

Примеры тестов

10.0 5.0
1.0 3.0
0.5 1.0

9.0

15.0 3.0
1.0 2.5
4.25 6.1

2.291

25.0 5.0
1.0 3.0
4.0 5.0

0.0

Задача 02D. Вокруг дома ≡

Условие

Васин дом имеет в плане форму прямоугольника. Северная и южная стороны имеют длину по A метров каждая, а западная и восточная — по B метров каждая.

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

Требуется написать программу, которая определит, вдоль какой стены будет идти Вася через t секунд после начала прогулки. Будем считать, что дойдя то угла, Вася немедленно за него поворачивает, поэтому на секундах с нулевой по A − 1-ю он находится у южной стены, на секунде номер A — у восточной, и так далее.

Формат входного файла

Входной файл содержит целые числа A B t.

Формат выходного файла

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

• N — северная стена,
• W — западная стена,
• S — южная стена,
• E — восточная стена.

Ограничения

1 ≤ A, B, t ≤ 5 * 10⁸

Примеры тестов

10 5 18

N

1 8 18

S

Задача 02E. Представьтесь ≡

Условие

Требуется написать программу, которая считывает имя и фамилию и выводит их в формате

Меня зовут [фамилия]

[имя] [фамилия]

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

Входные данные содержат два слова в разных строках: имя и фамилию.

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

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

Примеры тестов

Джеймс
Бонд

Меня зовут Бонд
Джеймс Бонд

Задача 02F. Электронная почта ≡

Условие

В ДВФУ у каждого студента и сотрудника есть персональный адрес электронной почты в домене dvfu.ru.

Требуется написать программу, которая по заданным фамилии, имени и роли пользователя создает адрес его электронной почты в формате [фамилия].[имя]@[роль].dvfu.ru

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

Входные данные содержат три слова в разных строках.

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

Выходные данные должны содержать одну строку — электронный адрес в описанном формате.

Примеры тестов

sporyshev
ms
students

sporyshev.ms@students.dvfu.ru

Задача 02G. Простое ≡

Условие

Условный оператор — это просто! Верно?

Напишите программу, которая принимает на вход от пользователя одну строку. Если пользователь ответил "Просто!", "Easy!" или "Einfach!", напечатайте в ответ улыбающийся смайл ":)". В ином случае — грустный смайл ":(".

Примеры тестов

Просто!

:)

Как-то не очень

:(

Задача 02H. Сложное ≡

Условие

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

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

Входные данные содержат предложение в кодировке CP1251.

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

Выходные данные должны содержать тип предложения в кодировке CP1251. Если предложение сложное, слово "сложное" должно стоять первым и отделяться пробелом от восклицательности предложения (смотри пример).

Примеры тестов

Что тут происходит?!?!

вопросительно-восклицательное

Скажите мне, пожалуйста!

сложное восклицательное

Ничего

повествовательное

Задача 02I. Игра в предложения ≡

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

Примеры тестов

4
cha
g'thazag
mog
Bin

Bin
mog
g'thazag
cha

Задача 02J. Горшочек каши ≡

Условие

Требуется написать программу, которая считывает строки из стандартного ввода. Если считана строка "Stop!", программа печатает "Ок" (кириллицей) и останавливает работу. В ином случае она печатает "Каша" и считывает следующую строку.

Примеры тестов

больше вари, ленивец
больше!
хмммм
перестань
остановись
я приказываю тебе
прекрати
остановись же
Stop!

Каша
Каша
Каша
Каша
Каша
Каша
Каша
Каша
Ок

Задача 02K. Космический корабль ≡

Условие

Запуск космического корабля это очень торжественное событие, требующее обратного отсчета.

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

На вход программа получает одно число N — количество секунд до запуска.

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

Программа должна вывести обратный отсчет от N до 1, завершающийся командой "Start". Каждый шаг отсчета сопровождается восклицательными знаками. С каждой секундой их количество увеличивается на единицу, так что команда "Start" сопровождается N восклицательными знаками.

Ограничения

1 < N < 100

Примеры тестов

5

5
4!
3!!
2!!!
1!!!!
Start!!!!!

Задача 02L. Грибы ≡

Условие

Аня очень хорошо разбирается в грибах. Грибы бывают разные. Опята, лисички. сыроежки, подосиновики, подберезовики, обабки, маслята, оленьи рожки, поганки (ядовитые). Boletus edulis (белые грибы) — самые хорошие. Нужно посчитать, сколько Boletus edulis собрала Аня.

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

В первой строке содержится число N — количество грибов. В следующих N строках — названия грибов.

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

Выходные данные должны содержать одно число — количество Boletus edulis. Регистр не имеет значения, т.е. к примеру BoLeTuS eDuLiS и bolETUS edulIS — один и тот же гриб.

Ограничения

1 ≤ N ≤ 100

Примеры тестов

7
подосиновик
камень
boletus edulis
обабок
обабок
обабок
Boletus edulis

2

5
шампиньон
лисичка
маслёнок
сыроежка
опёнок

0

Задача 02M. Таблица умножения ≡

Условие

Требуется написать программу, которая выводит таблицу умножения чисел от 1 до n.

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

Входные данные содержат одно целое число n.

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

Выходные данные должны содержать таблицу умножения числа 1 на числа от 1 до n, затем числа 2 на числа от 1 до n и т. д. Формат вывода см. в примере.

Ограничения

1 ≤ N ≤ 100

Примеры тестов

3

1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
3 * 1 = 3
3 * 2 = 6
3 * 3 = 9

Задача 02N. CamelCase ≡

Условие

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

1. Слова записываются друг за другом через знак подчёркивания с маленькой буквы (например my_variable).
2. Слова записываются друг за другом подряд, при этом каждое слово начинается с большой буквы (например MyVariable).

Рекомендуется рассмотреть частичные решения:

1. Имя состоит из одного слова

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

x

X

ATest

a_test

Задача 02O. Циклический сдвиг ≡

Условие

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

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

Первая строка содержит числа N и K Следующая строка содержит N чисел — элементы массива.

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

Необходимо вывести N чисел — исходный массив, циклически сдвинутый влево на K.

Ограничения

1 < N < 100

Примеры тестов

4 1
1 2 3 4

2 3 4 1

5 2
7 1 3 6 10

3 6 10 7 1

Задача 02P. Поэлементное сложение ≡

Условие

Требуется написать программу, которая поэлементно складывает два массива.

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

Первая строка входных данных содержит число N — длину массивов. Следующие 2 строки содержат по N чисел каждая — элементы массивов.

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

Выходные данные должны содержать N разделенных пробелом чисел — результат поэлементного сложения.

Ограничения

1 < N < 100

Примеры тестов

3
1 2 3
4 5 6

5 7 9

Задача 02Q. Форум ≡

Условие

Гости Всемирного Форума собрались по домам. Мы не знаем, представители каких делегаций были на форуме, но знаем, что делегаций не больше 197 (по количеству стран в мире). Всё, что может сказать каждый отдельный гость о себе, — номер делегации, которой он принадлежит. Необходимо рассадить гостей по автобусам так, чтобы каждой присутствующей делегации достался ровно один автобус. Какое минимальное количество автобусов нужно, чтобы рассадить гостей?

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

Входные данные содержат список чисел через пробел — номер делегации каждого отдельного гостя.

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

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

Примеры тестов

100 100 23 197 100 23 197

3

Задача 02R. Количество каждой цифры (курс Python) ≡

Условие

Петя написал на заборе N цифр. Когда Вася увидел то, что натворил Петя, он решил посчитать, сколько раз написана каждая цифра.

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел (цифр), каждое с новой строки.

Формат выходного файла

Выходной файл должен содержать 10 чисел — количество цифр 1, количество цифр 2, и т.д., количество цифр 9, количество цифр 0.

Ограничения

1 ≤ N ≤ 1000000

Примеры тестов

4
1
2
1
0

2 1 0 0 0 0 0 0 0 1

7
9
1
3
2
3
2
7

1 2 2 0 0 0 1 0 1 0

Задача 02S. Разделимся на группы ≡

Условие

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

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

Входные данные содержат список имён, каждое в своей строке.

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

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

Примеры тестов

Крош
Бараш
Человек-паук
Иванов
Петров
Сидоров

Крош, Человек-паук, Петров
Бараш, Иванов, Сидоров

Задача 02T. SQL шаблон для АБ тестов ≡

Условие

Аналитик Лёша каждый день собирает данные по АБ тестам и делает отчёты.

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

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

Помогите ему написать программу, которая для заданного АБ теста и порога генерирует SQL запрос к базе данных с помощью форматирования строки (строковой интерполяции).

Шаблон запроса:

SELECT
  id,
  SUM(product_price) AS revenue_by_user
FROM
  dataset.data_table
WHERE
  ab_test = '[название АБ теста]'
GROUP BY
  id
HAVING
  revenue_by_user < [порог]

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

Входные данные содержат две строки: нaзвание АБ теста и порог для фильтрации пользователей (целое или вещественное число).

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

Выходные данные должны содержать SQL запрос для заданного АБ теста и порога с точностью 2 знака после запятой.

Примеры тестов

Cats UI Rework
999

SELECT
  id,
  SUM(product_price) AS revenue_by_user
FROM
  dataset.data_table
WHERE
  ab_test = 'Cats UI Rework'
GROUP BY
  id
HAVING
  revenue_by_user < 999.00

Задача 02U. Поворот матрицы ≡

Условие

Пусть задана некоторая матрица A = {a_i,j}n,mi,j = 0, a_i,j ∈ {1,…,9}. Требуется написать программу, выполняющую поворот этой матрицы по часовой стрелке k ∈ Z раз. При k < 0 такой поворот эквивалентен повороту против часовой стрелки |k| раз.

В задаче запрещено пользоваться какими-либо пакетами.

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

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

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

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

Ограничения

2 ⩽ n,m ⩽ 2000

 − 100 ⩽ k ⩽ 100

Примеры тестов

3 3 3
1 2 3
4 5 6
7 8 9

3 6 9
2 5 8
1 4 7

3 3 -3
1 2 3
4 5 6
7 8 9

7 4 1
8 5 2
9 6 3

2 3 1
1 2 3
4 5 6

4 1
5 2
6 3

Задача 02V. Транспонирование квадратной матрицы ≡

Условие

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

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

Первая строка содержит число N — количество строк (и столбцов) в матрице.

Следующие N строк содержат N чисел каждая — элементы матрицы.

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

Выходные данные должны содержать N строк по N чисел каждая — элементы транспонированной матрицы.

Ограничения

1 < N < 100

Примеры тестов

3
1 2 3
4 5 6
7 8 9

1 4 7
2 5 8
3 6 9

Задача 02W. Количество слов ≡

Условие

Во входном файле записана строка текста, в которой могут встречаться:

• прописные и строчные (т.е. большие и маленькие) латинские буквы,
• пробелы,
• знаки препинания: точка, запятая, восклицательный и вопросительный знак,
• символ -, обозначающий в некоторых случаях тире, а в некоторых — дефис.

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

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4

Задача 02X. Количество слов-0 ≡

Условие

Во входном файле записана строка текста, в которой могут встречаться:

• прописные и строчные (т.е. большие и маленькие) латинские буквы,
• пробелы,
• знаки препинания: точка, запятая, восклицательный и вопросительный знак.

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

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

Примеры тестов

As God is my witness , I will never be hungry again .

11

Задача 02Y. Излишек ≡

Условие

У Влада возник излишек — 1000 рублей. Ему необходимо его срочно потратить, возможно, даже, с перерасходом. Для этого он зашел в супермаркет и кладет в корзину товары по порядку, пока их суммарная стоимость не достигнет излишка. Сколько рублей потратит Влад?

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

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

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

Выходные данные должны содержать одно число — суммарную итоговую стоимость товаров в корзине.

Примеры тестов

6
10
10
100
2000
10
10

2120

4
500
500
500
500

1000

Задача 02Z. Turing Machine ≡

Условие

Требуется выполнить программу для детерминированной машины Тьюринга.

Пусть задана машина Тьюринга с алфавитом A = {i}N − 1i = 0 и множеством состояний S = {i}Mi = 0. Программа, которую требуется выполнить, описывается тройками значений для каждой пары "символ" / "состояние"

1. Символ, который требуется записать на ленту;
2. Направление движения указателя машины: "L" — влево, "R" — вправо, "N" — не сдвигать указатель;
3. Состояние, в которое переходит машина.

Программа исполняется на бесконечной ленте заполненной символом 0. Изначально машина находится в состоянии 0 на позиции 0 и заканчивает работу при достижении состояния M.

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

Первая строка входных данных содержит натуральные числа N, M, K — размер алфавита, множества состояний и входных данных программы. Далее следуют N строк по M троек — описание программы. Строка i + 2 содержит тройки для символа i, перечисленные по возрастанию номера состояния. Последняя строка файла содержит текущие состояние ленты длины K.

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

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

Ограничения

Примеры тестов

3 3 8
0 N 3  1 R 1  0 L 2
1 N 3  0 R 1  1 L 2
2 R 1  2 L 2  2 N 3
2 0 1 0 1 0 1 2

2 1 0 1 0 1 0 2

2 4 3
1 R 1  1 L 0  1 L 1  1 N 4
1 L 2  1 R 1  1 L 3  1 L 3
0 0 0

1 1 1 1 1 1 1

4 12 4
0 N 12  0 R  1  3 L  3  0 L  3  3 R 5  0 R 5  0 R 6  0 R  7  0 R  8  0 N 12  0 R 10  0 L 11
1 N 12  1 R  1  1 N 12  1 L  3  3 R 6  1 R 5  1 R 6  1 R  7  1 R  8  1 N 12  1 R 10  1 L 11
2 R  1  2 R  2  2 N 12  2 L  4  2 R 9  2 R 7  2 R 8  2 N 12  2 N 12  2 R 10  2 N 12  2 N 12
3 N 12  3 N 12  3 N 12  3 N 12  3 L 4  3 R 5  3 R 6  0 R  2  1 R  2  2 R  9  2 L 11  3 N 12
2 1 0 2

2 0 1 2

Задача 03A. Индекс предыдущего вхождения ≡

Условие

Пусть имеется некоторый список строк. Требуется для каждой строки определить индекс предыдущего вхождения этой строки в список.

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

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

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

Выходной файл должен содержать n целых чисел — индексы предыдущих вхождений строк. Если строка встречается впервые требуется вывести -1.

Ограничения

5 ⩽ n ⩽ 200000

Примеры тестов

First string
Second string
Second string
First string
First string

-1
-1
1
0
3

Задача 03B. groupby group ≡

Условие

Необходимо написать программу, которая группирует студентов по их группам.

Формат входного файла

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

Группа и имя студента разделены символом табуляции.

Формат выходного файла

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

Сами группы следуют также в алфавитном порядке.

Ограничения

1 ≤ n ≤ 10⁵

Примеры тестов

3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan

M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача 03C. Имена файлов ≡

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

Чтобы избежать потери данных, предлагается при копировании переименовывать файлы по следующим правилам:

1. Файлы копируются в порядке перечисления в исходном каталоге.
2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

Формат входного файла

Входной файл содержит количество имён N, за которым следует N строк с именами. Имена состоят из латинских букв и цифр и имеют длину от 1 до M символов.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

Примеры тестов

4
aA
Aa
aa
AA1

aA
Aa1
aa2
AA11

Задача 03D. Add ≡

Условие

Требуется написать на языке Python функцию Add(x, y), которая принимает два числа и возвращает их сумму. Пример использования функции в примерах тестов.

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

Код решения должен содержать только определение и реализацию функции. Он не должен ничего выводить.

Примеры тестов

5

21

Задача 03E. PrintMatrix ≡

Условие

Требуется реализовать на языке Python функцию PrintMatrix(mat), которая принимает двумерный массив и печатает его. Пример использования функции в примерах тестов.

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

Код решения должен содержать только определение и реализацию функции.

Примеры тестов

1 2 3
4 5 6
7 8 9

1 2 3
4 5 6

Задача 03F. Map ≡

Условие

Требуется реализовать на языке Python функцию Map(func, l), которая принимает два параметра — функцию и список — и возвращает новый список, полученный применением функции func к элементам списка l. Пример использования функции в примерах тестов.

В решении запрещено использовать стандартную функцию map.

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

Код решения должен содержать только определение и реализацию функции. Он не должен ничего выводить на экран.

Примеры тестов

[1, 2, 3, 4]

13

Задача 03G. Join ≡

Условие

Требуется реализовать на языке Python функцию Join(array, separator), которая принимает два параметра — список строк и разделитель — и возвращает строку, полученную соединением элементов переданного списка, при этом между элементами списка вставляется разделитель (separator). Если не передать функции разделитель, то она должна использовать в качестве разделителя пробел. Пример использования функции в примерах тестов.

В решении запрещено использовать стандартную функцию join.

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

Код решения должен содержать только определение и реализацию функции. Он не должен ничего выводить.

Примеры тестов

aa!bb!cc

aa bb cc

Задача 04A. Декораторы ≡

Условие

Требуется реализовать на языке Python функции-декораторы.

Декоратор counter_decorator возвращает функцию, печатающую в консоль количество вызовов Function calls count: {n} и возвращающую результат декорируемой функцию от переданных аргументов.

Декоратор projection_decorator возвращает функцию 3-х аргументов x, y, z, которая возвращает результат декорируемой функции от аргумента 3x − 7y + 15z + 18.

from typing import Callable

def counter_decorator(f: Callable) -> Callable:
    '''Decorates `f` to print number of calls each call.'''
    pass

def projection_decorator(f: Callable[[int], None]) -> Callable[[int, int, int], None]:
    '''Decorates `f` as a function of three arguments x, y, z that calls `f` with a single argument $3x-7y+15z+18$'''
    pass

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

Код решения должен содержать только импортируемые модули, определение и реализацию функций.

Примеры тестов

Function calls count: 1
3
Function calls count: 2
9
Function calls count: 3
1

2704

Задача 04B. Норма L1 ≡

Условие

Дан вектор произвольной размерности. Необходимо посчитать так называемую норму L₁ для этого вектора. Норма L₁ — это сумма абсолютных величин компонент вектора (абсолютная величина вычисляется функцией abs).

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

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

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

Выходные данные должны содержать одно целое число — норму L₁ этого вектора.

Примеры тестов

3 4

7

10 -20 3

33

Задача 04C. Норма L2 ≡

Условие

Вам дан вектор произвольной размерности (массив вещественных чисел). Необходимо посчитать его норму L₂ (евклидову норму). Евклидова норма — это квадратный корень из суммы квадратов компонент вектора.

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

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

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

Выходные данные должны содержать одно вещественное число — евклидову норму этого вектора.

Примеры тестов

3.0 4.0

5.0

10.5 20.1 3.1

22.8882065701968

Задача 04D. Однострочник ≡

Условие

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

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

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

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

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

Примеры тестов

-1 2 -3 4 0 -5 6

36 16 4

Задача 04E. Двустрочник ≡

Условие

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

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

Входные данные содержат список целых чисел, разделенных пробелами. Гарантируется, что исходный список содержит как минимум 4 элемента.

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

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

Примеры тестов

1 2 30 40 50 6 7

1 2 50 40 30 6 7

Задача 04F. Reshape ≡

Условие

Дан вектор, состоящий из p чисел. Необходимо преобразовать вектор в матрицу размера n × m = p, состоящую из n строк и m столбцов. Матрица заполняется последовательно, то есть элементы вектора с 1 по m попадут в первую строку матрицы, с m + 1 по 2m — во вторую строку и так далее.

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

Первая строка входных данных содержат целое число p — количество элементов в входном векторе. Вторая строка содержит p целых чисел — элементы вектора. Третья строка содержит два целых числа n и m — размеры итоговой матрицы.

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

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

Примеры тестов

6
1 2 3 4 5 6
3 2

1 2
3 4
5 6

12
1 2 3 4 5 6 1 2 3 4 5 6
2 6

1 2 3 4 5 6
1 2 3 4 5 6

Задача 04G. Убрать соседа ≡

Условие

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

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

Входные данные содержат ряд чисел, разделенных пробелом.

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

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

Примеры тестов

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

Задача 04H. Будь как все ≡

Условие

Дан массив чисел. Нужно заменить в нем максимальный элемент на минимальный из этого же массива. Если максимальных несколько — заменить каждый из них.

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

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

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

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

Примеры тестов

3 -1 2 4 9 6

3 -1 2 4 -1 6

5 4 1 5 2

1 4 1 1 2

Задача 04I. Увеличить по позициям ≡

Условие

Даны массив и список индексов (номеров элементов). Нумерация начинается с 1. Необходимо прибавить единицу к каждому элементу массива, индекс которого есть в списке индексов.

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

Первая строка входных данных содержит два числа N и M — длины массива и списка индексов соответственно. Вторая строка содержит N целых чисел — элементы массива. Третья строка содержит M целых чисел — индексы.

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

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

Примеры тестов

5 3
1 2 3 4 5
1 3 5

2 2 4 4 6

Задача 04J. Game of Life ≡

Условие

Требуется написать программу, вычисляющую следующую итерацию игры «Жизнь». Игра проходит в прямоугольной области размером N на M, состоящей из символов точка (.), обозначающий мёртвую клетку, и решётка (#), обозначающий живую. Новое состояние каждой клетки определяется состоянием её 8 соседей по следующим правилам:

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

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

Входные данные содержат текущее состояние игры.

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

Выходные данные должны содержать следующую итерацию игры в том же формате.

Ограничения

1 ⩽ N,M ⩽ 100

Примеры тестов

....
.##.
.##.
....

....
.##.
.##.
....

.....
..#..
..#..
..#..
.....

.....
.....
.###.
.....
.....

Задача 05A. dir ≡

Условие

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

Названия приватных методов начинаются с символа '_' (ascii 95).

Задача 05B. dir* ≡

Условие

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

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

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

Задача 05C. Time ≡

Условие

Требуется реализовать на языке Python класс Time.

У класса должен быть следующий интерфейс:

class Time:
    # Конструктор, принимающий четыре целых числа: часы, минуты, секунды и миллисекунды.
    # В случае, если передан отрицательный параметр, вызвать исключение ValueError.
    # После конструирования, значения параметров времени должны быть корректными:
    # 0 <= GetHour() <= 23
    # 0 <= GetMinute() <= 59
    # 0 <= GetSecond() <= 59
    # 0 <= GetMillisecond() <= 999
    def __init__(self, hours=0, minutes=0, seconds=0, milliseconds=0):
        pass
    def GetHour(self):
        pass
    def GetMinute(self):
        pass
    def GetSecond(self):
        pass
    def GetMillisecond(self):
        pass
    # Прибавляет указанное количество времени к текущему объекту.
    # После выполнения этой операции параметры времени должны остаться корректными.
    def Add(self, time):
        pass
    # Оператор str должен представлять время в формате
    # HH:MM:SS.milliseconds
    def __str__(self):
        pass

   

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

Код решения должен содержать только определение и реализацию класса.

Примеры тестов

01:11:12.1
01:11:13.11

Задача 05D. ShiftableList ≡

Условие

Требуется реализовать на языке Python класс ShiftableList(list), который наследуется от list и реализует операторы циклического сдвига влево (<<) и вправо (>>). Результатом выполнения этих операций должен быть новый объект, при этом исходный не изменяется. Если операнд справа от оператора сдвига имеет тип, отличный от int, необходимо вызвать исключение TypeError. В случае, если величина сдвига отрицательна, должен выполниться сдвиг в противоположную сторону на количество позиций, равное модулю этой величины.

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

Код решения должен содержать только определение и реализацию класса.

Примеры тестов

b, c, a

abc cab

Задача 05E. CardStack ≡

Условие

Требуется реализовать на языке Python класс CardStack. У класса должен быть следующий интерфейс:

from __future__ import annotations
from typing import Union, Iterable, List

class CardStack:

    values: List[int]

    def __init__(self, val: Union[int, Iterable[int], None] = None):
      """If val is None values is an empty list
         If val is int fills values with val random integers between -100 and 100
         If val is Iterable[int] fills values from val
      """
      pass

    def shuffled(self) -> CardStack:
      """Returns a new CardStack instance with shuffled values"""
      pass

    def combine(self, other: CardStack) -> CardStack:
      """Returns a new CardStack instance with self and other values combined one after another
         [1, 2, 3], [4, 5, 6, 7] -> [1, 4, 2, 5, 3, 6, 7]
      """
      pass

    def add(self, value: int) -> None:
      """Adds a new value on top of the stack"""
      pass

    def __len__(self) -> int:
      """Returns the size of the stack"""
      pass

Описание интерфейса использует аннотации типов, в частности, Union, List и Iterable.

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

Код решения должен содержать только определение и реализацию класса.

Задача 05F. @property ≡

Условие

Требуется реализовать на языке Python класс Student со свойством name с геттером и сеттером.

class Student:

    def __init__(self):
        pass

    @property
    def name(self) -> str:
        pass
            

Сеттер свойства name должен позволять присваивать только строки, состоящие из пробелов и букв английского алфавита (в любом регистре), в остальных случаях требуется бросать исключение ValueError.

Задача 05G. Property ≡

Условие

Требуется реализовать на языке Python класс Property. У класса должен быть следующий интерфейс:

from __future__ import annotations
from collections.abc import Callable
from typing import Any, Generic, TypeVar

C = TypeVar('C')

class Property(Generic[C]):

    def __init__(self, getter:  Callable[[C],       Any] | None = None,
                       setter:  Callable[[C, Any], None] | None = None,
                       deleter: Callable[[C],      None] | None = None,
                       doc: str | None = None,
                       default_value: list[Any] | None = None):
        '''Property decorator, supporting getting, setting, deleting handled property.

        Generic:
    
            C: the class property is setup for

        Arguments:
    
            getter: member function that handles getting the value
            setter: member function that handles setting the value
            deleters: member function that handles deleting the value
            doc: general documentation for the property
            default_value: if setter is not None calls it with `default_value` on object initialization'''
        pass

    def getter(self, getter: Callable[[C], Any]) -> Property[C]:
        '''Adds getter to the property
        
        Arguments:
            getter: member function that handles getting the value

        Returns:
            A copy of Property with updated getter value'''
        pass

    def setter(self, setter: Callable[[C, Any], None] | None = None, default_value: Any | None = None) -> Property[C] | Callable[[Callable[[C, Any], None]], Property[C]]:
        '''Adds setter to the property
        
        Arguments:
            setter: member function that handles setting the value
            default_value: a value that is passed to `setter` on object initialization
        
        Returns:
            If `setter` is None returns a shorthand decorator function with set `default_value`.
            If `setter` is not None returns a copy of Property with updated setter and default_value arguments'''
        pass

    def deleter(self, deleter: Callable[[C], None]) -> Property:
        '''Adds deleter to the property
        
        Arguments:
            deleter: member function that handles deleting the value

        Returns:
            A copy of Property with updated deleter value'''
        pass

Класс должен повторять функционал стандартного property языка Python: позволять создавать свойства с установленными setter, getter, deleter и бросающий исключение AttributeError при попытке использования неустановленного метода со следующими сообщениями

• 'Cannot read {name}',
• 'Cannot set {name},
• 'Cannot delete {name},

В дополнение к этому появление такого свойства в классе должно после инициализации объекта добавлять к нему поле '_{name}' со значением None и единожды вызывать setter объекта со значением default_value, если свойство поддерживает присваивание.

Документация для свойства должна состоять из максимум 5-ти частей

• Строка "Property '{name}' on class {cls_name}", где cls_name имя класса, в который добавлено свойство.
• Аргумент doc, указанный при инициализации свойства, если он не равен None.
• Документация для функции getter, если свойство поддерживает получение значения.
• Документация для функции setter, если свойство поддерживает присваивание.
• Документация для функции deleter, если свойство поддерживает удаление.

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

Код решения должен содержать только импортируемые модули, определение и реализацию класса.

Примеры тестов

None
Petya

Property 'name' on class Person

Name of a person, str

Getter:

        Returns the name

Setter:

        Sets the name, must be of type str

Deleter:

        Sets the name to None
Vasya
Petya
None

Задача 05H. lru_cache ≡

Условие

Требуется реализовать на языке Python декоратор lru_cache. У функции должен быть следующий интерфейс:

from typing import Any, Callable, Hashable, Optional

HashableCallable = Callable[[Hashable, ...], Any]

def lru_cache(f: Optional[HashableCallable] = None, *, maxsize: int = 128) -> HashableCallable | Callable[[HashableCallable], HashableCallable]:
    '''Decorator to wrap a function with a memoizing callable that saves up to the `maxsize` most recent calls.

    Arguments:
        f: a function to decorate
        maxsize: maximal number of cached entries

    Returns:
        If `f` is None returns a shorthand decorator function with set `maxsize`.
        If `f` is not None return decorated function
    '''
    pass

В результате декорации функция должна кэшировать maxsize последних вызовов функции, где ключём являются переданные в функцию аргументы. То есть, при добавлении нового значения в кэш максимального размера из него будет удалена запись, которая была использована наиболее давно. Подробнее про LRU cache можно прочитать здесь. Гарантируется, что все передаваемые значения хэшируемы и могут быть использованы в качестве ключа словаря.

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

foo(1, 2) -> ((1, 2), ())
foo(1, b=2) -> ((1, ), (('b', 2), ))
foo(a=1, b=2) -> ((), (('a', 1), ('b', 2), ))

Возвращаемая в результате декорации функция должна также иметь следующие поля-функции.

import collections

CacheInfo = collections.namedtuple('CacheInfo', ['hits', 'misses', 'maxsize', 'currsize'])

def cache_info() -> CacheInfo:
    '''Returns information about cache state showing the following properties:

    hits: int, how many times decorated function result was pulled from cache
    misses: int, how many times decorated function was called
    maxsize: int, maximal cache size
    currsize: int, current cache size
    '''
    pass


def clear_cache():
    '''Clears cache'''
    pass


def cache_state() -> dict[tuple[tuple[Hashable, ...], tuple[tuple[str, Hashable], ...]], Any]:
    '''Returns current cache state: a dict-like object contatining
    mapping from function arguments specification to function result for these arguments.

    Arguments specification is a tuple with two elements:
        first element is a tuple containing positional arguments,
        second element is a tuple of tuples containing key, value pairs for keyword arguments passed to the function

    Arguments are saved in order they were passed to the function
    '''
    pass

Функция cache_info возвращает именованный tuple CodeInfo с полями

• hits — количество вызовов функции, при которых результат был возвращён из кэша
• misses — количество вызовов функции, при которых результат был вычислен путём вызова декорируемой функции
• maxsize — максимальный размер кэша
• currsize — количество элементов в кэше на данный момент.

Функция clear_cache удаляет все элементы в кэше.

Функция cache_state возвращает словарь, отображающий текущее состояние кэша. Элементы словаря должны быть расположены в порядке "недавности" их использования.

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

Код решения должен содержать только импортируемые модули, определение и реализацию функций.

Примеры тестов

141693817714056513234709965875411919657707794958199867
CacheInto(hits=254, misses=257, maxsize=128, currsize=128)

3 7 3 11
{((5, 6), ()): 11, ((1, 2), ()): 3}

Задача 05I. Проверка типов ≡

Условие

Требуется реализовать на языке Python функцию-декоратор check_types, выполняющую проверку параметров и возвращаемого значения функции на соответствие аннотации при вызове функции. Функция должна поддерживать list, dict, Any, tuple, Optional, Union, set (см. typing) и проверку на полное соответствие типу, при этом объекты классов наследников разрешается передавать как объекты классов родителей. Если вызов функции не проходит проверку, необходимо вызвать исключение TypeCheckError, имеющее следующий интерфейс

class TypeCheckError(BaseException):
    
    # Имя аргумента, которому было передано значение неверного типа. `return`, если функция вернула значение неверного типа
    name: str

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

Все тесты используют следующий функционал

from __future__ import annotations

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

Код решения должен содержать определение функции check_types и класса TypeCheckError, а также все вспомогательные переменные, функции и классы.

Примеры тестов

3
Failed a

Failed return

3
Failed other

4
1 8 27
Failed x

Задача 05J. dataclass_lite ≡

Условие

Требуется реализовать на языке Python декоратор dataclass_lite. Декоратор должен добавлять к переданному классу метод __init__, имеющий аргументы, соответствующим полям, заданным в классе, аналогично dataclasses.dataclass. Гарантируется, что класс не определяет функцию __init__. Полученная функция должна удовлетворять следующим требованиям.

• Первый аргумент функции должен иметь имя self и являться только позиционным.
• Последующие аргументы должны быть заданы в порядке определения полей класса.
• Аргумент функции должен иметь ту же аннотацию, что и соответствующее ему поле класса.
• Если полю класса присвоено некоторое значение x, то соответствующий ему аргумент должен иметь значение по умолчанию. Значение по умолчанию строится следующим образом.
  • Если x является объектом класса field.
    • При x.default is not MISSING значением по умолчанию является x.default.
    • При x.default_factory is not MISSING значением по умолчанию является объект класса factory. В таком случае соответствующему полю будет присвоено значение, полученное путём вызова x.default_factory(), если аргументу не было передано иного значения.
    • Гарантируется, что хотя бы одно из этих полей имеет значение MISSING.
    • При x.kw_only == True, передача соответствующего аргумента должна быть возможна только по имени. Гарантируется, что в таком случае хотя бы одно значение из x.default и x.default_factory не является MISSING.
  • Иначе значением по умолчанию является x. Гарантируется, что repr(x) является выражением, создающим копию x при его выполнении.
• В результате инициализации, объект класса должен иметь поля, инициализированные согласно переданным в функцию инициализации аргументам.

Функция dataclass_lite вызывает следующие исключения.

• RuntimeError('non-default argument follows default argument'), если аргумент без значения по умолчанию следует после аргумента со значением по умолчанию.
• RuntimeError('non-kwonly argument follows kwonly argument'), если аргумент, передача которого разрешена по позиции, следует за аргументом, передача которого возможно только по имени.

При тестировании попытки в пространстве имён доступны следующие объекты

MISSING = object()

class field:

    def __init__(self, *, default: Any = MISSING, default_factory: Callable[[], Any] | MISSING = MISSING, kw_only: bool = False):
        '''Represents dataclass_lite field.

        Arguments:
            default: default value to be assigned to the field
            default_factory: function to be used to generate default value for the field
            kw_only: indicates if corresponding argument in initialization function is keyword only'''

        if default is not MISSING and default_factory is not MISSING:
            raise ValueError("'default' and 'default_factory' cannot be specified at the same time")

        self.default = default
        self.default_factory = default_factory
        self.kw_only = kw_only

class factory:
    '''A special value to be used as default for fields with factory initialization.'''

    def __repr__(self):
        return '[factory]'

Все тесты используют следующий функционал

from __future__ import annotations

При решении предполагается использование следующих функций и модулей exec, compile, ast.

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

Код решения должен содержать только импортируемые модули, определение и реализацию функции.

Примеры тестов

Help on function __init__ in module __main__:

__init__(self, /, name: 'str', age: 'int')

Vasya 23
Petya 42

Help on function __init__ in module __main__:

__init__(self, /, name: 'str', age: 'int', *, children: 'list[Person]' = [factory])

Vasya 23 []
Petya 42 Vasya

Задача 06A. Factor integer ≡

Условие

Требуется реализовать на языке программирования Python функцию

from collections.abc import Generator

def factor_integer(n: int) -> Generator[int, None, None]:
    '''Yields all factors of `n` in ascending order, repeating each factor the number of times equal to its exponent.
        
    Args:
        n: integer to factor

    '''
    pass

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

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

Код решения должен содержать только определение и реализацию функции.

Примеры тестов

2 2 5 5

Задача 06B. hmm_forward ≡

Условие

Требуется реализовать на языке программирования Python функцию

from typing import TypeVar
from collections.abc import Generator, Hashable

S = TypeVar('S', bound=Hashable) # state type
O = TypeVar('O', bound=Hashable) # observation type
def hmm_forward(
    initial_probability: dict[S, float],
    transition_probability: dict[S, dict[S, float]],
    observation_probability: dict[S, dict[O, float]]
) -> Generator[S, O, dict[S, float]]:
    """Implements [forward alogirthm](https://en.wikipedia.org/wiki/Forward_algorithm) for a hidden markov model.
    Each iteration the generator output the most porbable state of the model, receiving new observations through `send` method.
    Iteration stops after `None` value has been received and the generator outputs a dictionary mapping each state to its propability.

    Arguments:
        initial_probability: initial state probabilitites
        transition_probability: probabilities of transition from one state to another
        observation_probability: probabilities to observe each of the observations at each of the states

    Yields:
        most probable state

    Returns
        a mapping from each state to its propability
    """
    pass

Функция выполняет Forward algorithm для заданной скрытой марковской модели с начальными вероятностями initial_probability, вероятностями перехода transition_probability и вероятностями наблюдений observation_probability. Функция возвращает объект типа генератор, производящий на каждой итерации наиболее вероятное состояние модели. Генератор получает новые наблюдения через метод send. При получении значения None генератор останавливается и возвращает словарь вероятностей каждого состояния.

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

Код решения должен содержать только импортируемые модули, определение и реализацию функции.

Примеры тестов

rain
rain
rain
sun
rain
rain
rain 0.867
sun 0.133
        

Задача 06C. stack_chain ≡

Условие

Требуется реализовать на языке Python класс stack_chain. У класса должен быть следующий интерфейс:

from __future__ import annotations

from collections.abc import Iterable, Iterator

class stack_chain:

    def __init__(self, *iterables: Iterable):
        """Iterates over iterables in Last In First Out order.

        Arguments:
            iterables: iterables to iterate over"""
        raise NotImplementedError()

    def __iter__(self) -> Iterator:
        """Returns iterator over stored iterables"""
        raise NotImplementedError()

    def __iadd__(self, iterable: Iterable) -> stack_chain:
        """Add a new iterable on top of stack in-place

        Arguments:
            iterable: iterable to add

        Returns:
            self
        """
        raise NotImplementedError()

Класс должен удовлетворять Iterable. stack_chain итерируется по iterables в порядке «последним пришёл — первым ушёл». Объект должен позволять добавлять новый Iterable на вершину стека с использованием оператора +=.

Возвращаемый итератор должен позволять продолжать итерацию после вызова исключения StopIteration, если в stack_chain был добавлен новый Iterable.

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

Код решения должен содержать только импортируемые модули, определение и реализацию класса.

Примеры тестов

0 1 4 2 1 0 0 1 2

0 1 0 2 1 0 1 0

Задача 06D. Take ≡

Условие

Требуется реализовать на языке программирования Python функцию

from typing import TypeVar
from collections.abc import Generator, Iterable

T = TypeVar('T')
def take(iterable: Iterable[T], *, skip: int = 0, step: int = 1, count: int | None = None) -> Generator[T, None, None]:
    '''Yields every `step`-th value from `iterable` skipping first `skip` values.
    If `count` is not None yields this many values at most.
        
    Args:
        iterable: Iterable to take values from
        skip: Number of values to skip from the beginning, non-negative integer
        step: Skip `step` - 1 values between every yield, positive integer
        count: Yields this many values at most, None or non-negative integer

    Raises:
        ValueError:
            `skip` or `count` is less than 0
            `step` is less than 1
        TypeError:
            `skip`, `step` is not an int or `iterable` is not an Iterable
            `count` is not an int or None

    '''
    pass

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

Код решения должен содержать только определение и реализацию функции.

Примеры тестов

5 10 15 20 25

Задача 06E. Pipeline ≡

Условие

Требуется реализовать на языке Python класс Pipeline. У класса должен быть следующий интерфейс:

from __future__ import annotations

from typing import Any
from collections.abc import Callable, Generator, Iterable, Iterator

class Pipeline:

    def __init__(self,
                 *data: Iterable,
                 func: Callable[[Any, ...], Any] | None = None,
                 name: str | None = None):
        """Iterates over `data` applying `func` if available.

        Arguments:
            data: iterables to iterate over
            func: callable to apply to iterables, elements of iterables are passed as positional arguments
            name: name of the operation
        """
        raise NotImplementedError()

    @property
    def name(self) -> str | None:
        """Obtains name of the operation."""
        raise NotImplementedError()

    def walk(self) -> Generator[Pipeline]:
        """Iterates over iterables tree depth first in the order passed during initialization returning Pipeline objects"""
        raise NotImplementedError()

    def __or__(self, func: Callable[[Any], Any] | tuple[Callable[[Any], Any], str]) -> Pipeline:
        """Creates a new Pipeline applying `func` to elements of `self`"""
        raise NotImplementedError()

    def __matmul__(self, func: Callable[[Any, ...], Any] | tuple[Callable[[Any, ...], Any], str]) -> Pipeline:
        """Creates a new Pipeline applying `func` to unpacked elements of `self`"""
        raise NotImplementedError()

    def __add__(self, other: Iterable) -> Pipeline:
        """Creates a new copy of `self` adding `other` to the list of iterables"""
        raise NotImplementedError()

Класс должен удовлетворять Iterable. При итерации по Pipleine возвращаются объекты типа tuple {a_i}n − 1i = 0, где a_i текущий элемент data_i. При n = 1 возвращается единственный элемент a₀. Если func is not None, элементами Pipeline являются результаты применения функции: func(a_0, a_1, ..., a_{n-1}).

Свойство name возвращает имя Pipeline. Если имя не было указано при инициализации используется имя func. Если и func было опущено, возвращается None.

Результатом вызова метода walk является генератор, возвращающий элементы дерева, являющиеся объектами класса Pipeline при обходе в глубину в порядке, указанном в data.

Класс должен определять следующие операции

• Pipeline | Callable — создаёт новый объект типа Pipeline, применяя Callable к элементам исходного Pipeline.
• Pipeline | (Callable, str) — аналогично предыдущему, но передавая str в качестве имени.
• Pipeline @ Callable — создаёт новый объект типа Pipeline, применяя Callable к распакованным элементам исходного Pipeline.
• Pipeline @ (Callable, str) — аналогично предыдущему, но передавая str в качестве имени.
• Pipeline + Iterable — создаёт новый объект типа Pipeline, добавляя Iterable к data.

Класс должен переопределять операцию repr. Результатом должна являться строка, представляющая собой создание объекта Pipeline, при этом вместо функции указывается её имя без кавычек, а аргументы, имеющие значение None не указываются.

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

Код решения должен содержать только импортируемые модули, определение и реализацию класса.

Примеры тестов

Pipeline([1, 2, 3, 4, 5], name='data1')
Pipeline([5, 4, 3, 2, 1], Pipeline([1, 2, 3, 4, 5], name='data1'))
(1, (5, 1)) (2, (4, 2)) (3, (3, 3)) (4, (2, 4)) (5, (1, 5))

Pipeline(Pipeline(Pipeline([1, 2, 3], func=square), [3, 2, 1], name='zip'), func=<lambda>, name='sum')
4 6 10

Pipeline(Pipeline([1, 2, 3], [3, 2, 1], name='zip'), func=<lambda>, name='sum')
4 4 4

7 8 11
data1 -> square -> data2 -> times_two -> zip -> sum

Pipeline([1, 2, 3], [4, 5, 6], name='data')
(1, 4) (2, 5) (3, 6)

Задача 07A. Среднее арифметическое ≡

Условие

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

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

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

Формат выходного файла

Выходные данные должны содержать единственное число — среднее арифметическое выборки с точностью не менее 3 знаков после запятой.

Ограничения

1 < n < 10⁵

Примеры тестов

3
1 3 5

3

Задача 07B. Среднее гармоническое ≡

Условие

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

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 < n < 10⁵

Примеры тестов

3
1 3 5

1.957

Задача 07C. Средние взвешенные ≡

Условие

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

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

Входные данные содержат число n, за которым следует n строк, состоящих из пар чисел: вещественное число x_i и соответствующая ему частота m_i (т.е. количества элементов x_i в исходной выборке).

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 300, 1 ≤ m_i ≤ 5, 0 < x_i < 3

Примеры тестов

2
2 4
3 4

2.5 2.4 2.449

Задача 07D. Метод скользящего среднего ≡

Условие

Пусть задан временной ряд {y_t}nt = 1. Требуется написать программу, вычисляющую сглаженный ряд {ŷ_t}n − m / 2t = m / 2, где m — ширина интервала сглаживания.

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

Первая строка входных данных содержит два целых числа n и m. Следующая строка содержит n вещественных чисел — уровни ряда y_t.

Формат выходного файла

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

Ограничения

1 < n < 10⁵

3 ⩽ m ⩽ 15

Примеры тестов

9 3
5 2 5 5 8 5 5 2 5

4 4 6 6 6 4 4

Задача 07E. Метод скользящего взвешенного среднего ≡

Условие

Пусть задан временной ряд {y_t}nt = 1. Требуется написать программу, вычисляющую сглаженный ряд {ŷ_t}n − m / 2t = m / 2 с использованием весов {w_i}mi = 1 для расчёта среднего, где m — ширина интервала сглаживания.

Формат входного файла

Первая строка входных данных содержит два целых числа n и m. Далее следуют m целых чисел — веса w_i. Последняя строка содержит n вещественных чисел — уровни ряда y_t.

Формат выходного файла

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

Ограничения

1 < n < 10⁵

3 ⩽ m ⩽ 15

Примеры тестов

9 3
1 2 1
5 1 5 5 9 5 5 1 5

3 4 6 7 6 4 3

Задача 07F. Корреляция ≡

Условие

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

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

Первая строка входных данных содержит целые числа N и M — количество и длину выборок соответственно. Каждая из последующих N строк содержит по M вещественных чисел.

Формат выходного файла

Выходные данные должны содержать матрицу размером N × N — матрицу коэффициентов корреляции. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.

Ограничения

2 ≤ N < 50, 1 < M < 10⁴

Примеры тестов

2 10
6 -10 10 -5 -8 -4 4 -5 0 4
4 -5 3 10 -2 -1 -6 -2 2 -8

1 0.075
0.075 1

3 10
2 -3 -6 -3 0 0 -7 6 -1 -8
-5 5 4 1 13 10 -10 -1 9 2
4 -2 4 3 5 4 -1 0 3 4

1 0.158 0.01
0.158 1 0.462
0.01 0.462 1

Задача 07G. Центральный момент ≡

Условие

Задана выборка {x_i} объёма n. Требуется вычислить выборочный центральный момент k-го порядка.

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

Входные данные содержат числа n и k, за которыми следует n вещественных чисел разделённых пробелом.

Формат выходного файла

Выходные данные должны содержать единственное вещественное число — выборочный центральный момент k-го порядка с точностью не менее трёх знаков после запятой.

Ограничения

1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 5

Примеры тестов

10 1
1 4 5 4 4 5 1 5 2 3

0

10 2
7 8 -2 -8 8 -3 9 -6 1 -2

36.16

Задача 07H. Гистограмма ≡

Условие

Пусть имеется выборка {x_i}ni = 1. Для построения гистограммы необходимо разбить выборку на интервалы равной длины [b₁, b₂), [b₂, b₃) … [b_k, b_k + 1], b₁ = mini x_i, b_k + 1 = maxi x_i.

Число k - оптимальное количество интервалов - вычисляется согласно формуле Стёрджеса k = 1 + ⌊log₂ n⌋, где ⌊ ...⌋ — антье.

При решении задачи необходимо использовать библиотеку numpy.

Формат входного файла

Входные данные содержат число n, за которым следует n вещественных чисел.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 10⁴

Примеры тестов

3
0 1 2

1 2

6
8 9 2 1 2 0

4 0 2

6
8 9 1 2 0 10

3 0 3

Задача 07I. Nearest point ≡

Условие

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

import numpy as np

def nearest(points: np.ndarray, a: np.ndarray) -> np.ndarray:
    '''Returns the point from `points` nearest to `a` in terms of euclidean distance

    Args:
        points: A 2-dimensional np.ndarray
        a: A 1-dimensional np.ndarray, `a`.shape[0] == `points`.shape[1]

    '''
    pass

При решении задачи необходимо использовать библиотеку numpy.

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

Код решения должен содержать только определение и реализацию функции.

Примеры тестов

print(*nearest(np.array([[0, 0], [3, 3]]), np.array([1, 1])))

0 0

Задача 07J. Calculate distance ≡

Условие