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

Условие

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

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

Условие

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

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

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

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

Задача 1C. Представьтесь ≡

Условие

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

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

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

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

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

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

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

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

Джеймс
Бонд

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

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

Условие

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

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

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

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

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

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

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

sporyshev
ms
students

sporyshev.ms@students.dvfu.ru

Задача 1E. Солнечный день ≡

Условие

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

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

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

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

10
1
15

5

1000
9
9

81

Задача 1F. Олины торты ≡

Условие

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

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

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

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

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

Ограничения

1 < N, M < 10000

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

10
2

5

6
4

1.5

Задача 2A. Простое ≡

Условие

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

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

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

Просто!

:)

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

:(

Задача 2B. Сложное ≡

Условие

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

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

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

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

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

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

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

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

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

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

Ничего

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

Задача 2C. FizzBuzz ≡

Условие

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

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

23

25

Buzz

30

FizzBuzz

Задача 2D. Кто первый? ≡

Условие

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

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

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

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

Программа должна напечатать фамилию студента, который пойдет к доске первым.

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

Петров
Иванов
Сидоров

Иванов

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

4
cha
g'thazag
mog
Bin

Bin
mog
g'thazag
cha

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ A, B ≤ 10⁶

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

3 14

16

9 1

0

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

Условие

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

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

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

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

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

18 25
7 37

2 2

Задача 2H. Вася и мысли ≡

Условие

Юный программист Вася любит прогуливаться по тропинке длиной 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

Задача 2I. Вокруг дома ≡

Условие

Васин дом имеет в плане форму прямоугольника. Северная и южная стороны имеют длину по 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

Задача 3A. Горшочек каши ≡

Условие

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

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

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

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

Задача 3B. Грибы ≡

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

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

2

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

0

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

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

5

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

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

Условие

Требуется написать программу, которая выводит таблицу умножения чисел от 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

Задача 3E. CamelCase ≡

Условие

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

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

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

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

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

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

Ограничения

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

x

X

ATest

a_test

Задача 3F. Циклический сдвиг ≡

Условие

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

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

Первая строка содержит числа 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

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

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

3
1 2 3
4 5 6

5 7 9

Задача 3H. Форум ≡

Условие

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

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

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

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

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

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

100 100 23 197 100 23 197

3

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

Условие

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

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

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

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

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

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

11

Задача 3J. Количество слов ≡

Условие

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

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

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

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

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

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

Ограничения

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

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4

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

Условие

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

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

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

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

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

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

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

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

Задача 3L. Количество каждой цифры (курс 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

Задача 3M. 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

Задача 3N. Имена файлов ≡

Условие

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

Задача 3O. 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

Задача 3P. Поворот матрицы ≡

Условие

Пусть задана некоторая матрица 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

Задача 4A. Излишек ≡

Условие

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

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

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

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

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

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

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

6
10
10
100
2000
10
10

2120

4
500
500
500
500

1000

Задача 4B. Будь как все ≡

Условие

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

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

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

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

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

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

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

3 -1 2 4 9 6

3 -1 2 4 -1 6

5 4 1 5 2

1 4 1 1 2

Задача 4C. Палиндром? ≡

Условие

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

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

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

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

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

Выходные данные должны содержать True, если фраза — палиндром, и False в противном случае.

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

А роза упала на лапу Азора

True

Роза не упала на лапу Азора

False

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

Условие

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

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

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

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

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

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

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

5 3
1 2 3 4 5
1 3 5

2 2 4 4 6

Задача 4E. Энтое слово ≡

Условие

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

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

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

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

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

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

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

FEFU was established in 1899 as the Eastern Institute
5

1899

FEFU was established
5

established

Задача 4F. Норма L1 ≡

Условие

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

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

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

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

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

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

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

3 4

7

10 -20 3

33

Задача 4G. Норма L2 ≡

Условие

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

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

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

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

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

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

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

3.0 4.0

5.0

10.5 20.1 3.1

22.8882065701968

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

Условие

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

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

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

Первая строка содержит число 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

Задача 4I. Reshape ≡

Условие

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

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

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

Первая строка входных данных содержат целое число 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

Задача 4J. Убрать соседа ≡

Условие

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

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

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

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

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

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

Задача 4K. Key sort ≡

Условие

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

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

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

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

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

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

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

azx zab ddd

zab ddd azx

Задача 4L. Однострочник ≡

Условие

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

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

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

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

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

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

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

-1 2 -3 4 0 -5 6

36 16 4

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

Условие

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

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

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

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

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

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

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

1 2 30 40 50 6 7

1 2 50 40 30 6 7

Задача 4N. GCD ≡

Условие

Дано 3 числа: A, B, C. Необходимо посчитать наибольший общий делитель (НОД) каждой из пар A и B, A и C, B и C

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

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

Входные данные содержат 3 числа — A, B, C.

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

Выходные данные должны содержать 3 числа — НОД A и B, НОД A и C и НОД B и C

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

2 6 3

2 1 3

Задача 4O. Add ≡

Условие

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

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

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

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

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

5

21

Задача 4P. PrintMatrix ≡

Условие

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

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

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

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

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

1 2 3
4 5 6
7 8 9

1 2 3
4 5 6

Задача 4Q. Map ≡

Условие

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

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

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

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

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

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

[1, 2, 3, 4]

13

Задача 4R. Game of Life ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ⩽ N,M ⩽ 100

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

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

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

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

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

Задача 4S. Join ≡

Условие

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

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

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

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

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

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

aa!bb!cc

aa bb cc

Задача 4T. groupby group ≡

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan

M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача 5A. Hello world ≡

Условие

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

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

class Hello_world:
    # Конструктор
    def __init__(self):
      pass

    # Функция, по умолчанию возвращающая "Hello world!". В случае 
    # использования set_new_hello_world возвращаемое значение изменяется.
    def get_hello_world(self):
        pass

    # Функция, изменяющая возвращаемое функцей get_hello_world значение на new_hello_world.
    def set_new_hello_world(self, new_hello_world):
        pass

   

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

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

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

hello = Hello_world()
print(hello.get_hello_world())

Hello world!

hello = Hello_world()
print(hello.get_hello_world())

hello.set_new_hello_world('zbc')
print(hello.get_hello_world())

hello.set_new_hello_world('Python')
print(hello.get_hello_world())

Hello world! 
zbc
Python

Задача 5B. 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

Задача 5C. ShiftableList ≡

Условие

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

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

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

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

b, c, a

abc cab

Задача 5E. dir ≡

Условие

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

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

Задача 5F. dir* ≡

Условие

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

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

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

Задача 5G. 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.

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

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

Задача 6A. Простой декоратор ≡

Условие

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

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

      
      def time_decorator (decorated_func):
        pass
      
    

      
      def counter_decorator(decorated_func):
        pass
      
    

      
      def method_decorator(decorated_method):
        pass 
      
    

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

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

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

@time_decorator
def floyd_warshall (n):
  dp = [[0] * n for i in range(n)]
  for i in range(n):
    for j in range(n):
      if (i == j):
        dp[i][j] = 0
      else:
        dp[i][j] = random.randint(1, n)

  for k in range(n):
    for i in range(n):
      for j in range(n):
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

  sum = 0
  for i in range(n):
    for j in range(n):  
      sum += dp[i][j]

  print(sum)

floyd_warshall(100)

Start time: 1545320524.501671
70943
End time: 1545320524.830567
Execution time: 0.32890844345092773

def sum (a, b):
  print(a + b)

fn = counter_decorator(sum)
fn(1, 2)
fn(4, 5)
fn(-4, 5)

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

class do_it:
  def __init__(self):
    pass

  @method_decorator
  def calc(self, x):
    print(x * x)

obj = do_it()
obj.calc(1, 2, 3)

2704

Задача 6B. @property ≡

Условие

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

class Student:

    def __init__(self):
        pass

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

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

Задача 6C. 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

Задача 6D. Проверка типов ≡

Условие

Требуется реализовать на языке 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

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

Условие

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

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

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

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

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

Ограничения

1 < n < 10⁵

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

3
1 3 5

3

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

Условие

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

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

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

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

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

Ограничения

1 < n < 10⁵

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

3
1 3 5

1.957

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

Условие

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

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

Входные данные содержат число 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

Задача 7D. Гистограмма ≡

Условие

Пусть имеется выборка {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⌋, где ⌊ ...⌋ — антье.

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

Входные данные содержат число 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

Задача 7E. Корреляция ≡

Условие

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

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

Первая строка входных данных содержит целые числа 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

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

Условие

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

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

Входные данные содержат числа 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

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

Условие

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

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

Первая строка входных данных содержит два целых числа 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

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

Условие

Пусть задан временной ряд {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

Задача 7I. 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

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

Условие

Существует набор линий в двумерном пространстве. В этом же пространстве присутствует точка point. Необходимо найти кратчайшие расстояния до всех линий. Требуется реализовать на языке Python функцию, позволяющую находить расстояния от точки point до всех линий. Результатом выполнения этой функции должен быть массив расстояний. Работа должна быть выполнена с применением numpy для хранения и обработки всех данных.

import numpy as np

def calculate(start_points: np.ndarray, end_points: np.ndarray, point: np.ndarray) -> np.ndarray:
    '''Возвращает одномерный np.ndarray, содержащий расстояния до линий

    Args:
        start_points: двумерный np.ndarray, содержащий координаты первых точек линий
        end_points: двумерный np.ndarray, содержащий координаты вторых точек линий
        p: двумерный np.ndarray, содержайщий координаты точки point.
        
        start_points.shape == end_points.shape

    Returns:
        одномерный np.ndarray, содержащий расстояния от точки point до линий
    '''
    pass

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

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

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

1. 1.11115→ 1.1112
2. 1.11105→ 1.1110
3. 1.11107→ 1.1111
4. 1.11103→ 1.1110

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

print(*calculate(
        np.array([[1,  2.5]]),
        np.array([[3,  2.5]]),
        np.array([[2, 1]])))

1.5

print(*calculate(
        np.array([[1, 2.5], [3.5, 3], [3.5, 4]]),
        np.array([[3, 2.5], [3.5, 0.5], [2.5, 5]]),
        np.array([[2.5, 4]])))

1.5 1. 0.7071

Задача 7K. Game of Life with Numpy ≡

Условие

Требуется реализовать на языке Python класс GameOfLife. Класс описывает обобщённую игру «Жизнь». Игра представляет собой многомерный (n >= 2) массив булевых значений. Каждая ячейка может быть живой (True) или мёртвой (False). На каждой итерации состояние игры обновляется следующим образом:

• Живая ячейка остаётся живой, если она имеет от a до b включительно живых соседей
• Мёртвая ячейка становится живой, если она имеет от c до d включительно живых соседей
• Иначе ячейка становится или остаётся мёртвой

import numpy as np

class GameOfLife:
    '''Represents a generalized Conway's Game of Life.
    The game is an n-dimensional array (n >= 2) of boolean values. Each cell is either alive (True) or dead (False).
    On each iteration the cells are updated as follows:
        - An alive cell stays alive if it has between `a` and `b` live neighbours
        - A dead cell becomes alive if it has between `c` and `d` live neighbours
        - Otherwise the cell dies
    The board has wraparound edges, so the neighbours of edge cell are located on the opposite edge.

    Fields:
        board: the current state of the game, n-dimensional array of type bool
        a: minimal number of live neighbours for a cell to stay alive
        b: maximal number of live neighbours for a cell to stay alive
        c: minimal number of live neighbours for a cell to become alive
        d: maximal number of live neighbours for a cell to become alive
    '''

    def __init__(self, board: np.ndarray,
                 a: int = 2, b: int = 3,
                 c: int = 3, d: int = 3):
        '''Initializes `board` and game rule fields. `board` must be stored as a copy'''
        pass

    def next_iteration(self) -> None:
        '''Computes the next iteration of the game. Invalidates `self.board`'''
        pass

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

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

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

Задача 7L. Марковские коты ≡

Условие

Вам выпала уникальная возможность исследовать популяцию марковских котов. Известно, что существует N пород, а также начальный размер популяции — количество особей каждой породы x_i ∈ N₀, i = 1, N. Марковские коты также обладают уникальной особенностью — каждый день ровно в полночь каждая отдельная особь породы i с вероятностью p_i,j независимо от остальных трансформируется в k_i,j ∈ N₀ особей породы j, при этом N∑j = 1p_i,j = 1. В качестве отчёта Вам требуется предоставить размер популяции в полночь через T дней наблюдений. Естественно, Вам не хочется бегать за котами и считать их вручную, поэтому Вы решаете ограничиться математическим ожиданием, ведь никто точно не захочет проверить предоставленный Вами отчёт, даже если количество особей будет нецелым.

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

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

Первая строка входного файла содержит два целых числа N, T — количество пород и дней наблюдений соответственно. В следующих N строках содержится по N вещественных чисел — вероятности p_i,j. В следующих N строках содержится по N целых чисел — количества k_i,j. Последняя строка файла содержит N целых чисел x_i — начальный размер популяции.

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

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

Ограничения

2 ⩽ N ⩽ 500

1 ⩽ T ⩽ 15

0 ⩽ k_i,j ⩽ 5

0 ⩽ x_i ⩽ 10

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

2 10
0 1
1 0
0 1
2 0
1 1

32 32

2 5
  1   0
0.5 0.5
1 0
2 4
1 1

32 32

2 5
0.9 0.1
0.5 0.5
1 0
5 1
0 2

6.9905 0.0625

Problem 8A. Assignment ≡

Statement

Let the assignment expression be described by the following grammar

Comma = ",", { " " };

Digit = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
Number = "0" | ( Digit, { Digit | "0" } );

Letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
       | "c" | "d" | "e" | "f" | "g" | "h" | "i"
       | "j" | "k" | "l" | "m" | "n" | "o" | "p"
       | "q" | "r" | "s" | "t" | "u" | "v" | "w"
       | "x" | "y" | "z" ;

Variable = Letter, { Letter | Digit | "0" };

Value = Variable | Number | EnclosedValueList | EmptyList;
ValueList = Value, { Comma, Value }, [ Comma ];
EnclosedValueList = "(", ValueList , ")";
EmptyList = "(", { " " }, ")";

Destination = Variable | EnclosedDestinationList;
DestinationList = Destination, { Comma, Destination }, ( [ Comma, "*", Variable ] | [ Comma ] );
EnclosedDestinationList = "(", DestinationList, ")";

Assignment = ( DestinationList | EnclosedDestinationList ), " = ", ( ValueList | EnclosedValueList );

Both sides are treated as potentially nested lists. A variable on the left side is assigned a value placed at the same position on the right side. A value therefore may be a Number, a Variable or a list. A list must be enclosed in parenthesis and have at least one comma, i.e. (a,) is a list and (a) is equivalent to simply a. Additionally, parenthesis at the top level may be omitted. The assignment is performed from top to bottom, left to right, meaning that a Variable may be used as Value on the right side if it has already been assigned a Value. In a special case that a Variable is preceded by an asterisk it is assigned a potentially empty list of the rest of the Values at that level. The assignment fails if a Variable or a Value doesn't have a corresponding item on the other side or if a Variable is used as a Value before it has been assigned a Value.

Your program must decompose such assignment into a list of simple assignments: one Variable is assigned one Number or a list of Numbers.

Input format

Input consists of a single line — the assignment expression to be executed.

Output format

If the assignment cannot be performed output a single number -1. Otherwise, output must contain a simple assignment expression for each variable in lexicographical order one per line. The simple assignment is defined by the following grammar

SimpleAssignment = Variable, " = ", NumberOrList;
NumberOrList= Number | ( "(", NumberOrList, { Comma, NumberOrList }, [ Comma ] ")" ) | EmptyList;

Constraints

The assignment expression is guaranteed to be grammatically correct.

Length of the input is no more than 10⁴ symbols.

Sample tests

a, b, c = 42, 23, (23, 42)

a = 42
b = 23
c = (23, 42)

a, *b = 1, 2, 3, 4, 5

a = 1
b = (2, 3, 4, 5)

a, (b, c) = 42, (23, a)

a = 42
b = 23
c = 42

a, b = 42, 23, 10

-1