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

Условие

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

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

Условие

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

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

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

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

Условие

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

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

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

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

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

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

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

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

Джеймс
Бонд

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

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

Условие

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

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

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

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

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

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

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

sporyshev
ms
students

sporyshev.ms@students.dvfu.ru

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

Условие

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

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

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

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

10
1
15

5

1000
9
9

81

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

Условие

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

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

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

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

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

Ограничения

1 < N, M < 10000

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

10
2

5

6
4

1.5

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

Условие

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

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

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

Просто!

:)

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

:(

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

Условие

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

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

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

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

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

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

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

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

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

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

Ничего

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

Задача I. FizzBuzz ≡

Условие

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

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

23

25

Buzz

30

FizzBuzz

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

Условие

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

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

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

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

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

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

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

Иванов

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ A, B ≤ 10⁶

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

3 14

16

9 1

0

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

Условие

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

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

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

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

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

18 25
7 37

2 2

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

Условие

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

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

Условие

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

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

Условие

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

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

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

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

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

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

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

Иванов

Задача C. Грибы ≡

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

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

2

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

0

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

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

5

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

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

Условие

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

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

4
cha
g'thazag
mog
Bin

Bin
mog
g'thazag
cha

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

Условие

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

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

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

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

Условие

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

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

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

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

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

Ограничения

1 < N < 100

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

3
1 2 3
4 5 6

5 7 9

Задача J. Форум ≡

Условие

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

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

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

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

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

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

100 100 23 197 100 23 197

3

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

Условие

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

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

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

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

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

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

11

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

Условие

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

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

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

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

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

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

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

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

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

Условие

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

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

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

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

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

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

Ограничения

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

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4

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

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

Условие

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

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

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

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

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

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

6
10
10
100
2000
10
10

2120

4
500
500
500
500

1000

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

Условие

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

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

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

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

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

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

3 -1 2 4 9 6

3 -1 2 4 -1 6

5 4 1 5 2

1 4 1 1 2

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

Условие

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

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

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

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

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

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

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

True

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

False

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

Условие

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

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

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

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

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

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

5 3
1 2 3 4 5
1 3 5

2 2 4 4 6

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

Условие

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

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

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

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

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

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

FEFU was established in 1899 as the Eastern Institute
5

1899

FEFU was established
5

established

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

Условие

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

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

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

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

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

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

3 4

7

10 -20 3

33

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

Условие

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

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

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

Задача H. Норма L2 ≡

Условие

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

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

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

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

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

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

3.0 4.0

5.0

10.5 20.1 3.1

22.8882065701968

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

Условие

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

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

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

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

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

Задача J. Add ≡

Условие

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

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

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

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

5

21

Задача K. Key sort ≡

Условие

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

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

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

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

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

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

azx zab ddd

zab ddd azx

Задача L. GCD ≡

Условие

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

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

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

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

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

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

2 6 3

2 1 3

Задача M. PrintMatrix ≡

Условие

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

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

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

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

1 2 3
4 5 6
7 8 9

1 2 3
4 5 6

Задача N. Map ≡

Условие

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

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

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

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

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

[1, 2, 3, 4]

13

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

Условие

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

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

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

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

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

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

-1 2 -3 4 0 -5 6

36 16 4

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

Условие

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

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

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

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

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

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

1 2 30 40 50 6 7

1 2 50 40 30 6 7

Задача Q. Join ≡

Условие

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

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

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

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

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

aa!bb!cc

aa bb cc

Задача A. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

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

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

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

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача B. Range Variation Query ≡

Условие

В начальный момент времени последовательность a_n задана следующей формулой: a_n = n² mod 12345 + n³ mod 23456.

Требуется много раз отвечать на запросы следующего вида:

• Найти разность между максимальным и минимальным значениями среди элементов a_i, a_i + 1, …, a_j.
• Присвоить элементу a_i значение j.

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

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами x_i, y_i.

Если x_i > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов a_xi, …, a_yi. При этом 1 ≤ x_i ≤ y_i ≤ 100 000.

Если x_i < 0, то требуется присвоить элементу a_|xi| значение y_i.

В этом случае  − 100 000 ≤ x_i ≤  − 1 и |y_i| ≤ 100 000.

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

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

Ограничения

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

7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

34
68
250
234
1

Задача C. Сумма+присвоение на отрезке ≡

Условие

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

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

• A l r x

   — присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 10⁹)

• Q l r

   — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)

Изначально массив заполнен нулями.

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

На каждый запрос вида

Q l r

Ограничения

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

5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

3
2
3
4
2
7

Задача D. RMQ ≡

Условие

• «max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
• «add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

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

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

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

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

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

5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3

3
7

Задача E. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача A. Заколдованный аквариум ≡

Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.

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

 — Да какая же это проверка, это же чистой воды саботаж! — возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.

 — Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

 — Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

 — Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.

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

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны a_i метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

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

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

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

Ограничения

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

1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0

2.0

Задача B. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача C. Вырубка леса ≡

Условие

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

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

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

Система оценивания и описание подзадач

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

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

Подзадача 2 (10 баллов)

1 ≤ X ≤ 10¹⁸; X < K; X < M.

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

Подзадача 3 (10 баллов)

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

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

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

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

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

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

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

2 4 3 3 25

7

Задача D. Поляна Дров ≡

Условие

Маленький мальчик Фермá живет в деревне. Наступают холодные времена, поэтому бабушка попросила мальчика сходить в лес, чтобы собрать дров. В лесу около деревни, в которой живет Ферма, находится волшебная Поляна Дров, на которой всегда лежат дрова, и никогда не кончаются. Естественно, Ферма должен пойти именно туда.

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

• Деревня находится в точке с координатами (0, 1).
• Поляна находится в точке с координатами (1, 0).
• Граница между лесом и полем — горизонтальная прямая y = a, где a — некоторое число (0 ⩽ a ⩽ 1).
• Скорость передвижения по полю составляет V_p, скорость передвижения по лесу — V_f. Вдоль границы можно двигаться как по лесу, так и по полю.

Найдите точку, в которой мальчик Ферма должен войти в лес, чтобы дойти до Поляны Дров как можно быстрее.

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

В первой строке входного файла содержатся два положительных целых числа — V_p и V_f (1 ⩽ V_p, V_f ⩽ 10⁵). Во второй строке содержится единственное вещественное число — координата по оси Oy границы между лесом и полем a (0 ⩽ a ⩽ 1).

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

В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой мальчик Ферма должен войти в лес.

Ограничения

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

5 3
0.4

0.783310604

5 5
0.5

0.500000000

Problem A. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Задача B. Сравнения подстрок ≡

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a… b] и [c… d].

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

Сперва строка S из строчных латинских букв. Далее число M — количество запросов.

В следующих M строках по четыре целых числа — запросы a, b, c, d.

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

Выведите M строк, по одному ответу для каждого запроса. Ответ должен быть Yes, если подстроки совпадают, и No в противном случае.

Ограничения

0 ≤ M ≤ 10⁵, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|, 1 ≤ |S| ≤ 10⁵.

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

trololo
3
1 7 1 7
3 5 5 7
1 1 1 5

Yes
Yes
No

Задача C. Нормальная палиндромика ≡

Условие

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

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

Ограничения

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

abcc

ba

abcd

cba

Задача D. Синхронизация ≡

Условие

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

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

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

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

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

Входной файл содержит целое число N. Далее следует N целых чисел a₁, a₂, …, a_N — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b₁, b₂, …, b_M — времена событий, зафиксированных Колей.

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

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

Ограничения

2 ≤ M ≤ N ≤ 10⁵;

0 ≤ a₁ ≤ a₂ ≤ …  ≤ a_N ≤ 10⁹;

0 = b₁ ≤ b₂ ≤ …  ≤ b_M ≤ 10⁹;

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

5
10 15 17 19 20
2
0 2 

2

Problem A. Topological sorting ≡

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

Sample tests

4 3
1 2
1 3
3 4

1 3 2 4

Problem B. Bipartite graph ≡

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Output file format

Constraints

Sample tests

3 2
1 2  1 3

BIPARTITE

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

NO

Задача C. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

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

3 1
2 3

2

Задача D. Почтовая реформа ≡

Условие

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

Недавно образованное почтовое агентство "Экс-Федя" предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h, курьеру агентства требуется иметь с собой не менее h метров веревки.

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

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

• Уведомление от волшебника из города i о том, что высота его башни стала равна h, имеет вид ! i h, 1 ≤ i ≤ n, 1 ≤ h ≤ 10⁵.
• Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j, 1 ≤ i, j ≤ n.

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

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

3
1 2 3
1 3
2 3
5
? 1 2
! 1 5
? 2 3
! 3 2
? 1 2

3
3
5

1
100
5
! 1 1
? 1 1
! 1 1000
? 1 1
! 1 1

1
1000

Alice and numbers ≡

Условие

Юная программистка Алиса не любит целое число K.

Алиса хочет узнать количество целых чисел в диапазоне от 1 до N включительно, не делящихся на K.

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

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

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

Выведите единственное целое число — количество целых чисел, не делящихся на K.

Ограничения

2 ≤ N ≤ 10⁹

1 ≤ K ≤ 100

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

5 2

3

4 2

2

Задача A. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

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

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

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

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

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

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Задача B. Быки и коровы 2 ≡

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

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

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

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

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

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

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

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

15 5
XX...XXYYYXX.YY

6 10

Задача C. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

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

В первой строке файла содержится единственное число N.

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

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

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

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача D. Максимальный перепад ≡

Условие

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

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

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

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

Ограничения

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

3
1 1 1
1 2 1
1 2 3

2

Задача E. Болезнь ≡

Условие

В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются n различных болезнетворных бактерий.

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

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

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

В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.

Последнее число в строке равно 1, если анализ дал положительный результат, и 0 — в противном случае.

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

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

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

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

3 3
1 0 0 0
1 1 1 1
0 1 0 0

2 1 2
1 3
0

2 2
1 1 0
1 0 1

Incorrect

2 1
1 1 1

0
0
2 1 2