Задача Airports
На одній паралелі розташована непарна кількість міст. Відстані від кожного міста до двох сусідніх - попарно різні. Дві конкуруючі компанії мають право відкрити поN сучасних аеропортів. У кожному місті можна відкрити лише один аеропорт.Жителі міста, яке залишиться без аеропорту, будуть літати з найближчого міста. Обидві компанії намагаються обрати міста для будівництва таким чином, щоб жителі міста, що залишилося без аеропорту, літали
саме з їхнього. Компанії обирають міста по черзі - спочатку обирає місто перша компанія, потім друга компанія, потім знову перша і т.д. При правильній стратегії боротьбу за пасажирів з останнього міста завжди виграє перша компанія. Якщо ж перша компанія помилиться, обираючи місто для першої новобудови, виграшну стратегію реалізує друга компанія. Вкажіть всі можливі правильні номери містдля побудови першою компанією першого аеропорту. Міста нумеруються зліва направо.
Технічні умови. Програма Airports читає з клавіатури ціле число 2N+1 - кількість міст, (N<298) а далі - 2N цілих чисел не більших
за 10000 - відстані між сусідніми містами зліва направо. Програма виводить у порядку зростання на екран номери міст, вибір яких для першої забудови забезпечує виграш при правильній стратегії першій компанії. Всі числа розділено пропусками.
Приклад
Введення
9 1 2 10 1 2 10 1 2
Виведення
2 5 8
© LIKT 1998-2018