Алгоритмы

В саду растут деревья. У каждого есть цена и длина. Чтобы построить забор какой-то длины 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 холлов, некоторые из которых соединены коридорами, причем, если по коридору можно пройти в одну сторону, это вовсе не означает, что можно пройти и в другую. Это фишка архитекторов.

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

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

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

Входные данные
В первой строке входного файла четыре числа: N, S, V1, V2 (1 <= N <= 1000; 1 <= S, V1, V2 <= N), где N - общее количество холлов, S - номер холла, в котором Петя находится в начальный момент времени, V1, V2 - номера холлов, в которых располагаются умывальники. В следующих N строках по N чисел - 1 или 0. Стоящий в I-ой строке на J-ом месте 0 означает отсутствие коридора из I-го холла в J-ый, а стоящая 1 - присутствие.

Выходные данные
Вывести 1, если Петя сможет получить меньше нарядов вне очереди при использовании первого умывальника, нежели при использовании второго, или 0 в противном случае.

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

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

Первая строка входного файла содержит натуральное число 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.

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

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

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

Наверняка все слышали про карточную игру "Покер". В джентльменском покере все, как и в обычном - игроки сидят за круглым столом, ставят ставки, повышают их, и кто-то в конце каждого раунда забирает выигрыш - банк. Только в джентльменском покере выигрыш раунда достается не одному игроку, а делится на K человек (K - степень щедрости). А точнее, банк делится поровну между победителем раунда и следующими K-1 игроками, сидящими за выигравшим (за последним сидит первый игрок). В случае, если сумма выигранного банка не делится поровну между K игроками, то излишек забирает победитель. Так, например, если играют 4 человека и степень щедрости равна 3, то при выигрыше первого игрока банк поделится между 1-ым, 2-ым и 3-им игроками, а при победе четвертого - между 4-ым, 1-ым и 2-ым. Ваша задача по протоколу игры сосчитать, сколько денег у каждого из игроков оказалось в конце игры. Т.к. покер джентльменский, то разрешается играть в долг.

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

В первой строке содержатся три положительных целых числа: N, K и S, где N - число игроков (игроки пронумерованы от 1 до N по направлению хода игры), K - степень щедрости и S - начальная сумма денег у каждого игрока, 2 <= N <= 30000, 1 <= K <= N, S <= 10500. Гарантируется, что долг игрока будет не менее, чем -2¹⁵-1 и выигрыш не более, чем 2¹⁵. Далее идут строки, описывающие протокол игры. Протокол игры состоит не более, чем из 2¹⁰ событий. Возможные строки протокола игры:
BET A B - игрок под номером А добавляет в банк сумму B. В начале каждого раунда банк пуст.
WIN A - означает конец раунда и игрок под номером А забирает банк и делит его со следующими K-1 игроками.
END - означает конец игры. Данная строка является последней во входном файле.

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

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

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

Формат входных данных:
В первой строке дано число 0 <= N <= 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < x_i, y_i < 10⁶ - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

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

Примечание

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все n своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке a[1], a[2],...,a[n]. Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами i[1], i[2],..., i[k] покрашены в один цвет, то a[i[1]] < a[i[2]] < ... < a[i[k]]. Петя хочет использовать как можно меньше цветов. Помогите ему!

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

Первая строка входного файла содержит число n - количество кубиков у Пети (1 <= n <= 250000). Затем следует n чисел, разделенных пробелами и/или переводами строки - a[1], a[2], ..., a[n].

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

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

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.

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

В первой строке через пробел заданы два целых числа M и N (1 <= N < M <= 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 <= L, H <= 101). Ступеньки нумеруются снизу вверх.

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

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

То же, что и Дровосек - 1, только граф произвольный, после хода выживают те компоненты связности, которые содержат корни (изначально в каждой компоненте связности есть хотя бы один корень).

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

В первой строке задаются 3 числа - количество вершин 1 < N <= 10000, число ребер 0 <= M <= 100000 и количество корней 1 <= R <= N. В следующей строке идут различные числа 1 <= R_i <= N - номера вершин, являющихся корнями. В следующих M строках идут пары чисел - описания ребер.

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

Выведите одно число -  номер игрока-победителя.

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

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

В первой строке вводится 2 числа - количество вершин 1 < N <= 100000 и номер корня 1 <= R <= N. В следующих N-1 строках идут пары чисел - описания ребер.

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

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

Входные данные
Вводятся 5 чисел: a, b, c, d и e.

Выходные данные
Найдите все целые решения уравнения ( ax³ + bx² + cx + d ) / ( x - e ) = 0 на отрезке [0,1000] и выведите их количество.

Входные данные
Вводятся 4 числа: a, b, c и d.

Выходные данные
Найдите все целые решения уравнения ax³ + bx² + cx + d = 0 на отрезке [0,1000] и выведите их в порядке убывания. Если на данном отрезке нет ни одного решения, то ничего выводить не нужно.