Задача A. Правильная окраска ≡

Условие

По мотивам романа И.А. Ильфа и Е.П. Петрова "Двенадцать стульев".

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

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

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

Его компаньон Остап Бендер купил в аптеке другую микстуру "Наяда". Но после перекраски оказалось, что, смешавшись с зеленью "Титаника", это средство неожиданно окрасило голову и усы Ипполита Матвеевича в краски солнечного спектра. После скептического осмотра Остап предложил Воробьянинову сбрить усы и волосы.

Всё могло бы быть иначе, если бы концессионеры точно рассчитали цвет второго флакона. Посмотрим, как можно это сделать.

Наряду с аддитивной цветовой моделью RGB, используемой для кодирования цветов пикселей экрана, существует и субтрактивная модель RYB, которая применяется для представления цвета в изобразительном искусстве. Для задания цвета в этой модели нужно указать количество красного, желтого и синего цвета как число от 0 до 1. Так, 100 — это красный цвет, 001 — синий, 111 — чёрный, а 110 — оранжевый.

Модель RYB позволяет легко найти цвет смеси двух красок. При смешивании цветов (r₁, y₁, b₁) и (r₂, y₂, b₂) получается цвет (r₃, y₃, b₃), где r₃ = (r₁ + r₂)/k, y₃ = (y₁ + y₂)/k, b₃ = (b₁ + b₂)/k. Здесь k = max{r₁ + r₂, y₁ + y₂, b₁ + b₂}.

Даны цвета (r₁, y₁, b₁) и (r₃, y₃, b₃). С каким цветом (r₂, y₂, b₂) нужно смешать первый цвет, чтобы получить третий цвет?

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

Первая строка входного файла содержит вещественные числа r₁ y₁ b₁. Вторая строка содержит вещественные числа r₃ y₃ b₃.

Хотя бы одно из чисел в каждой тройке равно 1.

Во входных данных не более 2-х знаков после запятой.

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

Требуется вывести в выходной файл вещественные числа r₂ y₂ b₂ с точностью не менее 5 знаков после запятой.

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

Ограничения

0 ≤ r₁, y₁, b₁, r₃, y₃, b₃ ≤ 1

Гарантируется, что для заданных исходных данных задача имеет решение.

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

1 0 0
1 1 0

0.00000 1.00000 0.00000 

1 0.5 0
1 1 0

0.50000 1.00000 0.00000 

0.25 1 0.5
0.5 0.75 1

0.50000 0.12500 1.00000 

Задача B. Кирпичная стена ≡

Условие

Изображение кирпичной стены состоит из W_h слоёв по W_w кирпичей в каждом. Изображение кирпича состоит из B_h строк по B_w символов в каждой. Все строки изображения кирпича начинаются с символа '|' (ASCII 124). Остальные символы в первых B_h − 1 строках изображения кирпича  — '.' (ASCII 46), а в последней строке — '_' (ASCII 95).

Изображения в слоях с чётными номерами циклически сдвинуты на B_w / 2 символов вправо. Всё изображение стены предваряется одной строкой, состоящей из W_w × B_w символов '_' (ASCII 95).

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

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

Входной файл содержит целые числа B_w B_h W_w W_h.

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

Выходной файл должен содержать W_h × B_h + 1 строк по W_w × B_w символов в каждой — изображение стены.

Ограничения

1 ≤ B_w, B_h, W_w, W_h ≤ 50, число B_w — чётное

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

2 1 1 1

__
|_

4 2 5 3

____________________
|...|...|...|...|...
|___|___|___|___|___
..|...|...|...|...|.
__|___|___|___|___|_
|...|...|...|...|...
|___|___|___|___|___

Задача C. Коктейль ≡

Условие

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

Для приготовления коктейля требуется p_i% i-го сока (p_i% — массовая доля). В наличии имеется a_i граммов i-го сока. Сколько граммов коктейля можно приготовить?

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 1000

1 ≤ p_i ≤ 100

p₁ + p₂ + … + p_N = 100

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

2
50 300
50 400

600.000

3
20 30
30 40
50 39

78.000

Задача D. Государство ≡

Условие

Жили-были в одномерном пространстве два правителя одного государства — два брата. Государство их было маленьким, всего одна клетка. (Всё одномерное пространство разделено на клетки.)

И решили они расширить пределы своего государства, завоёвывая новые территории. Стали братья по очереди отправлять войска либо влево, либо вправо. Каждый раз в поход ходил только один брат. Но в одной клетке жила Баба Яга со своим сказочным войском, и её одному брату было не одолеть, только вдвоём.

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

Схема территории показана на рисунке. В начальный момент времени государство занимает клетку с номером N+1, и братьям доступны для завоевания ещё 2 N клеток. Баба Яга занимает клетку с номером k.

Кто победит в игре при оптимальной игре игроков? Начинает игру игрок с номером 1.

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

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

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

Выходной файл должен содержать число 1, если победит первый игрок, и число 2, если победит второй игрок.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ k ≤ N.

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

1 1

2

2 2

1

Задача E. Y-хромосома ≡

Условие

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

На Марсе есть квадратное световое табло, разделённое на N × N квадратиков. Каждый квадратик может либо светиться, либо не светиться. Требуется, чтобы на табло появилась буква Y в виде русской буквы У.

Буква должна состоять из двух диагональных линий. Первая линия должна идти слева направо и снизу вверх под углом 45°, начинаться она может с любого места. Вторая линия должна начинаться с любого не крайнего квадратика первой линии и идти влево и вверх (также под углом 45°) до тех пор, пока не достигнет самой левой горизонтали или самой верхней вертикали первой линии. В первой (большой) диагонали должно быть не менее 3-х клеток. Примеры таких букв показаны на рисунке.

Сколько существует способов изобразить букву Y на табло N × N? Буквы, отличающиеся размерами и/или местом, либо положением второй (маленькой) диагонали, считаются различными.

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

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

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

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

Ограничения

3 ≤ N ≤ 100

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

3

1

4

6

5

20

Задача F. Марфа Геннадьевна на даче ≡

Условие

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

Но к Марфе Геннадьевне пришли M подружек, где NK делится на M, но N не обязательно равно M. Чтобы никого не обидеть, Марфа Геннадьевна хочет разделить лук поровну между всеми подружками. Вероятно, для этого придётся разрезать некоторые связки.

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

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

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

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

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

Далее должны следовать N блоков чисел, по блоку на связку с луком. Для каждой связки нужно вывести информацию о разрезах. Каждый блок должен начинаться с целого числа a_i — количества разрезов, за которым должны следовать (a_i + 1) пар чисел b_ij c_ij (b_ij > 0, 1 ≤ c_ij ≤ M). Здесь b_ij — количество луковиц в j-й части связки, c_ij — номер подружки, которой достанется эта часть.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N, K, M ≤ 100.

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

2 2 2

0
0  2 1
0  2 2

3 2 2

1
1  1 1  1 2
0  2 1
0  2 2

Задача G. Марфа Геннадьевна и монеты ≡

Условие

У Марфы Геннадьевны есть кошелёк, который она всегда носит с собой. Она любит, чтобы в кошельке было всегда ровно K монет. Монеты могут быть достоинством 1, 2, 5 или 10 рублей.

Но у Марфы Геннадьевны в кошельке оказалось N монет, где N может быть не равно K. За одно действие Марфа Геннадьевна может вынуть монету из кошелька либо положить монету в кошелёк. Требуется выполнить минимальное количество действий, чтобы в кошельке оказалось K монет и та же сумма.

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

Входной файл содержит целые числа N K, за которыми следуют N целых чисел a_i, где a_i = 1, 2, 5 или 10 — достоинства монет в кошельке.

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

Выходной файл должен содержать целое число M — количество действий, за которым должно следовать M чисел b_i, где b_i = ± 1, ± 2, ± 5 или ± 10, положительное число означает, что монету соответствующего достоинства нужно положить в кошелёк, а отрицательное — что монету нужно достать из кошелька (при этом в кошельке должна лежать по крайней мере одна монета с таким достоинством).

Если решений несколько, выведите любое из них.

Если невозможно оставить в кошельке K монет с такой же суммой, выходной файл должен содержать единственное число −1.

Ограничения

1 ≤ N, K ≤ 100.

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

5 3
2 2 2 2 1

4
5 -1 -2 -2 

Задача H. Марфа Геннадьевна и документы ≡

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

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

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

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

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

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

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

Далее должны следовать K пар целых чисел. Пара −j i означает выкладывание документа с номером j, находящегося в i-м файле. Пара j i означает вкладывание документа с номером j в i-й файл. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ N. Все числа a_i различны.

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

3
1 3 2

4
-3 2
-2 3
3 3
2 2

4
1 4 2 3

6
-4 2
-3 4
4 4
-2 3
3 3
2 2

3
1 2 3

0

Задача I. Листовая медиана ≡

Условие

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

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

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа u_i v_i — номера вершин, которые соединены этим ребром.

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

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

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

7
1 4
2 3
2 4
2 5
4 6
4 7

3