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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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


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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

01. Лекция: Арифметика, ввод/вывод

Материалы

Синтаксис Python.

Инструкция по организации ввода-вывода.


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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1
10
1
15
5
2
1000
9
9
81

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 < N, M < 10000

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

Стандартный вход Стандартный выход
1
10
2
5
2
6
4
1.5

Задача 01C. FizzBuzz

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:7  

Условие

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

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

Стандартный вход Стандартный выход
1
23
2
25
Buzz
3
30
FizzBuzz

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

Автор:Владивостокская городская олимпиада школьников по информатике 2002/2003   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:10  

Условие

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

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

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

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

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

Ограничения

1 ≤ A, B ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 14
16
2
9 1
0

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

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
18 25
7 37
2 2

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

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ D, T ≤ 1000

10 − 3 ≤ v1 < v2 ≤ 102

10 − 3 ≤ w1 < w2 ≤ 102

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10.0 5.0
1.0 3.0
0.5 1.0
9.0
2
15.0 3.0
1.0 2.5
4.25 6.1
2.291
3
25.0 5.0
1.0 3.0
4.0 5.0
0.0

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

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ A, B, t ≤ 5 * 108

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5 18
N
2
1 8 18
S

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
Джеймс
Бонд
Меня зовут Бонд
Джеймс Бонд

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
sporyshev
ms
students
sporyshev.ms@students.dvfu.ru

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

Стандартный вход Стандартный выход
1
Просто!
:)
2
Как-то не очень
:(

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
Что тут происходит?!?!
вопросительно-восклицательное
2
Скажите мне, пожалуйста!
сложное восклицательное
3
Ничего
повествовательное

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

Стандартный вход Стандартный выход
1
4
cha
g'thazag
mog
Bin
Bin
mog
g'thazag
cha

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

Стандартный вход Стандартный выход
1
5
5
4!
3!!
2!!!
1!!!!
Start!!!!!

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

Стандартный вход Стандартный выход
1
7
подосиновик
камень
boletus edulis
обабок
обабок
обабок
Boletus edulis
2
2
5
шампиньон
лисичка
маслёнок
сыроежка
опёнок
0

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

Стандартный вход Стандартный выход
1
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

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:102  

Условие

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

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

Требуется написать программу, переводящую имя переменной из одного стандарта в другой.

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
x
X
2
ATest
a_test

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

Стандартный вход Стандартный выход
1
4 1
1 2 3 4
2 3 4 1
2
5 2
7 1 3 6 10
3 6 10 7 1

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

Стандартный вход Стандартный выход
1
3
1 2 3
4 5 6
5 7 9

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
100 100 23 197 100 23 197
3

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

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1
2
1
0
2 1 0 0 0 0 0 0 0 1
2
7
9
1
3
2
3
2
7
1 2 2 0 0 0 1 0 1 0

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

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

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

Помогите ему написать программу, которая для заданного АБ теста и порога генерирует 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 знака после запятой.

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

Стандартный вход Стандартный выход
1
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. Поворот матрицы

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

2⩽ n,m⩽ 2000

 − 100⩽ k⩽ 100

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

Стандартный вход Стандартный выход
1
3 3 3
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
2
3 3 -3
1 2 3
4 5 6
7 8 9
7 4 1
8 5 2
9 6 3
3
2 3 1
1 2 3
4 5 6
4 1
5 2
6 3

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 < N < 100

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

Стандартный вход Стандартный выход
1
3
1 2 3
4 5 6
7 8 9
1 4 7
2 5 8
3 6 9

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

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:d.in   Ограничение памяти:64 Мб
Выходной файл:d.out  
Максимальный балл:100  

Условие

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

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

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

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

Во входном файле записана строка.

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

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

Ограничения

Входная строка имеет длину не более 200 символов.

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

Входной файл (d.in) Выходной файл (d.out)
1
Hello , world!
2
2
www.olympiads.ru
3
3
Gyro-compass - this is a ...
4

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1
As God is my witness , I will never be hungry again .
11

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
6
10
10
100
2000
10
10
2120
2
4
500
500
500
500
1000

Задача 02Z. Turing Machine

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

Пусть задана машина Тьюринга с алфавитом 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.

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

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ M ≤ 20, 1 ≤ K ≤ 105. Максимальная длина ленты, необходимая для выполнения программы, не превышает 105.

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

Стандартный вход Стандартный выход
1
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
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
3
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. Индекс предыдущего вхождения

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

5⩽ n⩽ 200000

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

Стандартный вход Стандартный выход
1
First string
Second string
Second string
First string
First string
-1
-1
1
0
3

Задача 03B. groupby group

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan
M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

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

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
aA
Aa
aa
AA1
aA
Aa1
aa2
AA11

Задача 03D. Add

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:6  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1 x, y = 2, 3 print(Add(x, y))
5
2 print(Add(10, 11))
21

Задача 03E. PrintMatrix

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1 mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] PrintMatrix(mat)
1 2 3
4 5 6
7 8 9
2 PrintMatrix([[1, 2, 3], [4, 5, 6]])
1 2 3
4 5 6

Задача 03F. Map

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Стандартный вход Стандартный выход
1 ary = [-1, 2, -3, 4] print(Map(abs, ary))
[1, 2, 3, 4]
2 print(sum(Map(lambda x: x**2, [2, 3])))
13

Задача 03G. Join

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

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

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

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

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

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

Стандартный вход Стандартный выход
1 ary = ['aa', 'bb', 'cc'] print(Join(ary, '!'))
aa!bb!cc
2 ary = ['aa', 'bb', 'cc'] print(Join(ary))
aa bb cc

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1 def sum(a: int, b: int): 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
2 @projection_decorator def calc(x: int): print(x * x) calc(1, 2, 3)
2704

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:5  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3 4
7
2
10 -20 3
33

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3.0 4.0
5.0
2
10.5 20.1 3.1
22.8882065701968

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
-1 2 -3 4 0 -5 6
36 16 4

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
1 2 30 40 50 6 7
1 2 50 40 30 6 7

Задача 04F. Reshape

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
6
1 2 3 4 5 6
3 2
1 2
3 4
5 6
2
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 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
1 2 0 3 4 0 5 10
1 0 3 0 5 10
2
11 0 0 12
0 12

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3 -1 2 4 9 6
3 -1 2 4 -1 6
2
5 4 1 5 2
1 4 1 1 2

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
5 3
1 2 3 4 5
1 3 5

2 2 4 4 6

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 ⩽ N,M ⩽ 100

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

Стандартный вход Стандартный выход
1
....
.##.
.##.
....
....
.##.
.##.
....
2
.....
..#..
..#..
..#..
.....
.....
.....
.###.
.....
.....

Задача 05A. dir

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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


Задача 05B. dir*

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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


Задача 05C. Time

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

   

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

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

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

Стандартный вход Стандартный выход
1 time = Time(25, 11, 12, 1) print(str(time)) time.Add(Time(0, 0, 0, 1010)) print(str(time))
01:11:12.1
01:11:13.11

Задача 05D. ShiftableList

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1 lst = ShiftableList(['a', 'b', 'c']) lst2 = lst << 1 print(', '.join(lst2))
b, c, a
2 lst = ShiftableList(['a', 'b', 'c']) lst2 = lst >> -2 print(''.join(lst), ''.join(lst2))
abc cab

Задача 05E. CardStack

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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


class Student:

    def __init__(self):
        pass

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

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


Задача 05G. Property

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Части в документации должны быть разделены пустой строкой (см. пример 2).

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

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

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

Стандартный вход Стандартный выход
1 class Person: @Property def name(self) -> str | None: return self._name @name.setter def name(self, name: str): self._name = name p1 = Person() p2 = Person() p2.name = 'Petya' print(p1.name) print(p2.name)
None
Petya
2 class Person: def get_name(self) -> str: '''Getter: Returns the name''' return self._name def set_name(self, name: str): '''Setter: Sets the name, must be of type str''' self._name = name def delete_name(self): '''Deleter: Sets the name to None''' self._name = None name = Property(get_name, set_name, delete_name, 'Name of a person, str', 'Vasya') p = Person() print(Person.name.__doc__) print(p.name) p.name = 'Petya' print(p.name) del p.name print(p.name)
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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1 @lru_cache def fibonacci(n): match n: case 0: return 0 case 1: return 1 case _: return fibonacci(n - 2) + fibonacci(n - 1) print(fibonacci(256)) print(fibonacci.cache_info())
141693817714056513234709965875411919657707794958199867
CacheInto(hits=254, misses=257, maxsize=128, currsize=128)
2 @lru_cache(maxsize=2) def add(a, b): return a + b print(add(1, 2), add(3, 4), add(1, 2), add(5, 6)) print(add.cache_state())
3 7 3 11
{((5, 6), ()): 11, ((1, 2), ()): 3}

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

Стандартный вход Стандартный выход
1 @check_types def add(a: int, b: int) -> int: return a + b try: print(add(1, 2)) print(add('1', '2')) except TypeCheckError as e: print(f'Failed {e.name}')
3
Failed a
2 @check_types def sqr(a: float) -> int: return a * a try: sqr(2.) except TypeCheckError as e: print(f'Failed {e.name}')
Failed return
3 @check_types class Number: def __init__(self: Number, value: int): self.value = value def __add__(self: Number, other: Number) -> Number: return Number(self.value + other.value) try: print((Number(1) + Number(2)).value) print((Number(1) + 2).value) except TypeCheckError as e: print(f'Failed {e.name}')
3
Failed other
4 @check_types def pow(x: int | list[int], p: int) -> int | list[int]: if isinstance(x, list): return [i ** p for i in x] return x ** p try: print(pow(2, 2)) print(*pow([1, 2, 3], 3)) print(*pow((1, 2, 3), 3)) except TypeCheckError as e: print(f'Failed {e.name}')
4
1 8 27
Failed x

Задача 05J. dataclass_lite

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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.

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

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

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

Стандартный вход Стандартный выход
1 @dataclass_lite class Person: name: str age: int help(Person.__init__) person1 = Person('Vasya', 23) person2 = Person('Petya', 42) print(person1.name, person1.age) print(person2.name, person2.age)
Help on function __init__ in module __main__:

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

Vasya 23
Petya 42
2 @dataclass_lite class Person: name: str age: int children: list[Person] = field(default_factory=lambda: [], kw_only=True) help(Person.__init__) person1 = Person('Vasya', 23) person2 = Person('Petya', 42, children=[person1]) print(person1.name, person1.age, person1.children) print(person2.name, person2.age, person2.children[0].name)
Help on function __init__ in module __main__:

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

Vasya 23 []
Petya 42 Vasya

Задача 06A. stack_chain

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1 print(*stack_chain(range(3), range(2, -1, -1), (i * i for i in range(3))))
0 1 4 2 1 0 0 1 2
2 a = stack_chain(range(3)) for i in a: a += [i - 1] * i print(i, end=' ')
0 1 0 2 1 0 1 0

Задача 06B. Take

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

from collections.abc import Generator, Iterable

def take(iterable: Iterable, *, skip: int = 0, step: int = 1, count: int | None = None) -> Generator:
    '''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

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

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

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

Стандартный вход Стандартный выход
1 print(*take(range(100), skip=5, step=5, count=5))
5 10 15 20 25

Задача 06C. Pipeline

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке 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 {ai}n − 1i = 0, где ai текущий элемент datai. При n = 1 возвращается единственный элемент a0. Если func is not None, элементами Pipeline являются результаты применения функции: func(a_0, a_1, ..., a_{n-1}).

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1 a = Pipeline([1, 2, 3, 4, 5], name='data1') b = Pipeline([5, 4, 3, 2, 1], a) print(a) print(b) print(*zip(a, b))
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))
2 def square(x: int): return x * x a = Pipeline([1, 2, 3], func=square) a = Pipeline(a, [3, 2, 1], name='zip') a |= (lambda x: x[0] + x[1], 'sum') print(a) print(*a)
Pipeline(Pipeline(Pipeline([1, 2, 3], func=square), [3, 2, 1], name='zip'), func=<lambda>, name='sum')
4 6 10
3 a = Pipeline([1, 2, 3], [3, 2, 1], name='zip') @ (lambda x, y: x + y, 'sum') print(a) print(*a)
Pipeline(Pipeline([1, 2, 3], [3, 2, 1], name='zip'), func=<lambda>, name='sum')
4 4 4
4 a = Pipeline([1, 2, 3], name='data1') a |= (lambda x: x * x, 'square') b = Pipeline([3, 2, 1], name='data2') b |= (lambda x: 2 * x, 'times_two') c = Pipeline(a, b, name='zip') @ (lambda x, y: x + y, 'sum') print(*c) print(' -> '.join(i.name for i in c.walk()))
7 8 11
data1 -> square -> data2 -> times_two -> zip -> sum
5 a = Pipeline(name='data') + [1, 2, 3] + [4, 5, 6] print(a) print(*a)
Pipeline([1, 2, 3], [4, 5, 6], name='data')
(1, 4) (2, 5) (3, 6)

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 < n < 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
3

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 < n < 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
1.957

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 300, 1 ≤ mi ≤ 5, 0 < xi < 3

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2 4
3 4
2.5 2.4 2.449

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 < n < 105

3 ⩽ m ⩽ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 3
5 2 5 5 8 5 5 2 5
4 4 6 6 6 4 4

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

Ограничения

1 < n < 105

3 ⩽ m ⩽ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 3
1 2 1
5 1 5 5 9 5 5 1 5
3 4 6 7 6 4 3

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

2 < N < 50, 1 < M < 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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. Центральный момент

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105, 1 ≤ k ≤ 5

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 1
1 4 5 4 4 5 1 5 2 3
0
2
10 2
7 8 -2 -8 8 -3 9 -6 1 -2
36.16

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Пусть имеется выборка {xi}ni = 1. Для построения гистограммы необходимо разбить выборку на интервалы равной длины [b1, b2), [b2, b3) … [bk, bk + 1], b1 = mini xibk + 1 = maxi xi.

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 1 2
1 2
2
6
8 9 2 1 2 0
4 0 2
3
6
8 9 1 2 0 10
3 0 3

Задача 07I. Nearest point

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

Стандартный вход Стандартный выход
1
print(*nearest(np.array([[0, 0], [3, 3]]), np.array([1, 1])))
0 0

Задача 07J. Calculate distance

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Существует набор линий в двумерном пространстве. В этом же пространстве присутствует точка 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

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

Стандартный вход Стандартный выход
1
print(*calculate(
        np.array([[1,  2.5]]),
        np.array([[3,  2.5]]),
        np.array([[2, 1]])))
1.5
2
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

Задача 07K. Марковские коты

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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

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

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

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

Ограничения

2⩽ N⩽ 500

1⩽ T⩽ 15

0⩽ ki,j⩽ 5

0⩽ xi⩽ 10

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

Стандартный вход Стандартный выход
1
2 10
0 1
1 0
0 1
2 0
1 1
32 32
2
2 5
  1   0
0.5 0.5
1 0
2 4
1 1
32 32
3
2 5
0.9 0.1
0.5 0.5
1 0
5 1
0 2
6.9905 0.0625

Задача 07L. Game of Life with Numpy

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

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 a 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.

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

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


Problem 08A. Assignment

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:512 Mb
Maximum points:1  

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 104 symbols.

Sample tests

No. Standard input Standard output
1
a, b, c = 42, 23, (23, 42)
a = 42
b = 23
c = (23, 42)
2
a, *b = 1, 2, 3, 4, 5
a = 1
b = (2, 3, 4, 5)
3
a, (b, c) = 42, (23, a)
a = 42
b = 23
c = 42
4
a, b = 42, 23, 10
-1

Задача 09D. Дивизион D

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:40  

Условие

Количество задач, решённых в дивизионе D


Задача 09E. Дивизион E

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:60  

Условие

Количество задач, решённых в дивизионе E.

Задача 09F. Дивизион F

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:63  

Условие

Количество задач, решённых в дивизионе F.

Задача 10A. 1/8 ICPC

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Количество задач, решенных на 1/8 ICPC


Задача 10B. 1/4 ICPC

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Количество задач, решённых на 1/4 ICPC


Задача 10C. Финал RuCode

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Количество задач, решённых на финале RuCode


3.182s 0.019s 173