Сложите многоугольник

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

В первой строке входного файла записано целое число n (3 ≤ n ≤ 50), где n - количество отрезков в наборе. Вторая строка содержит длины отрезков - последовательность длины n целых чисел, каждое из которых от 1 до 10⁶ включительно.

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

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

Пример(ы)

input.txt	output.txt
4 1 1 1 100	1

 

input.txt	output.txt
3 1 2 3	-1

Балансировка нагрузки

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Процессоры многопроцессорной системы соединены в цепь последовательно, один за одним. Они пронумерованы целыми числами от 1 до n. Каждый из них содержит некоторый набор заданий на исполнение, i -ый процессор содержит t_i заданий. Система будет сбалансированной, если каждый процессор будет содержать одинаковое количество заданий. Балансировка нагрузки происходит раундами. Каждый раунд каждый процессор может "передать" не более одного задания каждому своему соседу. Соседями процессора i являются процессоры с номерами i -1 и i +1, крайние процессоры имеют лишь по одному соседу. Найдите наименьшее количество раундов, необходимое для балансировки системы.

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

В первой строке входного файла записано целое число n - количество процессоров (1 ≤ n ≤ 5000). Вторая строка содержит последовательность t. Последовательность имеет длину n и содержит целые числа, каждое из которых от 0 до 50000 включительно.

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

Выведите наименьшее количество раундов, необходимое для балансировки системы. Если сумма значений последовательности t не кратна n, то решения не существует. В этом случае выведите -1.

Пример(ы)

input.txt	output.txt
4 0 3 0 1	1

 

input.txt	output.txt
4 2 2 4 4	2

 

input.txt	output.txt
5 3 1 4 1 6	3

Пешеходные зоны против кольцевых

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

В первой строке входного файла содержится целое число n (1 ≤ n ≤ 40), где n - количество дорог в городе. Далее в n строках заданы отрезки парами координат своих концов. Все отрезки имеют положительную длину. Координаты не превосходят 100 по абсолютной величине.

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

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

Пример(ы)

input.txt	output.txt
4 0 0 10 0 10 5 5 5 5 5 5 0 10 0 10 5	5

 

input.txt	output.txt
4 0 3 2 3 1 3 3 3 3 3 3 0 0 3 4 -1	1.41421

 

input.txt	output.txt
2 0 0 6 8 0 0 6 8	10

Кросс-языковая программа

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Напишите программу, которая выведет в выходной файл исходный текст программы, компилирующей как компилятором Borland Pascal 7.0, так и Borland C++ 3.1.

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

Выведите текст искомой программы.