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

Problem F. C---- ≡

Statement

C---- language was designed specifically for students who failed standard course of Compiler Programming. C---- program is a list of statements. Each statement is one of:

• { — start of the block;
• } — end of the block;
• int var — variable declaration;
• var₁=var₂ — assign var₂ to var₁;
• var=constant — assign constant to var;
• print var — print value of var.

Each variable is declared at most once in the block, but variables with same name may be declared in different blocks. It that case, name refers to the variable declared in the nearest enclosing block. Note that variables may be defined in the middle of the block.

The program is guaranteed to be correct — all blocks are properly balanced, variables are referenced only after declaration, variables are always initialized before reading, etc. Program contains at least one print statement.

Your program must execute a given C---- program.

Input file format

First line of input file contains integer N. Following N lines contain one C---- statement each.

Output file format

Output file must contain a sequence of integers — one integer for each print statement.

Constraints

3 ≤ N ≤ 1000

Sample tests

10
int a
int x
{
a=50
int a
a=60
x=a
print x
}
print a

60
50

Problem G. Error detection ≡

Statement

FEFU computer scientists use a duplication method to detect errors in network data transfer. Each bit of data is duplicated. The duplicate follows the original bit. Each byte therefore is transferred as a message of two bytes. The first byte of the message encodes high bits of the original byte, the second byte encodes low bits.

For example, a byte 67 is encoded as follows:

1. 67₁₀ = 01000011₂;
2. the sequence 01000011 is encoded as 0011000000001111;
3. the sequence 0011000000001111 is split into 00110000 and 00001111;
4. 00110000₂ = 48₁₀, 00001111₂ = 15₁₀, so the result is 4815

Scientists received two bytes. Now they need to find out what the original byte was.

Input file format

Input file contains two integers designating two received bytes.

Output file format

Output file must contain a single integer — the original byte, or  − 1 if there was an error during transfer.

Constraints

Both input integers are in the range from 0 to 255.

Sample tests

48 15

67

48 7

-1

Problem H. Inclination ≡

Statement

A professor of Fences, Entrances and Frames University has developed a new Fence Inclination theory. According to that theory, a fence is modeled as a sequence of planks. Every plank is either slanted right, represented by character / (ASCII 47), or left, represented by character \ (ASCII 92). For example, a fence of three right-slanted planks followed by two left-slanted planks would be represented by string ///\\.

Fence Inclination theory predicts that plank slants change in steps.

On a single step, the fence is first subdivided into a minimal possible number of plank groups. Each group consists of R ≥ 0 right-slanted planks followed by L ≥ 0 left-slanted planks. In the sample 1 below an initial state is subdivided into 3 groups, while in the sample 2 — into 4 groups.

Next, for every group: if R > L, all planks in the group become right-slanted, if R < L, all planks in the group become left-slanted, if R = L, plank of the group remain unchanged. So after the first step the fence in sample 1 will change into the state //////\\\\.

Steps are repeated until the fence state stops changing.

You program must, given the the initial fence state, output its final state after the changes stop.

Input file format

Input file contains a single string of / and \ characters — representation of the initial fence state.

Output file format

Output file must contain a single string of / and \ characters — representation of the final fence state.

Constraints

The length of the input string is between 1 and 1001 characters.

Sample tests

///\\/\/\\

//////////

/\\//\/\\///

\\\///\\\///

Задача J. Библиотекарь ≡

Условие

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

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

Однажды в библиотеку зашёл читатель. Он дал Аполлинарию Матвеевичу список тем и попросил его подобрать книги по этим темам. Аполлинарий Матвеевич обрадовался: у него есть база данных! Но стоп: как найти в базе данных нужную информацию? Для этого нужна программа.

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

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

Первая строка входного файла содержит целое число N — количество областей знаний.

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

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

Далее входной файл содержит целое число M — количество тем в списке, подготовленном читателем. Далее следует список тем.

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

Для каждой темы требуется вывести строку "Topic: название темы". Далее должна следовать строка "Subject: название области знаний". Далее должна следовать строка "Books:" (без пробелов). Далее должен следовать список книг в том порядке, в котором они перечислены во входном файле.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 10

Количество книг, относящихся к определённой области знаний, от 1 до 100.

Количество тем, затронутых в определённой книге, от 1 до 10.

Все названия во входном файле имеют длину от 1 до 50 символов и состоят из маленьких латинских букв.

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

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

2
mathematics
2
algebra
3
lines
equations
coordinates
geometry
3
triangles
coordinates
lines
physics
2
mechanics
3
force
velocity
mass
gravitation
2
force
mass
5
force
triangles
velocity
coordinates
mass

Topic: force
Subject: physics
Books:
mechanics
gravitation
Topic: triangles
Subject: mathematics
Books:
geometry
Topic: velocity
Subject: physics
Books:
mechanics
Topic: coordinates
Subject: mathematics
Books:
algebra
geometry
Topic: mass
Subject: physics
Books:
mechanics
gravitation

Задача K. Автомобильные номера ≡

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

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

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

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

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача L. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

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

Ограничения

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

5 7 10 3 5 6

16

Задача M. Открытка программиста ≡

Условие

На день святого Валентина Дима решил сделать подарить своей девушке Лене открытку с сердечками. Лена учится в ДВФУ на программиста, поэтому Диме хотелось сделать программистскую открытку.

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

Изображение открытки представляет собой прямоугольную таблицу, состоящую из символов "." (ASCII 46), "/" (ASCII 47), "V" (ASCII 86), "\" (ASCII 92), "^" (ASCII 94). На открытке изображено n сердец. Каждое сердце задаётся координатами центра x y и размером d. Координата x отсчитывается по горизонтали слева направо, а координата y — по вертикали сверху вниз.

Изображение сердца состоит из шести наклонных линий, состоящих из символов "/" и "\". Две линии, образующие нижний контур сердца, имеют длину по d символов, две линии, образующие внешнюю часть верхнего контура, имеют длину по ⌊(d + 1) / 2⌋ символов, а две линии, образующие внутреннюю часть верхнего контура, имеют длину по ⌊(d − 1) / 2⌋ символов.

Центр и нижняя точка сердца обозначены символами "V". Если d чётно, то две верхние точки сердца обозначены символами "^".

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

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

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

Входной файла содержит натуральное число n  — количество сердец, за которым следует n троек натуральных чисел x_i y_i d_i.

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

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

Ограничения

1 ≤ n ≤ 10²

1 ≤ x_i, y_i, d_i ≤ 50

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

3
4 4 3
7 7 6
17 11 1

./\./\............
/..^..\..^........
\./.\././.\.......
./...\./...\......
/.\./.V.....\.....
\..V......../.....
.\........./......
..\......./.......
...\...../...../V\
....\.../......\./
.....\./........V.
......V...........

Задача N. Поврежденный XML ≡

Условие

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки  <  (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка  >  (ASCII 62). Примеры открывающих тегов:  < a > ,  < dog > .

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов:  < /a > ,  < /dog > .

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

• Пустая строка является корректной XML-строкой.
• Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
• Если A — корректная XML-строка, то строка  < X > A < /X > , получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

•  < a >  < /a > 
•  < a >  < ab >  < /ab >  < c >  < /c >  < /a > 
•  < a >  < /a >  < a >  < /a >  < a >  < /a > 

•  < a >  < /b > 
•  < a >  < b > 
•  < a >  < b >  < /a >  < /b > 

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

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

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

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

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

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы  < ,  >  и /.

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

<a></b>

<b></b>

<a><aa>

<a></a>

<a><>a>

<a></a>

<a/</a>

<a></a>

Задача W. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

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

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO