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

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

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 25

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

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

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

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 24

0 ≤ ai ≤ 23; 0 ≤ bi ≤ 22

a1 < a2 < … < aN; b1 ≤ b2 ≤ … ≤ bN

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
3 3
6 5
10 9
4 5 6
2
1
21 21
22 23
3
2
3 2
14 13
1 2 3

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

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

Условие

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

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

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

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

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

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

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

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

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

0.027s 0.003s 11