Решения принимаются до 0 часов 1 февраля 2013 г.

Задача Airports

На одной параллели расположено нечетное количество городов. Расстояния от каждого города к двум соседним  попарно различны. Две конкурирующие компании имеют право открыть по N современных аэропортов. В каждом городе можно открыть только один аэропорт. Жители города,  который остался без  аэропорта, будут летать из ближайшего города. Обе компании пытаются выбрать город для строительства таким образом, чтобы жители города без аэропорта, летали именно с него. Компании выбирают города по очереди - сначала выбирает город первая компания, затем вторая компания, потом снова первая и т.д. При правильной стратегии борьбу за пассажиров с последнего города всегда выигрывает первая компания. Если же первая компания ошибется, выбирая город для первой новостройки, выигрышную стратегию реализует вторая компания. Укажите все возможные правильные номера городов для строительства первой компанией первого аэропорта. Города нумеруются слева направо.
Технические условия. Программа Airports читает с клавиатуры целое число 2N +1 - количество городов, (N <298) а дальше - 2N целых чисел не больших 10000 - расстояния между соседними городами слева направо. Программа выводит в порядке возрастания на экран номера городов, выбор которых для первой застройки обеспечивает выигрыш при правильной стратегии первой компании. Все числа разделены пробелами.

Пример
Введение
9 1 2 10 1 2 10 1 2
Вывод
2 5 8
 

Задача Bamboo

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

Технические условия. Программа Bamboo читает с клавиатуры два натуральных числа N (1 <= N <= 150000) и K (1 <= K <= N), а далее N пар целых положительных чисел, на сколько метров вырос тростник за эти сутки и цена одного метра тростника  в тот же день. Все сила разделены пробелами. Программа выводит на экран одно целое неотрицательное число - наибольший возможный доход от продажи тростника. Гарантируется, что результат не превышает 2³¹-1.

 

Задача Bitris

Есть комплект из 2N кубиков. На каждом кубике написано одно натуральное число от 1 до N. Каждое из чисел написано ровно на двух кубиках. Кубики выставлены в одну колонку. Если два кубика с одинаковыми числами оказываются рядом, то они аннигилируют: оба кубики исчезают, а кубики, стоящие за ними, опускаются на освободившееся место. Нужно разобрать столбик - уничтожить все кубики. Для этого разрешается переставлять местами любые два рядом расположенных кубика. Перестановку можно делать только тогда, когда закончатся все возможные в данной ситуации аннигиляции.
Например, если N = 4, а кубики сначала стоят так:

то необходимо выполнить одну перестановку. Кубики с меткой 3 аннигилируют сразу;
 

переставим место четвертый снизу кубик (с меткой 1) и пятый снизу кубик (с меткой 4);
 

после этого аннигилируют последовательно кубики с меткой 4, с меткой 1 и с меткой 2. Можно, конечно, переставить третий и четвертый снизу кубики (в этом случае кубики с меткой 1 и с метка 4 аннигилируют одновременно, а вслед за ними аннигилируют кубики с меткой 2), можно второй и третий. Задача заключается в том, чтобы уничтожить все кубики , выполнив минимальное  количество перестановок. Точнее  - найти наименьшее необходимое для этого количество перестановок.
Технические условия. Программа Bitris читает с клавиатуры натуральное число N (2 ≤ N ≤ 100000), а дальше 2N чисел - метки кубиков от нижнего до верхнего. Все числа разделены одним пробелом. Программа выводит на экран одно целое неотрицательное число M - наименьшее количество перестановок, необходимую для уничтожения всего столба.
Примеры:
 

Задача Pigulia  В государстве  Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой. Дороги пронумеровано целыми числами от 1 до М. Однако в период очередной революции по дорогам стало ездить опасно – революционеры могли и кошелек отобрать… Президент Пигулии решил поехать из столичной резиденции, размещенной а городе 1, в город N с рабочим визитом, но очень боится революционеров. Пигульськая администрация президента определила опасность каждой дороги в виде числа от 0 (безопасная) до 1000  (очень опасная). «Опасность маршрута» - это максимальная из опасностей дорог, входящих в него. Помогите

Пример		Пояснения к примеру.  Здесь есть 2 маршрута из 1 в 3:  1-3 и 1-2-3.  Опасность первого равна 2, второго - 1
Ввод	Вывод
3 3   1 2 1 2 3 1 1 3 2	1

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

Технические условия. Программа Pigulia читает с устройства стандартного ввода (клавиатуры) два числа N и M через пробел (2≤ N≤1000, N-1≤ M ≤100000), а далее М строк по 3 целых числа через пробел А,В – города, соединенные дорогой (1≤ А,В ≤ N), и С –  «опасность» дороги (0≤ С ≤ 1000). Программа  выводит на экран единственное искомое число – «опасность» самого безопасного маршрута.

Задача Point.

Дано N различных точек на плоскости: A₁ (x₁, y₁), A₂ (x₂, y₂), ... , A_n(Х_п,Y_п). Для каждой пары точек A_i и A_j (I <J) посчитаем количество точек А_к таких, что К ≠ I, K ≠ J и А_к лежит на прямой, проходящей через точки A_i і A_j и сложим все эти количества. Что получится в результате?.
Технічні умови. Программа  Point читает целое  число N (1 ≤ N ≤ 1000), а далее в  последующих N строках  по два целых числа - на I-й строке координати точки A_i (X_i, Y_i. Координаты точек - целые числа в пределах от -10⁶ до 10⁶. Все числа в строках разделены пробелами. Программа выводит одно целое число - ответ к задаче.
 

Примеры

Ввод  Вывод
4                    0
0 0
1 0
0 1
1 1
Ввод     Вывод
5                    6
0 0
2 0
0 2
2 2
1 1

Пояснения
На прямых, проходящих через пары точек (0, 0) – (2, 0), (0, 0) – (0, 2), (2, 0) – (2, 2), (0, 2) – (2, 2) не лежит ни одна  точка, кроме этих.
На прямых, проходящих через пары точек (0, 0) – (2, 2), (0, 0) – (1, 1), (2, 0) – (0, 2), (2, 0) – (1, 1) ,(0, 2) – (1, 1), (2, 2) – (1, 1) лежит по одной точке.

Задание подготовили В.Мельник, Г.Непомнящий, Ю.Пасихов, Р.Шпакович