Алгоритмы

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

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

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

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество лифтов (\(1 \le n \le 100\)). Следующие \(n\) строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: \(l\), \(u\), \(s\) — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах (\(-100 \le l \le s \le u \le 100\), \(l < u\)), и \(d\) — направление движения лифта в начальный момент (\(d = 1\) означает, что лифт двигается вверх, \(d = -1\) — вниз).

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

В одном феодальном государстве средневековой Европы было \(n\) городов и \(m\) дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.

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

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

Формат входных данных
Первая строка содержит целые числа \(n\) и \(m\) — количество городов и дорог соответственно (\(2 \le n \le 2\,000\), \(1 \le m \le 50\,000\)). Города нумеруются от 1 до \(n\), города S и T имеют номера 1 и \(n\) соответственно.

Следующие \(n\) строк содержат под одному целому числу \(r_i\) — плату за проезд через город \(i\) (\(0 \le r_i \le 10\,000\), \(r_1 = r_n = 0\)).

Следующие \(m\) строк содержат описания дорог. Дорога описывается четырьмя целыми числами: \(a_i\), \(b_i\), \(p_i\) и \(c_i\). Здесь \(a_i\) и \(b_i\) — номера городов, которые соединяет дорога, \(p_i\) — номер города, правителю которого она принадлежит, \(c_i\) — ее стоимость (\(a_i \ne b_i\), \(1 \le c_i \le 10\,000\)). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой.

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

Если решения нет, выведите в выходной файл число \(-1\).

Ребята во дворе решили поиграть в прятки. Чтобы выбрать ведущего, который будет искать, они решили воспользоваться считалкой. Считалка состоит из \(k\) слов, и используется следующим образом.

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

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

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

Помогите им ответить на этот вопрос.

Формат входных данных
Строка содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 10^9\)).

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

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания <<Kozilla>>, в которой вы работаете, планирует разработать новую версию браузера <<Waterrat>> для работы в терминальном режиме, и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, \(j\)-я ячейка \(i\)-й строки имеет ширину \(a_{i,j}\).

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

Формат входных данных
Первая строка содержит \(n\) — количество строк в таблице (\(1 \le n \le 100\)). Следующие \(n\) строк входного файла содержат описание строк таблицы.

Описание каждой строки включает число \(m_i\) — количество ячеек этой строки, и \(m_i\) целых чисел \(a_{i,1}, a_{i,2}, \dots, a_{i,m_i}\) — ширину каждой из ячеек строки (\(1 \le m_i \le 10\), \(1 \le a_{i,j} \le 20\)).

Формат выходных данных
Выведите символическое изображение структуры таблицы.

Изображение \(i\)-й строки таблицы должно начинаться изображением горизонтальной линии, составленным из символов <<+>> (плюс) и <<->> (минус). Затем должна следовать строка, содержащая пробелы и символы <<|>> (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем \(a_{i,1}\) пробелов, затем вертикальная черта, затем \(a_{i,2}\) пробелов, и так далее, всего \(m_i\) блоков пробелов. После последнего блока должна следовать вертикальная черта. После последней строки таблицы также должно следовать изображение горизонтальной линии.

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

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

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

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

Формат входных данных
На первой строке записано целое число \(n\) — количество этапов эксперимента (\(1 \le n \le 100\)).

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

Формат выходных данных
На первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до \(n\) — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

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

Однако все оказалось совсем не так просто. Художник изготовил рамку, поместил в нее картину и понял, что что-то не так. Рамка получилась слишком широкой, и картина выглядела совсем не так ярко, как он ожидал.

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

Поясним подробнее то, как выглядит треугольная рамка. Ее изготовление происходит следующим образом: берется доска из красного дерева, имеющая форму треугольника со сторонами \(a\), \(b\) и \(c\). После этого стороны этого треугольника мысленно сдвигаются внутрь него на расстояние \(d\) (измеряемое по перпендикуляру к соответствующей стороне). На точках пересечения <<сдвинутых>> сторон строится маленький треугольник, который затем вырезается из исходного. Пример рамки со сторонами \(a=6\), \(b=8\), \(c=10\) и шириной \(d=1\) показан на рисунке.

Помогите художнику по имеющимся в прайс-листе данным вычислить площадь рамки.

Формат входных данных
Входные данные содержит четыре целых числа \(a\), \(b\), \(c\), \(d\) (\(1 \le a, b, c, d \le 1000\)) — длины внешних сторон рамки и ее ширину, соответственно. Гарантируется, что треугольник со сторонами \(a\), \(b\) и \(c\) существует, и что в треугольнике есть точка, расстояние от которой до ближайшей стороны строго больше \(d\).

Формат выходных данных
Выведите площадь рамки с точностью не меньше \(10^{-5}\).

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно каждое поле, на котором изображается цифра, состоит из \(w\) ячеек в ширину и \(h\) ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый \(19''\) монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в \(k\) раз и сделать толщину линий равной \(d\). Помогите ему в этом.

Опишем более формально понятие <<увеличить в \(k\) раз>>. Занумеруем ячейки поля \(w \times h\) сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты \((0, 0)\), правая нижняя — \((w - 1, h - 1)\), правая верхняя — \((w - 1, 0)\), левая нижняя — \((0, h - 1)\). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось \(Ox\) направлена вправо, ось \(Oy\) — вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

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

Увеличенная в \(k\) раз цифра рисуется на поле размером \((w - 1) \cdot (k - 1) + w\) ячеек по горизонтали на \((h - 1) \cdot (k - 1) + h\) ячеек по вертикали.

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

После этого, для того, чтобы получить толщину линий равную \(d\), дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем \((d - 1)\) от центров основных ячеек. Расстоянием между точками \(A(x_A, y_A)\) и \(B(x_B, y_B)\) будем называть число \(\rho(A, B) = |x_A - x_B| + |y_A - y_B|\).

По описанию цифры и параметрам \(k\) и \(d\) выведите изображение цифры, увеличенное в \(k\) раз, с толщиной линий \(d\).

Формат входных данных
Первая строка содержит целые числа \(k\) и \(d\) (\(1 \le k \le 100\), \(1 \le d \le 500\)). Вторая строка содержит целые числа \(w\) и \(h\) (\(1 \le w, h \le 10\)).

Третья строка содержит целое число \(n\) (\(1 \le n \le 100\)) — количество отрезков в описании цифры. Далее следуют \(n\) строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(0 \le x_1, x_2 < w\), \(0 \le y_1, y_2 < h\)) — координат концов отрезка.

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

Формат выходных данных
Выходные данные должны содержать ровно \((h - 1) \cdot (k - 1) + h\) строк по \((w - 1) \cdot (k - 1) + w\) символов в каждой, \(j\)-ый символ \(i\)-ой строки должен быть равен символу <<*>> (звездочка), если ячейка с центром в точке \((j,i)\) закрашена, и символу <<.>> (точка) — иначе.

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

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

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

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

Даны восемь символов из диапазона от "A" до "Z". Некоторые из них могут совпадать. Требуется определить, можно ли расположить эти символы в вершинах куба таким образом, чтобы на соседних (т. е. соединенных ребром) вершинах оказались разные символы

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

Выходные данные
Выходной файл должен содержать целое число 1, если расположение возможно, и 0 (нуль) в противном случае.

Выпуклый N-угольник P преобразуется в N-угольник Q путём замены середин сторон исходного многоугольника P на вершины многоугольника Q. Требуется по выпуклому N-угольнику Q, заданному координатами вершин, восстановить координаты вершин исходного N-угольника P.

Входные данные
Входные данные содержит нечётное число вершин N (3 <= N <= 999), за которым следуют целочисленные координаты x_i y_i вершин многоугольника Q, перечисленные в порядке обхода по часовой стрелке. Значения координат находятся в диапазоне от -20000 до 20000. Все числа во входном файле целые и разделены произвольным количеством пробелов и/или символов перевода строки.

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

В саду растут деревья. У каждого есть цена и длина. Чтобы построить забор какой-то длины L, нужно срубить деревьев с суммарной длиной L или больше. Нужно, срубив некоторые деревья, построить забор вокруг оставшихся. При этом нужно потратить как можно меньше денег. Если таких способов несколько, нужно выбрать тот, в котором деревьев рубится меньше. Если и таких несколько, выведите любой. Деревья считаются имеющими нулевой радиус.

Входные данные
Во входном файле записано число деревьев N (2 <= N <= 14), а затем каждое дерево описано четырьмя числами x_i, y_i, v_i, l_i - координаты (целые от -10000 до 10000), цена и длина (от 0 до 10000).

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

Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.

Входные данные
Первая строка содержит натуральное число N (1 <= N <= 50000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел C_i, E_i, P_i (0 < E_i <= Ci < 1000000; E₁+E₂+...+E_N < 2000000000; P_i > 0; P₁+P₂+...+P_N < 2000000000). Этажи нумеруются сверху вниз.

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

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

Города во Флатопии пронумерованы от 1 до N и город с номером i имеет декартовы координаты (x_i, y_i). Каждая дорога соединяет ровно два города. Все дороги (уже построенные и те, которые собираются построить) лежат на прямых линиях и их длина равна декартовому расстоянию между городами. Все дороги имеют двухстороннее движение. Дороги могут пересекаться, но водитель может переезжать с дороги на дорогу только в городах.

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

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

Первая строка входного файла содержит единственное целое число N (1 <= N <= 750), обозначающее число городов. Следующие N строк содержат по два целых числа, x_i и y_i, разделённых пробелом. Эти числа являются координатами соответствующих городов (для i от 1 до N). Координаты по модулю не превосходят 10000. Никакие два города не совпадают.

Следующая строка содержит одно число M (0 <= M <= 1000), представляющее количество уже построенных дорог. Следующие M строк содержат по два целых числа, разделённых пробелом. Эти два числа обозначают пару городов, которые уже соединены дорогами. Каждая пара соединена не более чем одной дорогой.

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

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

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

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

Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.

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

Входные данные
Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).

Выходные данные
Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.

Команда ЛКШ по плаванию состоит из N игроков, известна базовая скорость каждого игрока Vi. В шкафчике находится K магических плавательных костюмов, про которые тренер пустил слух, что они дают бонус к скорости. Костюмы бывают двух типов - спецназовские костюмы с шипами дают процентный бонус, а обычные плавки дают количественный бонус. Мощность воздействия костюма описывается целым числом от 1 до 300. Для спецназовских костюмов оно показывает, на сколько процентов увеличится базовая скорость, а для плавок - на какую величину.

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

Входные данные
В первой строке записано число N (0 <= N <= 400) - число спортсменов, далее N чисел, которые описывают их базовые скорости (целое число от 1 до 10000). Далее записано число K (0 <= K <= 800) - количество костюмов, затем K пар целых чисел, описывающих соответствующую костюмы (тип и мощность). Тип пары описывается либо единичкой (спецназовские костюмы), либо двоечкой (плавки).

Выходные данные
Вывести максимальную суммарную скорость команды с точностью до 4-х знаков.

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

Входные данные
В первой строке записано N - количество комнат (1 < N < 101) и далее номера комнат, в которые переезжают 1,2,3,..,N-я комнаты. СЭС не потерпит беспорядка, поэтому все переезды корректны (в каждую комнату переедет ровно одна комната).

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

В ЛКШ построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход - в комнате N. Каждый ЛКШонок проходит лабиринт ровно один раз и попадает в группу в зависимости от набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

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

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

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

Формат входных данных

Первая строка входного файла содержит натуральное число N (1 <= N <= 500), а во второй строке N чисел - степени вершин.

Формат выходных данных

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

Последовательность чисел монотонно убывающая если для любого i элемента (кроме последнего )выполняется A_i > A_i+1. Последовательность чисел монотонно возрастающая если для любого i элемента (кроме последнего )выполняется A_i < A_i+1. Последовательность монотонная если она или монотонно убывающая или монотонно возрастающая. Дана последовательность A_i из n чисел. Каждый элемент последовательности можно увеличивать или уменьшать. Требуется изменить последовательность так что бы в ней содержалось K монотонных непересекающихся последовательностей. (один элемент тоже последовательность). Т.к. преобразований бесконечно много то нужно найти такое преобразование чтобы сумма разностей по модулю конечного значения A_i и начального значения A_i была минимальна.

Входные данные
В первой строчке n,k n- количество элементов в последовательности, k сколько должно быть монотонных последовательностей. Во второй строчке n чисел через пробел - сама последовательность(каждое число по модулю меньше 20,000,000)

Выходные данные
Одно число, ответ на задачу.

Два участника олимпиады играют в следующую игру. Участники по очереди бросают монетки (одну или больше) в хитрый ящик. Если в ящике находится в точности X₁, или X₂, ..., или X_n монеток, то они, кроме одной, отдаются участнику, сделавшему последний ход. Оставшаяся монетка "исчезает" из игры. Игра заканчивается, если у одного из участников игры не осталось монеток. При этом монетки из ящика (все до одной) отдаются другому участнику(он является победителем игры). Определить наибольшее количество монеток, которое может выиграть первый участник при наилучшей игре второго. Если первый участник не может выиграть, то результатом является число 0.

Входные данные
В первой строке входного файла два числа 0 < S,T <= 50 (число монеток у первого и второго игроков). Во второй строке N (0 <= N <= 50) - число хитрых состояний ящика. В третьей строке целые числа X₁, X₂,..., X_n, 0 < X₁ <= X₂ <= ... <= X_n <= 100.

Выходные данные
Вывести число монеток у первого участника или 0.