Задача A. Расписание электричек ≡

Условие

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

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

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

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

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

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

Требуется вывести в выходной файл единственное целое число — минимальное количество сотрудников.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 25

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

4 1

3

5 2

2

Задача B. Марфа Геннадьевна и часы - 2 ≡

Условие

Однажды Марфа Геннадьевна проснулась взволнованной. "Надо не забыть перевести часы на час назад", — подумала она. У Марфы Геннадьевны было двое часов. Одни механические, другие электронные. Электронные часы переводят время на час назад автоматически, механические — нет.

В определённые часы Марфа Геннадьевна смотрела на те и другие часы и записывала, сколько часов они показывали. Теперь Марфа Геннадьевна заинтересовалась, во сколько электронные часы перевели время.

Марфа Геннадьевна обратилась к вам за помощью. Напишите программу, принимающую на вход записи Марфы Геннадьевны и вычисляющую все возможные моменты времени, когда электронные часы могли перевести время на час назад. Известно, что электронные часы перевели время ровно один раз на час назад в 1, 2, ..., 22 или 23 часа.

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

Входной файл содержит целое число N — количество записей Марфы Геннадьевны. Далее следуют N пар чисел a_i b_i, где a_i — количество часов, которое показывают механические часы, b_i — количество часов, которое показывают электронные часы.

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

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

Ограничения

1 ≤ N ≤ 24

0 ≤ a_i ≤ 23; 0 ≤ b_i ≤ 22

a₁ < a₂ < … < a_N; b₁ ≤ b₂ ≤ … ≤ b_N

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

3
3 3
6 5
10 9

4 5 6

1
21 21

22 23

2
3 2
14 13

1 2 3

Задача C. Марфа Геннадьевна и напёрстки ≡

Условие

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

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

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

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

Первая и вторая строки входного файла содержат по 3 целых числа от 1 до 3. Число 1 означает маленький шарик, 2 — средний, 3 — большой. В каждой строке все числа различны.

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

Требуется вывести в выходной файл единственное целое число — ответ в задаче.

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

1 2 3
3 2 1

3

2 1 3
2 1 3

0

3 1 2
3 2 1

1

Задача D. Круговая волна ≡

Условие

На перемене школьник Вася решил немного отдохнуть и стал чертить в черновике круговую волну (не путать с синусоидой). Он начертил прямоугольную систему координат, затем взял несколько одинаковых монеток радиусом 1 см и положил их друг за другом так, чтобы их центры располагались на оси абсцисс, а первая монетка касалась оси ординат. Потом Вася стал обводить монетки, как показано на рисунке — сначала сверху, потом снизу, потом опять сверху, снизу и т.д. Но тут прозвенел звонок на урок. К счастью, Вася успел засечь время: он рисовал волну t секунд, при этом Вася чертил со скоростью 1 см/с, то есть за 1 секунду он рисовал дугу длиной 1 см.

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

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

Входной файл содержит вещественное число t.

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

Требуется вывести в выходной файл два вещественных числа x y — координаты конечной точки волны в см с точностью до 3-х знаков после запятой.

Ограничения

0.1 ≤ t ≤ 300

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

3.16159

2.00019994 -0.01999601

10

6.16092847 -0.54402111

4.71238898038

3.0 -1.0

Задача E. Марфа Геннадьевна в поезде ≡

Условие

Однажды Марфа Геннадьевна ехала вместе с Аполлинарием Матвеевичем на поезде. К ним подошёл проводник и предложил кипяток. Пассажиры переглянулись: никто не хотел пить слишком горячий чай. Проводник сказал, что у него есть холодная вода в отдельной ёмкости, но холодной и горячей воды не очень много.

Теперь перед Марфой Геннадьевной и Аполлинарием Матвеевичем стоит непростая задача. У проводника имеется 2 сосуда с холодной и горячей водой. В первом сосуде есть A л холодной воды при температуре T₁ градусов. Во втором сосуде есть B л горячей воды при температуре T₂ градусов. Требуется перелить определённое количество воды из первого и второго сосуда в третий сосуд так, чтобы в третьем сосуде вода была при температуре от m до M градусов и её было как можно больше.

Если из 1-го сосуда налить x л, а из 2-го — y л, то температура воды в 3-м сосуде будет усреднена и равна T₁ x + T₂ yx + y.

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

Входной файл содержит целые числа A B T₁ T₂ m M.

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

Требуется вывести в выходной файл вещественное число — максимальное количество воды в литрах, которое можно получить в 3-м сосуде при температуре от m до M градусов, с точностью до 4-х знаков после запятой.

Ограничения

1 ≤ A, B ≤ 20

0 ≤ T₁ ≤ m ≤ M ≤ T₂ ≤ 100

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

5 10 25 100 50 60

9.3750

Задача F. Реформа галактических вооруженных сил ≡

Условие

Армия галактического альянса состоит из 2 N дивизионов боевых дроидов. Верховное командование приняло решение сократить количество дивизионов вдвое, объединив их попарно. Объединение двух дивизионов происходит следующим образом: каждый из дивизион разбивается на одинаковое количество K_i отрядов дроидов, после чего отряды сливаются и формируют K_i увеличенных отрядов, составляющих новый объединенный дивизион.

Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.

Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.

Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.

Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10; 1 ≤ D_i ≤ 10⁹

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

2
1 2 3 4

3

2
4 9 3 6

5

2
30 18 5 12

11

Задача G. Универсальный галактический гороскоп ≡

Условие

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

Год состоит из M месяцев, каждый месяц состоит из D дней. Количество лет, месяцев и дней в записи даты означает количество полных прошедших, соответственно, лет, месяцев и дней. Событие имело место в нулевом дне нулевого месяца нулевого года (0.0.0), и, например, спустя два с половиной дня дата будет 2.0.0. Таким образом, если дата рождения галактического жителя 5.0.0, то есть через пять полных дней с момента События, то считается, что он родился уже в течение шестого дня.

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

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

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

Входной файл содержит целые положительные числа N, M, D, K, P, после которых идут N дат дней рождения галактических жителей в формате DAYS.MONTHS.YEARS.

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

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

Ограничения

1 ≤ N, M, D, K, P ≤ 1000

0 ≤ DAYS < D; 0 ≤ MONTHS < M; 0 ≤ YEARS ≤ 999

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

5 2 2 1 4
0.0.0
1.0.0
0.1.0
1.1.0
0.0.1

1 2 3 4 1

3 2 5 1 3
4.0.133
1.1.77
3.1.44

2 0 3

Задача H. Зельеварение ≡

Условие

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

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

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T₀ + K, где T₀ — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

Помогите Васе определить, на какие колбы направить свои заклинания.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 10³

−10⁷ ≤ K ≤ 10⁷

−10⁴ ≤ a_i ≤ 10⁴

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

1 0
1

1

5 1
1 2 3 -1 -1

4