Высота, биссектриса, медиана

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Требуется построить такой треугольник ABC, что его высота равна AH, биссектриса AD, медиана AM. Если решений несколько -- выведите любое.

Входные данные

Вам даны 3 действительных числа AH, AD, AM (положительные, не превосходящие 100).

Выходные данные

В первую строку выведите YES или NO. Искомый треугольник должен быть не вырожденным, то есть иметь ненулевую площадь. Числа выводите с 8 точными знаками после запятой.

Пример

Ввод

Test #1
1 1 1

Test #2
1 1 2

Вывод

Test #1
YES
0 1
-0.5 0
0.5 0

Test #2
NO

Задача короля

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Давным давно жил король у которого было N сыновей. В этом же королевстве жило N прекрасных девушек. Король знал, какие девушки нравятся каждому сыну. Сыновья короля были умными и передовыми, т.е. возможно, что одному сыну нравится несколько девушек.
Король попросил придворного волшебника найти для каждого сына пару. Волшебник выполнил задание -- нашел для каждого сына пару, причем так, что каждая девушка вышла замуж за одного сына.
Однако, король посмотрел список и сказал: "Мне нравится список, который ты сделал, но я не совсем доволен. Для каждого сына я хотел бы знать всех девушек, на которых он мог бы жениться. Конечно, после его женитьбы на девушке для каждого другого сына ты должен суметь найти пару."
Эта задача оказалась не по силам волшебнику. Помогите ему.

Входные данные

Первая строка содержит натуральное число N (1 <= N <= 2000). Следующие N строк содержат список девушек, которые нравятся соответствующему сыну. Первое число каждого списка Ki обозначает количество девушек, которые ему нравятся. Следующие Ki чисел обозначают самих девушек. Сумма всех Ki не превосходит 200000.
Последняя строка входного файла содержит составленный волшебником список: A1, A2,..., AN. Число Ai обозначает номер девушки, на которой он должен жениться в соответствии с первоначальным списком волшебника. A1, A2,..., AN -- перестановка чисел от 1 до N. Гарантируется, что список корректен.

Выходные данные

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

Пример

Ввод

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

Вывод

2 1 2
2 1 2
1 3
1 4

Идентификация символов

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Есть ч/б монитор размером N x M пикселей. На нем могут выводиться K символов (каждый символ характеризуется некоторым ненулевым количеством черных пикселей на экране). Необходимо найти минимальное количество пикселей, по которым можно однозначно восстановить символ.

Входные данные

В первой строке файла записаны числа N, M и K (1 <= N, M <= 10, 2 <= K <= 6), разделенные пробелами. В следующих строках записаны K блоков по N строк, в каждой строке по M цифр - описание символов. Блоки разделены пустой строкой. '1' означает, что при выводе этого символа соответствующий пиксель черный, '0' означает, что белый. Гарантируется, что все символы уникальны.

Выходные данные

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

Пример

Ввод

2 4 3
0000
0001

1000
0001

1111
1001

Вывод

2
1000
1000

Конверсия

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

Во входном файле содержится единственное число R - радиус шара. R - положительное действительное число не большее 100, содержащее не более 5 знаков после запятой.

Выходные данные

В выходной файл выведите длину ребра тетраэдра с 5 знаками после запятой.

Пример

Ввод

0.0001

Вывод

0.00033

277. "Upgrade" дорог

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

Первая строка файла содержит три натуральных числа N (1 <= N <= 100), X - номер единственного некрупного города, и M - количество дорог. Следующие M строк описывают существующие дороги. Каждая строка содержит 3 натуральных числа: номера двух городов (города нумеруются от 1 до N), между которыми проложена дорога, и длину дороги, длина дороги - натуральное число не превосходящее 1000. Все числа в строках разделены одним или несколькими пробелами. Гарантируется, что между любыми двумя городами имеется не более одной дороги.

Выходные данные

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

Пример

Ввод

6 6 10
1 2 10
2 3 10
3 4 10
4 5 10
5 1 2
1 6 6
2 6 6
3 6 6
4 6 6
5 6 6

Вывод

26

ABBA

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Даны два целых числа a и b (0 < a, b < 10). Ваша задача сравнить числа a^b и b^a.

Входные данные

Во входном файле записаны целые числа a и b (0 <a,b < 10).

Выходные данные

Выведите "EQUAL", если a^b = b^a, "GREATER", если a^b > b^a, и "LESS", если a^b < b^a.

Пример

Ввод

1 2

Вывод

LESS

Дерево

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

Во входном файле в первой строке содержатся два целых числа N и M (1 <= N <= 100, 0 <= M <= 1000), записанные через пробел. Далее следуют M различных строк с описаниями ребер, каждая из которых содержит два натуральных числа Ai и Bi (1 <= Ai < Bi <= N), где Ai и Bi - номера вершин, соединенных i-м ребром.

Выходные данные

В выходной файл выведите слово YES, если граф является деревом или NO - в противном случае.

Пример

Ввод

3 2
1 2
1 3

Вывод

YES

Печатный пиар

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Маленькому пиар-агентству поступил заказ на изготовление крупной партии агитационных материалов. Требуется изготовить и доставить N листовок. У агентства есть всего один принтер, но на нем можно распечатать любую из листовок. Листовки могут быть разные, поэтому на их распечатку может потребоваться различное время, на распечатку i-й листовки требуется Ti минут. Сразу после того, как листовка распечатана, ее требуется доставить адресату. В распоряжении агентства имеется неограниченное число курьеров, поэтому сразу, как только листовка распечатана, курьер везет ее к адресату. Адресаты у листовок различны, на доставку i-й листовки требуется Li минут. Вас наняли рассчитать минимально возможное время, которое пройдет от начала печати до доставки последней листовки, с учетом того, что печатать листовки можно в произвольном порядке.

Входные данные

В первой строчке входного файла записано целое число N (1 <= N <= 100). Вторая строка содержит N целых чисел Ti (1 <= i <= N). Третья строка содержит N целых чисел Li (1 <= i <= N). Известно, что 1 <= Ti, Li <= 1000. Числа во второй и третьей строках разделены одним или несколькими пробелами.

Выходные данные

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

Пример

Ввод

2
2 1
2 1

Вывод

4