Корпоративная вечеринка

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

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

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

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

В первой строке входного файла записано натуральное число N (1 <= N <= 255), где N - количество служащих нижнего звена в корпорации. Далее в N строках записана матрица неотрицательных целых чисел размерности NxN, где число в позиции (i,j) обозначает зарплату общего начальника i-ого и j-ого служащих нижнего звена (если таких начальников несколько, дается зарплата самого низкооплачиваемого начальника). Гарантируется, что матрица симметрична относительно главной диагонали. Очевидно, на главной диагонали матрицы записаны зарплаты служащих нижнего звена. Все числа в строках разделяются пробелами. Гарантируется, что любая зарплата не превосходит 10000.

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

В первую строку выходного файла выведите число K - количество служащих (вместе с Президентом) в корпорации. Присвойте каждому служащему уникальный номер от 1 до K. Далее выведите K строк, описывающих служащих. Каждая строка должна соответствовать некоторому служащему и начинаться с двух целых чисел - его уникального номера и его зарплаты. Затем должен следовать список уникальных номеров его непосредственных подчиненных. Строки выводите в любом порядке. Числа в строках разделяйте пробелами. Уникальные номера непосредственных подчиненных в списках выводите в любом порядке. Если информация на сайте наверняка неправильная, то есть не существует структуры корпорации, соответствующей информации на сайте и удовлетворяющей условию задачи, выводите "NO SOLUTION" (без кавычек).

Пример

Ввод

5
1 27 28 28 12
27 2 28 28 27
28 28 3 26 28
28 28 26 4 28
12 27 28 28 5

Вывод

9
1 28 4 3
4 26 2 9
9 4
2 3
3 27 7 8
8 2
7 12 6 5
5 5
6 1

Бутерброд

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

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

Дядя Федор очень любит есть. Однажды Федор сделал огромный бутерброд с колбасой. Этот бутерброд, уже приготовленный непосредственно к поеданию, лежал на столе, когда в кухню вошел кот Матроскин. Бутерброд состоял из К слоев колбасы и Х слоев хлеба. Как раз в это время кот учился пользоваться линейкой. В целях совершенствования своих навыков измерителя он измерил расстояние от пола до каждого слоя хлеба или колбасы. Затем Федор с огромным удовольствием съел этот бутерброд. Вернувшись домой, кот Матроскин решил узнать, правильно ли съел бутерброд дядя Федор. Как известно, считается, что бутерброд съеден правильно тогда и только тогда, когда нижний слой бутерброда во время поедания был колбасный. Итак, помогите Матроскину определить, правильно ли Федор съел бутерброд.

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

На вход вашей программе кот Матроскин введет К и Х, затем К чисел - расстояния от пола до каждого из колбасных слоев и, наконец, Х чисел - расстояния от пола до каждого из хлебных слоев.
Все числа неотрицательные целые и не превосходят миллиона.

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

Выведите RIGHT, если Федор правильно съел бутерброд, WRONG в противном случае.

Пример

Ввод

Пример №1
10 0
1 2 3 4 5 6 7 8 9 10

Пример №2
2 2
2 3
1 4

Вывод

Пример №1
RIGHT

Пример №2
WRONG

Отдых на море

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

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

Наступило лето, и дядя Федор ждал, что вся семья отправится в Простоквашино. Но мама сказала: "У меня 3 вечерних платья, а одеть их негде!". Все уговоры поехать в Простоквашино не увенчались успехом. Итак, родители Федора точно решили ехать на море, несмотря на недовольство его отца. Федор спросил у отца: "Когда же вы вернетесь?". И тут его папа задумался. До моря К километров, поезд едет со скоростью V километров в час и делает О остановок по М минут. Обратно они поедут этим же поездом. На семейном совете было решено, что, приехав на юг, мама Федора сразу же надевает первое платье, носит его F часов, затем сразу же надевает второе, носит его S часов, и, наконец, надевает третье платье и носит его T часов. После этого, собрав все вещи за один час, они тут же погружаются на поезд и едут обратно.
Зная все эти подробности, помогите папе дяди Федора посчитать, через сколько часов они вернутся из путешествия.

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

В файле записано 7 натуральных чисел. К, V, О, М, F, S, T. Все числа не превосходят 1000.

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

Выведите единственное число с точностью до 3 знаков - ответ на поставленную задачу.

Пример

Ввод

600 60 20 3 7 13 11

Вывод

54.000

Посылка с моря

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

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

Путешествие, вопреки прогнозам и обещаниям отца Федора, затянулось. Из Шарика не получилось хорошего охотника, поэтому дядя Федор пообещал ему фото ружье. Он написал письмо родителям с просьбой прислать ему это "оружие", и родители отправили ружье посылкой (зная нашу почту, представьте, сколько времени находились на море родители Федора). Но почтальон Печкин не захотел отдавать посылку, так как ни у кота Матроскина, ни у Шарика, ни у Федора не было документов. Поэтому они решили пойти на хитрость, подменив ящик с посылкой ящиком со всяким мусором. Для этого, они пригласили почтальона Печкина в гости и угостили его чаем и конфетами. Но, увы и ах, Печкин не взял стул, а сел прямо на коробку, после чего начал с огромной скоростью потреблять чай и конфеты. Федор все время находился в комнате, а Шарик иногда выходил порубить дрова, Матроскин выходил доить корову. Коробка, в которой прислали посылку, была очень тяжелая, поэтому, чтобы подменить ее, всем троим (Федору, Матроскину и Шарику) нужно было присутствовать в комнате. Разумеется, Печкина при этом в комнате быть не должно, поэтому менять коробки можно было только, когда он выбегал за птичкой Галчонок(как вы все помните Галчонок отбирал у Печкина конфеты). Дядя Федор, Матроскин и Шарик долго тренировались и выяснили, что для замены коробки им требуется T секунд.

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

В первой строке входного файла, записано 4 натуральных числа Т, N, K, M (T <= 100, N <= 100, K <= 100, M <= 100). Далее следует еще три строки. В первой из них записано N пар натуральных чисел ai bi - время начала и конца i-ой рубки дров Шариком. В второй из них записано К пар натуральных чисел qi wi - время начала и конца очередной дойки коровы Матроскиным. В последней строке записано M пар натуральных чисел zi xi - время начала и конца очередной погони Печкина за птичкой. Все интервалы заданы в секундах. Интервалы в каждом из множеств могут идти в произвольном порядке, но они не могут пересекаться. Кроме всего прочего длительность каждого интервала неменьше 3 секунд. Если Матроскин, Шарик или Печкин зашли в комнату, то они находятся там хотя бы одну секунду (ai, bi, qi, wi, zi, xi <= 1000).

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

Выдайте наименьший момент времени, когда Федор, Матроскин и Шарик могут начать менять коробки или NO, если такого момента не существует. Помните, что менять коробку можно только, когда все трое находятся в комнате, при этом они должны успеть сделать обмен до того, как вернется Печкин и до того как уйдет кто-нибудь из этой компании. Стоит заметить, что нельзя прерывать обмен коробок ни на минуту. Если обмен начат, то он должен быть закончен без всякого замедления и прерывания.

Пример

Ввод

10 1 1 2
1 10
25 35
3 19 39 48

Вывод

324. Фигвам!

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

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

Шарик и Матроскин опять поссорились! Естественно, они не разговаривают друг с другом. Но так как они хотят говорить друг другу гадости, они были вынуждены попросить Печкина помочь им в этом. Они предложили ему передавать телеграммы, в которых обменивались "приветствиями". Печкин тут же смекнул, что на этом можно неплохо заработать. Он немедленно заявил, что он готов выполнять поручения, если ему будут платить по 0 < k < 10000 копеек за каждый символ сообщения (в том числе за пробельные символы). Чтобы Печкину было удобнее узнать, от кого (и, соответственно, кому) сообщение, он попросил в начале каждого сообщения от Шарика писать "Sharik: " (без кавычек), а в начале каждого сообщения от Матроскина писать "Matros: " (тоже без кавычек) (обратите внимание, что после двоеточия обязательно следует пробел). Так как Печкин был очень аккуратен и предусмотрителен, он аккуратно переписал все сообщения в свою тетрадку. Теперь ему интересно, сколько денег ему должен Шарик и Матроскин (естественно, каждый платит только за исходящие сообщения). (ПСПC - Простоквашинские Системы Почтовой Связи, тарифный план Простоквоптима^®).

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

В первой строке входных данных записано два целых числа - N - количество сообщений в тетради у Печкина и k. (0 <= N <= 3000). В последующих N строках записаны сами сообщения, длина каждого не превосходит 200 символов.

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

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

Пример

Ввод

2 5
Sharik: Hallo!
Matros: Hi!

Вывод

0.70 0.55

Молоко Матроскина

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

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

Корова Мурка давала такое замечательное молоко, что все в округе с удовольствием его пили. Все мы знаем, что Матроскин предприимчивый кот, поэтому он решил продавать молоко. Но у него появилась небольшая проблема. У Матроскина есть N (1 <= N <= 100) пустых банок, i-тая из которых вмещает ai литров молока. Матроскин очень не любит продавать молоко, поэтому занимается этим редко. Итак, у него накопилось L литров молока (1 <= L <= 100) и он хочет унести все это молоко на рынок. Так как ходить очень далеко, Матроскин хочет унести молоко за один раз. Понятное дело, что никто не будет покупать полупустую банку с молоком, поэтому Матроскин хочет, чтобы все банки были заполнены. Банки у Матроскина стеклянные и достаточно тяжелые, поэтому он хочет не только унести маскимальное количество молока, но и минимизировать количество банок.

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

В первой строке будет записано два числа N, L. Во второй строке записано N натуральных чисел ai не превосходящих 200.

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

Если Матроскин может унести все молоко, то в первой строке выведите число L, в противном случае выведите наибольшее количество молока, которое может унести Матроскин.
Во второй строке выведите минимальное количество банок, которое понадобится Матроскину.

Пример

Ввод

Пример №1
3 5
2 5 3

Пример №2
4 9
1 5 2 5

Вывод

Пример №1
5
1

Пример №2
8
3

Квадрат и точка

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

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

На координатной плоскости нарисован квадрат со сторонами параллельными осям координат. Длина его стороны равна A. Левый нижний угол квадрата совпадает с началом координат. Дана точка с координатами (x, y). Ваша задача определить лежит ли эта точка внутри квадрата, на его стороне или снаружи.

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

В первой строке входного файла записаны три целых числа A, x, y (1 <= A <= 1000; -1000 <= x, y <= 1000).

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

Если точка лежит строго внутри квадрата, выведите 0. Если точка лежит на стороне, то выведите 1. Если точка лежит вне квадрата, то выведите 2.

Пример

Ввод

2 1 1

Вывод

Уравнение

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

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

Дано уравнение вида Ax^2 + Bx + C = 0. Ваша задача найти все его вещественные корни.

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

В первой строке записаны через пробел целые числа A, B и C (-10^5 <= A,B,C <= 10^5). Любой из коэффициентов может обращаться в 0.

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

Если корней бесконечно много выводите INFINITE, иначе в первую строку выходного файла выведите неотрицательное целое число K - количество различных корней уравнения. Далее в K строк запишите все корни в строго возрастающем порядке (кратные корни выводить не следует), значения округляйте к 5-му знаку.

Пример

Ввод

1 -5 6

Вывод

2
2.00000
3.00000

Копирование

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

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

В Берляндский ГУ поступила новая обучающая программа. Её надо скопировать на все N компьютеров. Сейчас она установлена только на первом. Компьютеры не объединены в локальную сеть и не снабжены дисководами. Единственный способ передать информацию с одного компьютера на другой - скопировать её, используя нуль-модем (провод, соединяющий два компьютера напрямую). К компьютеру может быть подключен в один момент времени только один нуль-модем. Таким образом, с любого компьютера, где установлена программа, её можно скопировать на какой-то другой (но только на один) всего за один час. В БерГУ есть всего K нуль-модемных шнуров. Ваша задача по заданным N и K найти наименьшее время, необходимое для копирования программы на все имеющиеся компьютеры.

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

В первой строке записаны через пробел числа N и K (1 <= N <= 10^9, 1 <= K <= 10^9).

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

Выведите единственное число - наименьшее время (в часах), необходимое для копирования новой программы на все компьютеры.

Пример

Ввод

8 3

Вывод

Дробь

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

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

Периодическая десятичная дробь обычно записывается в виде:
[целая_часть,непериодическая_часть(период)]
Любая простая дробь может быть представлена в виде десятичной периодической дроби и наоборот. Например, десятичная дробь 0,2(45) соответствует дроби 27/110. Ваша задача перевести периодическую дробь в обыкновенную.

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

Во входном файле в первой строке содержится периодическая десятичная дробь x (0 < x < 1) в формате, описанном выше. Общее количество цифр в периоде и непериодической части дроби не превосходит 8. Непереодическая часть может отсутствовать, периодическая отсутствовать не может (но может быть равна любому неотрицательному числу).

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

В выходной файл вывести представление дроби x в виде простой дроби p/q, где p и q являются взаимно простыми целыми числами.

Пример

Ввод

0,2(45)

Вывод

27/110

Бумага

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

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

Имеется квадратный лист бумаги. С ним делают два вида действий. Действие a заключается в складывании вдвое листа так, как показано на рисунке 1. Действием b лист складывают, как показано на рисунке 2. Всего над листом делают N (1 <= N <= 50) действий, причем каждое нечетное действие - a, а четное - b. После этого его разрезают так, как показано на рисунке 3. Спрашивается, на сколько несвязных частей K этот лист распадется?