Problem 1. Breadth First Search

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 1
1 2
2 3
1 2 3

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

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:e.in   Ограничение памяти:64 Мб
Выходной файл:e.out  

Условие

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

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

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

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

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

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

В выходной файл выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, выведите в выходной файл одно число  − 1 (минус один).

Ограничения

2 ≤ N ≤ 100, 1 ≤ M ≤ 20, 2 ≤ Pi ≤ 50.

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

Входной файл (e.in) Выходной файл (e.out)
1
5 2
4 1 2 3 4
2 5 3
3 1
0
2
5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
2
3
10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
1
4
4 2
2 1 2
2 3 4
1 3
-1

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

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

Условие

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

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

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

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

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

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

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

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

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

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

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

Входной файл содержит числа V M N — соответственно скорость вытекания воды (в м / с), поток втекающей воды (м3 / c) и количество отверстий в лицевой стороне аквариума. Далее следует N троек чисел xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер i. Отверстия не пересекаются и не соприкасаются друг с другом.

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

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

Ограничения

0 < V, M ≤ 1000, 0 ≤ N ≤ 100, 0 ≤ xi, yi, ai ≤ 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0
2.0

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:dinner.in   Ограничение памяти:256 Мб
Выходной файл:dinner.out  

Условие

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

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

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

Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n1 = a1 × a2 × … × ak заказов. Тому, кто выбирал вторым, досталось лишь n2 < n1 заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из nm заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.

Требуется написать программу, которая по заданным числам k, m и n1, n2, , nm выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.

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

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

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

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

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

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

Ограничения

1 ≤ k ≤ 20; 2 ≤ m ≤ 100; ∀ i ∈ 1..m: 1 ≤ ni ≤ 109

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

Входной файл (dinner.in) Выходной файл (dinner.out)
1
3 3
12 8 4
3 4 1

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

Автор:А. Станкевич, Н. Ведерников (Жюри XXI командной олимпиады школьников СПб по информатике)   Ограничение времени:2 сек
Входной файл:bet.in   Ограничение памяти:256 Мб
Выходной файл:bet.out  

Условие

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

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа A и C — коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле: A⋅ (r2 + g2 + b2) + 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, если оптимально добавить синюю фишку. Если есть несколько оптимальных вариантов, можно вывести любой из них

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

Входной файл (bet.in) Выходной файл (bet.out)
1
3
2 10
2 4 4
1 2
3 4 5
4 2
7 7 7
RED
BLUE
GREEN

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:diploma.in   Ограничение памяти:64 Мб
Выходной файл:diploma.out  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Problem 7. Square sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

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

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

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105, 1 ≤ ui, vi ≤ N.

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

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

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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 100

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

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

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

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

Условие

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

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

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

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

Первая строка входного файла содержит целое число N. Следующие N строк содержат по одному слову каждая.

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

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

Ограничения

1 ≤ N ≤ 100

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
e
ee
eee
ee
2
3
aabbee
cyydyyy
xiixiixiii
aabbee
xiixiixiii

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

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

Условие

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

Например, Вася, получивший в течение четверти оценки 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 баллов.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100; 1 ≤ Q ≤ 100

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

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

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

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

Условие

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

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

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

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

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

N ≤ 10;

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

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

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

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

Ограничения

1 ≤ N ≤ 20

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

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

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

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ M ≤ 99

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
50
aAb
aA
2
30
xxxxXXxxX
xxxxXXx
3
99
ab
a

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 20, 1 ≤ Ti ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 10 3 5 6
16

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

Автор:A. Klenin   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

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

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

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

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

Ограничения

1 ≤ N, K ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

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

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:64 Мб
Выходной файл:numbers.out  

Условие

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

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

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

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

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

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

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

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

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

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

Входной файл (numbers.in) Выходной файл (numbers.out)
1
X772KX
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

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

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

Условие

Заданы три числа: 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 < 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
12 31 25
YES
12 13
2
12 31 26
NO

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

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

Условие

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

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

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

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

В первой строке входного файла содержится число N. В следующих N строках — описание позиции, состоящее из символов '.' (точка), 'O' (заглавная латинская О),'X' (заглавная латинская X). Они определяют пустую клетку, белую шашку и черную шашку соответственно.

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

В выходном файле должна содержаться единственная строка вида L1 N1 − L2 N2 − … − LK NK, где K ≥ 1, или Impossible если взятие невозможно.

Ограничения

1 ≤ N ≤ 12

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.O.O.
....X
.O.O.
X....  
e3-c1-a3-c5-e3  
2
4
X...
....
....
...O  
Impossible

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

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
9 30
0
2
4 3
0 101 5 12
7

Problem M. Lin-log sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

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

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

Условие

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

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

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

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

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

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

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

Модель RYB позволяет легко найти цвет смеси двух красок. При смешивании цветов (r1, y1, b1) и (r2, y2, b2) получается цвет (r3, y3, b3), где r3 = (r1 + r2) / k, y3 = (y1 + y2) / k, b3 = (b1 + b2) / k. Здесь k = max{r1 + r2, y1 + y2, b1 + b2}.

Даны цвета (r1, y1, b1) и (r3, y3, b3). С каким цветом (r2, y2, b2) нужно смешать первый цвет, чтобы получить третий цвет?

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

Первая строка входного файла содержит вещественные числа r1 y1 b1. Вторая строка содержит вещественные числа r3 y3 b3.

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

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

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

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

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

Ограничения

0 ≤ r1, y1, b1, r3, y3, b3 ≤ 1

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0 0
1 1 0
0.00000 1.00000 0.00000 
2
1 0.5 0
1 1 0
0.50000 1.00000 0.00000 
3
0.25 1 0.5
0.5 0.75 1
0.50000 0.12500 1.00000 

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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, K, M ≤ 100.

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

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

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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, K ≤ 100.

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

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

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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105, 1 ≤ ai ≤ N. Все числа ai различны.

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

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

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

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

Условие

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

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

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

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

Входной файл содержит целые числа Bw Bh Ww Wh.

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

Выходной файл должен содержать Wh × Bh + 1 строк по Ww × Bw символов в каждой — изображение стены.

Ограничения

1 ≤ Bw, Bh, Ww, Wh ≤ 50, число Bw — чётное

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

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

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 1000

1 ≤ pi ≤ 100

p1 + p2 + …  + pN = 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
50 300
50 400
600.000
2
3
20 30
30 40
50 39
78.000

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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Оба программиста живут за городом. Их дома расположены в точках с координатами (XA; YA) и (XB; YB).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (XS; YS) и конца (XE; YE). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере CR. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере CF за каждый километр пути — ущерб за раздавленные тыквы.

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

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

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

Во входном файле содержатся десять целых чисел: XA YA XB YB XS YS XE YE CF CR

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

Выходной файл должен содержать единственное число — минимальные затраты при перемещении из A в B с абсолютной ошибкой не более 10 − 3.

Ограничения

 − 103 ≤ XA, YA, XB, YB, XS, YS, XE, YE ≤ 103

1 ≤ CF ≤ 103

1 ≤ CR ≤ 106

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 2 2 0 3 3 0 1 1
2.414213562373095
2
1 5 4 0
-2 -2 10 10
1 2
7.656854249492381
3
10 10 25 19
15 13 20 16
1 1000000
17.492855684535900

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

Автор:Южно-Уральский открытый командный чемпионат   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

Все числа вещественные, больше 0 и меньше 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10.0 10.0 10.0
25.00000

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

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

Во входном файле содержатся вещественные числа a и b, разделенные пробелами.

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

В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 0 (нуль).

Ограничения

0 ≤ a, b ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
45.1 135.0
49.9127 50.0873
2
135.0 45.0
0 0

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

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

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

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

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

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

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

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

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

Условие

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

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

Входной файл содержит два целых числа xA yA — координаты точки A, за которыми следуют четыре целых числа x1 y1 x2 y2 — координаты двух противоположных углов прямоугольника.

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

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

Ограничения

 − 1000 ≤ x, y, x1, y1, x2, y2 ≤ 1000; x1 ≤ x2, y1 ≤ y2

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

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

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

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

Условие

Прямая a проходит через точки A1 (aX1; aY1) и A2 (aX2; aY2). Прямая b проходит через точки B1 (bX1; bY1) и B2 (bX2; bY2).

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

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

Во входном файле содержаться восемь целых чисел — aX1, aY1, aX2, aY2, bX1, bY1, bX2, bY2

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

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

Ограничения

0 ≤ |aXk|, |aYk|, |bXk|, |bYk| ≤ 105

A1 ≠ A2

B1 ≠ B2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 0  2 2  1 1  3 3
-1
2
0 0  1 1
2 3  5 6
0
3
1 1
3 5
-1 5
8 -1
2.000000000 3.000000000

2.151s 0.014s 91