Задача 1. О сети (5 сек.)

В сети 2 <= N <= 15 компьютеров, некоторые соединены попарно между собой проводом. Максимальная пропускная способность провода между двумя связанными компьютерами измеряется натуральным числом, не превосходящим 100. Пропускная способность провода в обоих направлениях совпадает. Два компьютера соединены не более чем одним проводом. Компьютер может одновременно обмениваться информацией со всеми компьютерами, связанными с ним. Требуется вычислить максимальную пропускную способность канала между компьютерами с номерами 1 и N.

Формат ввода.

В первой строке входного файла input.txt задано N - количество компьютеров и M - количество проводов связи. В каждой из последующих M строк заданы тройки чисел - номера связанных компьютеров и пропускная способность провода.

Формат вывода.

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

Пример 1.

Пример 2.

Задача 2. Границы (1 сек.)

Даны два прямоугольника на плоскости, со сторонами параллельными осям координат и заданные координатами своих левых верхних и правых нижних вершин. Ось OX направлена вправо, ось OY - вниз. Ваша программа должна вывести контур фигуры, полученной при объединении прямоугольников, если они пересекаются (т.е. имеют хотя бы одну общую точку).

Формат ввода.

Файл input.txt состоит из четырех строк, содержащих пары целых координат X и Y,
-40000 <= X, Y <= 40000. В первой строке - координаты левого верхнего угла первого прямоугольника. Во второй строке - координаты правого нижнего угла первого прямоугольника. В третьей строке - координаты левого верхнего угла второго прямоугольника. В четвертой строке - координаты правого нижнего угла второго прямоугольника.

Формат вывода.

В файл output.txt вывести вершины ломаной, задающей контур. Вершины перечисляются в порядке обхода по часовой стрелке, начиная с самой левой из верхних вершин. Каждая пара координат выводится с новой строки. Первую точку ломаной в конце выходного файла выводить не надо. Если прямоугольники не пересекаются, то выводится строка "No solution".

Пример.

Задача 3. Об удачливом игроке (5 сек.)

Казино "Your Lucky Day" в пригороде Лас-Вегаса решило провести конкурс на самого удачливого игрока. Игрок, у которого в течение дня сумма выигрыша за несколько подряд идущих игр оказалась наибольшей, объявляется победителем и награждается бесплатным ужином в подведомственном ресторане казино. Если игрок ни разу не выигрывал, его выигрышем считается минимальный проигрыш. Следуя 27-й поправке к конституции, казино запрещает за один раз выигрывать или проигрывать более 10000 долларов.

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

Формат ввода.

Во входном файле input.txt перечислены результаты игроков. В первой строке задано число M (1 <= M <= 32000) - количество игроков. Далее в строках расположены следующие данные об игроках: имя игрока (не более 32 символов, в именах игроков используются только символы латинского алфавита), на отдельной строке число N - количество сеансов игры этого игрока (1 <= N <= 10000) и N чисел, разделенных пробелом или переводом строки, - результаты игр. Положительные числа означают выигрыши, отрицательные - проигрыши.

Суммарное количество всех игр всех игроков не превышает 100000. Ответ никогда не превысит 1000000.

Формат вывода.

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

Пример.

Задача 4. Сбой в системе (5 сек.)

При обработке текста произошел сбой в системе "Die Fensteren", в результате чего все его символы изменились. Дело в том, что каждый символ представлялся кодом ABCD таблицы: перевод строки был нулевым символом, пробел первым, а дальше по порядку знаки ':', ';', '?', '!', ',', '.', '-', '/', ''', '(', ')', потом цифры от 0 до 9, буквы от A до Z, от a до z. Всего 75 символов. Итак, код каждого символа изменился, "сдвинувшись" на какое-то постоянное для всех количество шагов. То есть, если оно равно 2, символ 'A' "перешел" в символ 'C', символ 'C' в 'E', символ с кодом 74 в символ с кодом 1 и т.д. Необходимо узнать на сколько сместились символы в таблице и выдать исходный текст.

Кто-то вспомнил, что это был обычный текст. Все предложения начинаются с большой буквы. После знаков препинания (',','?','...', '?!' и т.д.) обязательно стоит пробел. Только после последнего предложения может не быть пробела или знака препинания (например, если последнее предложение - подпись). Учтите, что символ "-" может встречаться и внутри слов, и в виде знака препинания, тогда вокруг него должны стоять пробелы. Скобки расставлены корректно : после открывающей и перед закрывающей пробелов нет, после закрывающей обязательно стоит пробел или знак препинания. Символ `'` может встречаться внутри слова или выполнять роль кавычек. Причем все кавычки должны быть закрыты, вложенные не допускаются. Перевод строки может стоять там, где должен стоять пробел.

Формат ввода.

Входной файл input.txt содержит зашифрованный английский текст (не более 5000 символов).

Формат вывода.

Выходной файл output.txt содержит искомый текст. Предполагается, что решение находится однозначно.

Пример.

Задача 5. Задача о свинье (20 сек)

В стране Свинлэнд жил-был фермер. У него был огород. Соседская свинья часто топтала на нем грядки. Она была очень умная, поэтому делала это, руководствуясь следующими правилами:

1. не топтать одну и ту же грядку два раза (по ее мнению это не рационально);
2. затоптать все грядки;
3. как можно меньше поворачиваться (из-за особенностей строения свиньи при таком весе вперед бежать проще, чем налево или направо);
4. через стенки не прыгать (а также не пробивать их и не делать подкопы);
5. заходить на огород только со входа, выходить только через выход (огород обнесен стеной, см. пункт 4).

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

Огород имеет квадратную форму размером 6 на 6 грядок. Размеры свиньи, входа и выхода совпадают с размерами одной грядки. Длина стенки равна длине одной грядки.

Совместим начало координат с одним из углов огорода так, чтобы грядки имели неотрицательные координаты в этой системе, а ось OX совпадала с той стороной огорода, где расположены вход и выход. Тогда X-тая координата выхода будет на 1 меньше X-той координаты входа, а Y-координаты выхода и входа будут равны 0.

Формат ввода.

Во входном файле input.txt заданы 4 целых положительных числа: первое число задает X-тую координату входа. Следующие три числа описывают положение стены: два числа задают координаты грядки, на границе которой стоит стенка и третье N - эту границу (0 - верхняя; 1 - правая; 2 - нижняя; 3 - левая). Стенка не может закрывать вход или выход.

Формат вывода.

Выходной файл output.txt должен содержать одно целое число P - минимальное количество поворотов или строчку "No", если обход не возможен.

Пример.

Схема к примеру:

Задача 6. Привал (5 сек.)

Школьники пошли в поход, взяв с собой запасы провизии, упакованные в ящики. Во время привала пошёл дождь, и ящики пришлось закрывать тентом. Всё бы хорошо, но края ящиков оказались острыми и допустимо лишь касание тентом краёв. Малейшее натяжение (см. рис) прорвёт тент, и школьники останутся без ужина.

I-й ящик (0 < i <= 1000) задаётся координатой на прямой xi (0 <= xi <= 32000), шириной si и высотой hi, (0 < si, hi <= 1000). Ящики прямоугольные, стоят на земле, не накладываются друг на друга. Тент удерживается вертикальными колышками. J-й колышек (0 < j <= 1000) задается высотой Hj (от земли) и координатой Xj по оси абсцисс (0 <= Xj, Hj <= 32000).

Формат ввода.

В первой строке входного файла input.txt указывается количество ящиков N. Следующие N строк описывают положение и размеры ящиков (координата левого края, ширина и высота). В следующей строке задано число М - количество колышков, а затем в M строках их описания (координата и высота от земли). Координаты колышков отсортированы по возрастанию, координаты ящиков задаются в произвольном порядке.

Формат вывода.

Файл output.txt содержит одно число - количество промоченных ящиков.

Задача 7. Хомячки (3 сек.)

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

Формат ввода.

В первой и второй строках входного файла input.txt содержатся положительные целые числа, над которыми нужно произвести операции сложения и вычитания. Ограничение: количество десятичных разрядов - M, 0 <= M <= 255

Формат вывода.

Выходной файл output.txt должен содержать два числа без ведущих нулей (то есть без нулей в начале). В первой строке - результат сложения входных чисел, а во второй - результат вычитания второго входного числа из первого.

Пример.