Задача A. Столкновение шариков

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

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x1, y1) и (x2, y2) метров, а также проекции скоростей на координатные оси (dx1, dy1) и (dx2, dy2) метров в секунду соответственно.

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

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

Входной файл содержит вещественные числа R x1 y1 dx1 dy1 x2 y2 dx2 dy2.

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

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

Ограничения

1 ≤ R ≤ 1000, 1000 ≤ x1, y1, dx1, dy1, x2, y2, dx2, dy2 ≤ 1000,

(x1 − x2)2 + (y1 − y2)2 > 4 R2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
0 0 10 0
50 0 -10 0
2.4

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

Автор:А. Кленин   Ограничение времени: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

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

Автор:А. Жуплев   Ограничение времени: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 с абсолютной ошибкой не более 103.

Ограничения

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

Задача D. Точка Ферма-Торричелли

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

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

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

Во входном файле содержатся целые числа XA YA XB YB XC YC — координаты точек A, B, C соответственно.

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

Выходной файл должен содержать два числа XO YO — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |XA|, |YA|, |XB|, |YB|, |XC|, |YC| ≤ 105

Никакие две точки не совпадают

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

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

Задача E. Выпуклая оболочка

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

Условие

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению множество, содержащее заданное множество точек X, называется выпуклой оболочкой множества X.

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

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

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

Первая строка входного файла содержит число n — количество углов. Каждая из следующих n строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей.

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

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

На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со- держать описание объектов. Объекты описываются следующим образом:

Если выпуклой оболочкой является вся плоскость, то выведите l = 0.

Ограничения

1 ≤ n ≤ 1000

Все координаты целые и не превышают 104 по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

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

Входной файл (convex.in) Выходной файл (convex.out)
1
2
3 1 4 1 4 4
2 2 4 3 3 4
3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5
2
2
0 0 1 0 0 1
0 0 -1 0 0 1
1
line 1 0 -1 0
3
2
0 0 1 0 0 1
0 0 -1 0 0 -1
0

Problem F. Aerodynamics

Author:NEERC-2008 Jury   Time limit:2 sec
Input file:aerodynamics.in   Memory limit:64 Mb
Output file:aerodynamics.out  

Statement

Bill is working in a secret laboratory. He is developing missiles for national security projects. Bill is the head of the aerodynamics department.

One surprising fact of aerodynamics is called Whitcomb area rule. An object flying at high-subsonic speeds develops local supersonic airflows and the resulting shock waves create the effect called wave drag. Wave drag does not depend on the exact form of the object, but rather on its cross-sectional profile.

Consider a coordinate system with OZ axis pointing in the direction of object's motion. Denote the area of a section of the object by a plane z=z0 as S(z0). Cross-sectional profile of the object is a function S that maps z0 to S(z0). There is a perfect aerodynamic shape called Sears-Haack body. The closer cross-sectional profile of an object to the cross-sectional profile of Sears-Haack body, the less wave drag it introduces. That is an essence of Whitcomb area rule.

Bill's department makes a lot of computer simulations to study missile's aerodynamic properties before it is even built. To approximate missile's cross-sectional profile one takes samples of S(z0) for integer arguments z0 from zmin to zmax.

Your task is to find the area S(z0) for each integer z0 from zmin to zmax, inclusive, given the description of the missile. The description of the missile is given to you as a set of points. The missile is the minimal convex solid containing all the given points. It is guaranteed that there are four points that do not belong to the same plane.

Input file format

The first line of the input file contains three integer numbers: n, zmin and zmax. The following n lines contain three integer numbers each: x, y, and z coordinates of the given points. All coordinates do not exceed 100 by their absolute values. No two points coincide. There are four points that do not belong to the same plane.

Output file format

For each integer z0 from zmin to zmax, inclusive, output one floating point number: the area S(z0). The area must be precise to at least 5 digits after decimal point.

Constraints

4 ≤ n ≤ 100

0 ≤ zmin ≤ zmax ≤ 100

Sample tests

No. Input file (aerodynamics.in) Output file (aerodynamics.out)
1
9 0 5
0 0 5
-3 0 2
0 -1 2
3 0 2
0 1 2
2 2 0
2 -2 0
-2 -2 0
-2 2 0
16.00000
14.92000
10.08000
4.48000
1.12000
0.00000

Задача G. Водовод на о. Русский

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

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

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

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида ri, ci, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5
...##
##...
.####
...#.
YES
6  2 1  2 2  3 2  3 3  3 4  3 5 
2
3 6
#.###.
###.##
......
MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
3
3 6
..###.
###.##
..###.
MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6
4
3 3
...
.##
...
NO

Problem H. Breadth First Search

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 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. Vertices are numbered with integer numbers from 1 to N. M is the number of edges, S is the starting vertice. Each of next M lines contain 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 must contain 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

Задача I. Лабиринт

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

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

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

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

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

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

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

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

Задача J. Производство деталей

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

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

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

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

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

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2… pn, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

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

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ pi ≤ 109

Сумма всех чисел ki не превосходит 200000.

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

Входной файл (details.in) Выходной файл (details.out)
1
3
100 200 300
1 2
0
2 2 1
300 2
2 1
2
2
2 3
1 2
0
5 2
2 1
3
4
2 3 4 5
2 3 2
1 3
0
2 1 3
9 3
3 2 1

Задача K. КПК

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

Условие

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

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

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

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел ai aj, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

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

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

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

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

Автор:Московская олимпиада для 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

Задача M. Модули

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

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

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

Problem N. Ford-Bellman

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 finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Problem O. Hot-keys

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&abc
&bca
a&cb
aaaa

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

Автор: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

Задача Q. Min-cost-max-flow aka В поисках невест

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

Условие

Однажды король Флатландии решил отправить k своих сыновей на поиски невест. Всем известно, что во Флатландии n городов, некоторые из которых соединены дорогами. Король живет в столице, которая имеет номер 1, а город с номером n знаменит своими невестами.

Итак, король повелел, чтобы каждый из его сыновей добрался по дорогам из города 1 в город n. Поскольку, несмотря на обилие невест в городе n, красивых среди них не так много, сыновья опасаются друг друга. Поэтому они хотят добраться до цели таким образом, чтобы никакие два сына не проходили по одной и той же дороге (даже в разное время). Так как король любит своих сыновей, он хочет, чтобы среднее время сына в пути до города назначения было минимально.

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

В первой строке входного файла находятся числа n, m и k — количество городов и дорог во Флатландии и сыновей короля, соответственно (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100). Следующие m строк содержат по три целых положительных числа каждая — города, которые соединяет соответствующая дорога и время, которое требуется для ее прохождения (время не превышает 106). По дороге можно перемещаться в любом из двух направлений, два города могут быть соединены несколькими дорогами.

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

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

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

Входной файл (brides.in) Выходной файл (brides.out)
1
5 8 2
1 2 1
1 3 1
1 4 3
2 5 5
2 3 1
3 5 1
3 4 1
5 4 1
3.00000
3 1 5 6
3 2 7 8

Задача R. Быстрое двудольное паросочетание

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

Условие

Напишите программу для нахождения максимального двудольного паросочетания.

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

Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.

Далее содержится описание m ребер в виде списка пар целых чисел (ui, vi). Наличие пары (ui, vi) означает ребро между ui-ой вершиной левой доли и vi-ой вершиной правой доли.

Гарантируется, кратных рёбер в графе нет.

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

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

Ограничения

1 ≤ p, q ≤ 105

1 ≤ m ≤ 2*105

1 ≤ ui ≤ p

1 ≤ vi ≤ q

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

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

Problem S. Dijkstra

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

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem T. Fast Dijkstra

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 weighted directed graph and finds all distances from fixed vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Задача U. Перетягивание канатов

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

Условие

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

Дети обратились к самому умному ученику в классе, Васе, с просьбой поделить их на две команды и выбрать судью.

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 30.

0 ≤ ai ≤ 107.

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

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

Задача V. Свинья-копилка

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

Условие

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

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

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.

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

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

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

Задача W. Благотворительность Марфы Геннадьевны

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

Условие

Однажды Марфа Геннадьевна выиграла в лотерею большую сумму денег и решила потратить часть выигрыша на благотворительность.

Чтобы определить, сколько денег отдать на благотворительность, Марфа Геннадьевна придумала игру. Она записала N чисел a1, a2, ..., aN по кругу (по часовой стрелке).

Начинает Марфа Геннадьевна с числа a1. Начальная сумма денег равняется a1. Затем Марфа Геннадьевна кидает игральный кубик (на разных гранях кубика нарисовано 1, 2, 3, 4, 5 и 6 точек). Если на кубике выпало число x, то Марфа Геннадьевна отсчитывает x чисел по часовой стрелке. Например, если выпало число 3, то Марфа Геннадьевна перейдёт от числа a1 к числу a4. Число, к которому перешла Марфа Геннадьевна, прибавляется к сумме. Марфа Геннадьевна бросает кубик M раз и каждый раз прибавляет очередное число к сумме.

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

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

Входной файл содержит целые числа N M, за которыми следуют N целых чисел a1 a2... aN.

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

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

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ 5000

0 ≤ ai ≤ 1000

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

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

Задача X. Благотворительность Марфы Геннадьевны - 2

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

Условие

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

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

Марфа Геннадьевна бросает N игральных кубиков и подсчитывает сумму очков, выпавших на кубиках. Затем она умножает сумму очков на некоторый коэффициент — это и будет сумма пожертвования.

На каждом кубике с одинаковыми вероятностями выпадает одно из чисел от 1 до 6.

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

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

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

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

Требуется вывести в выходной файл (5 N + 1) пар чисел — для каждого возможного значения суммы очков от N до 6 N нужно вывести это значение и вероятность того, что сумма очков примет такое значение.

Вероятности вывести с точностью до 10-ти знаков после запятой.

Ограничения

1 ≤ N ≤ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1 0.1666666667
2 0.1666666667
3 0.1666666667
4 0.1666666667
5 0.1666666667
6 0.1666666667
2
2
2 0.0277777778
3 0.0555555556
4 0.0833333333
5 0.1111111111
6 0.1388888889
7 0.1666666667
8 0.1388888889
9 0.1111111111
10 0.0833333333
11 0.0555555556
12 0.0277777778

Задача Y. Методом тряпки

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

Условие

Школьники плохо написали контрольную работу по признакам делимости на k. Марфа Геннадьевна оставила их после уроков для работы над ошибками. Она написала на доске большое число N и сама на секунду задумалась. А делится ли её число на k?

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

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

В первом примере необходимо стереть цифры 7 и 6. Если стереть цифры 1, 4, 6, то полученное число 7 будет делиться на 7, но этот ответ не оптимален.

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

В третьем примере ничего нельзя поделать.

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

Рекомендуется рассмотреть следующие частные случаи:

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

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

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

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

Ограничения

1 ≤ k ≤ 1000;

1 ≤ N ≤ 101000;

в записи числа N нет лидирующий нулей;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1746
14
2
3
106
6
3
10
256
IMPOSSIBLE

0.289s 0.004s 67