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