Задача 1. Breadth First Search ≡

Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

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

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

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

Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S. Если какая-то из вершин недостижима из S, выведите единственное число  − 1.

Ограничения

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

3 2 1
1 2
2 3

1 2 3

Задача 2. Метро ≡

Условие

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

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

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

Во входном файле записано сначала число N — количество станций метро в городе. Далее записано число M — количество линий метро. Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

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

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

Ограничения

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

5 2
4 1 2 3 4
2 5 3
3 1

0

5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5

2

10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8

1

4 2
2 1 2
2 3 4
1 3

-1

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

Условие

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

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

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

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

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

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

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

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

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами 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

Задача 4. Праздничный ужин ≡

Условие

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

Меню праздничного новогоднего ужина в кафе состоит из k типов блюд. Для каждого типа блюда есть несколько вариантов на выбор. Всего есть a₁ вариантов для первого типа блюда, a₂ вариантов для второго типа блюда, и так далее, a_k вариантов для k-го типа блюда. Всего, таким образом, предлагается a₁ × a₂ × …  × a_k различных заказов праздничного ужина.

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

Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n₁ = a₁ × a₂ × …  × a_k заказов. Тому, кто выбирал вторым, досталось лишь n₂ < n₁ заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из n_m заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.

Требуется написать программу, которая по заданным числам k, m и n₁, n₂, …, n_m выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.

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

События в примере могли развиваться, например, следующим образом. Исходно количество заказов ужина было равно 3 × 2 × 2 = 12. Директор, выбрав свой заказ, указал блюдо первого типа, поэтому второму сотруднику осталось лишь два варианта блюда первого типа. Количество заказов для него сократилось до 2 × 2 × 2 = 8. Он также указал на свое блюдо первого типа, и Джон уже мог выбирать лишь из 1 × 2 × 2 = 4 заказов ужина.

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

Первая строка входного файла содержит два целых числа k и m, разделенных ровно одним пробелом. Вторая строка содержит m чисел: n₁, n₂, …, n_m.

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

Выходной файл должен содержать k чисел: a₁, a₂, …, a_k. Если возможных вариантов решения поставленной задачи несколько, требуется вывести любой. Соседние числа должны быть разделены ровно одним пробелом. Гарантируется, что хотя бы одно решение существует.

Ограничения

1 ≤ k ≤ 20; 2 ≤ m ≤ 100; ∀ i ∈ 1..m: 1 ≤ n_i ≤ 10⁹

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

3 3
12 8 4

3 4 1

Задача 5. Ставка ≡

Условие

Андрей очень любит играть в Космический покер.

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа A и C — коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле: A ⋅ (r² + g² + b²) + C ⋅ min { r, g, b}, где r, g, b — количество фишек красного, зеленого и синего соответственно.

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

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

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

В первой строке задано одно целое число t (1 ≤ t ≤ 10 000) — количество игровых ситуаций.

Каждая игровая ситуация описывается двумя строками. В первой строке задано два целых числа A и C (1 ≤ A, C ≤ 10) — коэффициенты для вычисления выигрыша. Во второй строке задано три целых числа r, g и b (0 ≤ r, g, b ≤ 15) — количество фишек красного, зеленого и синего цвета, соответственно.

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

Выведите t строк. В k-ой строке выведите RED, если оптимально добавить красную фишку, GREEN, если оптимально добавить зеленую фишку или BLUE, если оптимально добавить синюю фишку. Если есть несколько оптимальных вариантов, можно вывести любой из них

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

3
2 10
2 4 4
1 2
3 4 5
4 2
7 7 7

RED
BLUE
GREEN

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Problem 7. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

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

Условие

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

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

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

Входной файл содержит целое число 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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 100

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

3

1

4

6

5

20

Задача C. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Задача D. Последний урок ≡

Условие

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

Например, Вася, получивший в течение четверти оценки 3, 4, 2, 3, 3, 5, будет иметь среднюю оценку 20 / 6 = 3.3333... и получит итоговую оценку 3.

Средние оценки 1.5, 2.5, 3.5 и 4.5 округляются до 2, 3, 4 и 5 соответственно.

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

Например, если Вася на последнем уроке сумеет получить пятёрку, то его средняя оценка станет равна 25 / 7 = 3.571... и итоговая оценка повысится до 4 баллов.

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

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

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

Ограничения

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

1
6 2 2 2 2 2 2

0

2
6 3 4 2 3 3 5
4 4 5 4 5

1

Задача E. Восстановление сетки ≡

Условие

Турнир по олимпийской системе, состоящий из N раундов, проводятся между 2^N участниками по следующей схеме: сначала составляется последовательность из расставленных в произвольном порядке игроков. В первом раунде первый в последовательности участник соревнуется со вторым, третий с четвёртым, и т.д. Проигравшие выбывают из турнира, и на втором раунде победитель первой пары играет с победителем второй, победитель третьей с победителем четвёртой, и т.д. Наконец, после N-го раунда остаётся ровно один участник, который становится победителем турнира.

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

Рекомендуется рассмотреть частичные решения

N ≤ 10;

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

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

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

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

Ограничения

1 ≤ N ≤ 20

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

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

7 8 6 5 3 4 1 2 

Задача F. Марсианский заголовок ≡

Условие

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

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

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

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

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

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

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

Вторая строка входного файла содержит текст статьи.

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

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

Ограничения

1 ≤ M ≤ 99

Длина текста составляет от 2 до 5000 символов.

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

50
aAb

aA

30
xxxxXXxxX

xxxxXXx

99
ab

a

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

Условие

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

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

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

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

Ограничения

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

5 7 10 3 5 6

16

Задача H. Слово из кубиков ≡

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

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

Условие

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

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

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

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

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

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

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

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

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

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача J. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

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

Входной файл содержит целые числа a b c.

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

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

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

12 31 25

YES
12 13

12 31 26

NO

Задача K. Длинное взятие ≡

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

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

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

Ограничения

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

5
.....
.O.O.
....X
.O.O.
X....  

e3-c1-a3-c5-e3  

4
X...
....
....
...O  

Impossible

Задача L. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Problem M. Lin-log sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

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

Условие

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

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

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

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

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

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

Наряду с аддитивной цветовой моделью 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 

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

Условие

Марфа Геннадьевна собрала большой урожай лука и решила поделиться им с подружками. Она сделала 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

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

Условие

У Марфы Геннадьевны есть кошелёк, который она всегда носит с собой. Она любит, чтобы в кошельке было всегда ровно 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 

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

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 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

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

Условие

Изображение кирпичной стены состоит из 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

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

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

Условие

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

Для приготовления коктейля требуется 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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

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

1 1

2

2 2

1

Задача U. Поездка на Хэллоуин ≡

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (X_A; Y_A) и (X_B; Y_B).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (X_S; Y_S) и конца (X_E; Y_E). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере C_R. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере C_F за каждый километр пути — ущерб за раздавленные тыквы.

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

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

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

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

Ограничения

 − 10³ ≤ X_A, Y_A, X_B, Y_B, X_S, Y_S, X_E, Y_E ≤ 10³

1 ≤ C_F ≤ 10³

1 ≤ C_R ≤ 10⁶

Дома программистов находятся в разных точках и не находятся на дороге

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

1 1 2 2 0 3 3 0 1 1

2.414213562373095

1 5 4 0
-2 -2 10 10
1 2

7.656854249492381

10 10 25 19
15 13 20 16
1 1000000

17.492855684535900

Задача V. Задача Пифагора ≡

Условие

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

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

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

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

Ограничения

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

10.0 10.0 10.0

25.00000

Задача W. Пеленг НЛО ≡

Условие

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго — 180°).

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

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

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

Ограничения

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

45.1 135.0

49.9127 50.0873

135.0 45.0

0 0

Задача X. Поворот отрезка ≡

Условие

Вершины отрезка AB имеют координаты (X_a; Y_a) и (X_b; Y_b).

Требуется найти координаты вершин отрезка A^* B^* (X^*_a; Y^*_a) и (X^*_b; Y^*_b), полученного путём поворота отрезка AB вокруг точки O (X_o; Y_o) на β градусов.

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

Входной файл содержит целые числа X_a, Y_a, X_b, Y_b, X_o, Y_o, β

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

Выходной файл должен содержать четыре вещественных числа X^*_a, Y^*_a, X^*_b, Y^*_b с точностью 10^− 3.

Ограничения

0 ≤ |X_a|, |Y_a|, |X_b|, |Y_b|, |X_o|, |Y_o| ≤ 10⁵

0 ≤ β  ≤ 360

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

1 1  2 2  0 0  90

-1.000000000 1.000000000 -2.000000000 2.000000000

1 1  2 2
0 0
45

0.000000000 1.414213562 0.000000000 2.828427125

7 5
11 11
9 8
180

11.000000000 11.000000000 7.000000000 5.000000000

Задача Y. Быстрее к границе! ≡

Условие

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

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

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

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

Ограничения

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

-1 0
1 1 4 3

2.236

2 2
1 1 4 3

1

Задача Z. Пересечение двух прямых ≡

Условие

Прямая a проходит через точки A₁ (a_X1; a_Y1) и A₂ (a_X2; a_Y2). Прямая b проходит через точки B₁ (b_X1; b_Y1) и B₂ (b_X2; b_Y2).

Требуется найти точку пересечения прямых a и b или установить что прямые параллельны.

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

Во входном файле содержаться восемь целых чисел — a_X1, a_Y1, a_X2, a_Y2, b_X1, b_Y1, b_X2, b_Y2

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

Выходной файл должен содержать:

• Единственное число  − 1, если прямые совпадают;
• Единственное число 0, если прямые параллельны и не имеют общих точек;
• Два вещественных числа X₀, Y₀ — координаты точки пересечения прямых с точностью 10^− 3, если прямые пересекаются в одной точке;

Ограничения

0 ≤ |a_Xk|, |a_Yk|, |b_Xk|, |b_Yk| ≤ 10⁵

A₁ ≠ A₂

B₁ ≠ B₂

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

0 0  2 2  1 1  3 3

-1

0 0  1 1
2 3  5 6

0

1 1
3 5
-1 5
8 -1

2.000000000 3.000000000