Рассмотрим цепочку, состоящую из N колец. Какое минимальное количество колец необходимо расцепить, чтобы из оставшихся кусков можно было собрать цепочки любой длины от 1 до N колец? При создании новых цепочек можно использовать расцепленные кольца.

Например, при N=21, достаточно расцепить всего 2 кольца таким образом, чтобы получились куски длинной 3, 5 и 11. Два расцепленных кольца считаются кусками единичной длины.

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

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

Единственная строка входного файла содержит одно целое число N (1≤N≤10⁹).

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

Единственная строка выходного файла должна содержать одно целое число – найденное минимальное количество колец.

24

3

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

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

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

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

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

Первая строка входного файла содержит целое число N (2≤N≤1000) – количество деревьев в саду. Каждая i-ая из последующих N-1-ой строк содержит N-i чисел, которые последовательно представляют длины тропинок между i-ым деревом и деревьями с i+1-го до N-го. Все числа целые, неотрицательные, и не превышают 10⁶.

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

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

3
10 12
13

10

Город Прямой Рог представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы.

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

Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.

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

Первая строка входного файла содержит целое число N (1≤N≤100 000) – количество заказов. Далее следует N строк, каждая из которых содержит одно целое число – расстояние от офиса до адресата. Если расстояние положительное – то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 10⁸.

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

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

10
-2
-8
16
-12
-11
19
18
1
-5
-20

65

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

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

Например, на рисунке изображена прямая, которая задает некоторое разделение многоугольников. Оценка дефекта этого разделения (два случая соответствия): (D)+(C+E) и (A+D)+(B+C). Из рисунка, D+C+E меньше, соответственно, в целом, оценка дефекта разделения порожденного этой прямой есть D+C+E.

Напишите программу, которая по заданным двум многоугольником находит прямую, которая образует разделение наименьшего дефекта.

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

Первая строка входного файла содержит одно целое число N (3≤N≤20) – количество вершин первого многоугольника. Последующие N строк содержат пары целых чисел – координаты вершин первого многоугольника в порядке обхода. (N+2)-ая строка файла содержит число M (3≤M≤20) – количество вершин второго многоугольника. Последующие M строк содержат его координаты заданные таким же образом, как и для первого многоугольника. Координаты точек положительны и не превышают 1000.

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

Единственная строка выходного файла должна содержать две пары чисел – координат двух точек, которые однозначно задают разделение (прямую) с наименьшим дефектом. Числа требуется выводить в порядке: x₁ y₁ x₂ y₂. Координаты требуется выводить с точностью 10^-3. Координаты точек должны быть положительны и не превышают 1000.

Пример

В королевстве Олимпия живут N мудрецов, которые имеют совершенные интеллектуальные способности. Для поддержания творческого настроя среди интеллектуальной элиты королевства король ввел такую традицию.

Каждый вечер M колпаков раскрашиваются в один из K разных цветов. Таким образом, M_i колпаков раскрашены в i-й цвет (i=1..K). Мудрецам эти данные известны. Пока мудрецы спят, каждому из них на голову цепляют один из колпаков, а оставшиеся прячут. Когда мудрецы просыпаются, они садятся в круг, так чтобы каждый из них видел колпаки всех остальных, и начинают думать о цвете своего колпака. Это выглядит таким образом. Каждый мудрец пишет на листочке, знает ли он цвет своего колпака. После этого все демонстрируют свои листочки. Если кто-то написал, что знает цвет – процедура заканчивается, и все идут на завтрак. Если никто не смог определить цвет, то мудрецы начинают думать снова, операция с листочками повторяется.

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

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

Первая строка входного файла содержит целые числа N (1≤N≤10⁶) – количество мудрецов, M (N≤M≤10⁶) – количество колпаков, и K (1≤K≤10⁶) – количество разных цветов. Вторая строка содержит K целых чисел, каждое из которых задает количество колпаков определенного цвета. Третья строка состоит из N целых чисел, которые представляют цвета колпаков каждого из мудрецов. Цвета пронумерованы от 1 до K.

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

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

3 5 2
3 2
1 1 1

1 2 3
3