Розв'язки приймаються до 0 годин 1.02.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 пар цілих додатних чисел, на скільки метрів виріс очерет за певну добу і ціна одного метра очерету того ж дня. Всі числа розділені пропусками. Програма виводить на екран одне ціле невід’ємне число – найбільший можливий прибуток від продажу очерету. Гарантується, що результат не перевищує 231-1.
Приклади:
|
Введення |
Виведення |
Пояснення |
|
3 2 1 2 3 1 5 3 |
26 |
26=1*2+3*3+5*3 |
|
7 3 6 2 2 1 5 3 4 5 7 2 1 4 4 1 |
109 |
109=6*3+2*5+5*5+4*5+7*4+1*4+4*1 |
Задача Bitris
Є комплект із 2N кубиків. На кожному кубику написано одне натуральне число від 1 до N. Кожне із чисел написано рівно на двох кубиках. Кубики виставлені в одну колонку. Якщо два кубика з однаковими числами опиняються поруч, то вони анігілюють: обидва кубики зникають, а кубики, які стоять над ними, опускаються на звільнене місце. Потрібно розібрати стовпчик – знищити усі кубики. Для цього дозволяється переставляти місцями будь-які два поруч розташованих кубика. Перестановку можна робити тільки тоді, коли закінчаться всі можливі в даній ситуації анігіляції.
Наприклад, якщо N=4, а кубики спочатку стоять так:
|
2 |
|
4 |
|
1 |
|
3 |
|
3 |
|
4 |
|
1 |
|
2 |
то необхідно виконати одну перестановку. Кубики з міткою 3 анігілюють одразу;
|
2 |
|
4 |
|
1 |
|
4 |
|
1 |
|
2 |
переставимо місцями четвертий знизу кубик (з міткою 1) і п’ятий знизу кубик (з міткою 4);
|
2 |
|
1 |
|
4 |
|
4 |
|
1 |
|
2 |
після цього анігілюють послідовно кубики з міткою 4, з міткою 1 і з міткою 2. Можна, звичайно, переставити третій і четвертий знизу кубики (в цьому випадку кубики з міткою 1 і з міткою 4 анігілюють одночасно, а вслід за ними анігілюють кубики з міткою 2), можна другий і третій.Задача полягає в тому, щоб знищити усі кубики, виконавши найменш можливу кількість перестановок. Точніше, знайти найменшу необхідну для цього кількість перестановок.
Технічні умови. Програма Bitris читає з клавіатури натуральне число N (2≤N≤100000), а далі 2N чисел - мітки кубиків від нижнього до верхнього. Всі числа розділені одним пробілом. Програма виводить на екран одне ціле невід’ємне число M – найменшу кількість перестановок, необхідну для знищення усього стовпчика.
Приклади:
|
Введення |
Виведення |
|
4 2 1 4 3 3 1 4 2 |
1 |
|
3 1 3 2 1 3 2 |
3 |
|
3 1 3 2 2 3 1 |
0 |
Задача Pigulia У державі Пигулії є N міст, деякі з них сполучені двосторонніми дорогами. Проїхати можна з будь-якого міста в будь-яке. Дороги пронумеровано цілими числами від 1 до М. Але у період чергової революції по дорогам стало їздити небезпечно – революціонери могли і гаманець відібрати… Президент Пигулії вирішив поїхати із столичної резиденції, що в місті 1 до міста N з робочим візитом, але дуже боїться революціонерів. Пигульська адміністрація президента визначила небезпеку кожної дороги у вигляді числа від 0 (безпечна) до 1000 (дуже небезпечна). «Небезпека маршруту» - це максимальна з небезпек доріг, що до нього входять. Допоможіть а
|
Приклад |
|
|
|||||||||||
|
Введення |
Виведення |
||||||||||||
|
1
|
дміністрації обрати самий безпечний маршрут для президента (тобто такий, небезпека якого мінімально можлива). Будь які два міста можуть бути з’єднані кількома дорогами.
Технічні умови. Програма Pigulia читає з пристрою стандартного введення (клавіатури) два числа N та M через пропуск (2≤ N≤1000, N-1≤ M ≤100000 ), а далі М рядків по 3 цілих числа через пропуск А,В – міста, що їх сполучає дорога (1≤ А,В ≤ N), та С – «небезпеку» дороги (0≤ С ≤ 1000). Програма виводить на екран єдине шукане число – «небезпеку» самого безпечного маршруту.
Задача Point.
Дано N різних точок на площині: A1 (x1, y1), A2 (x2, y2), ... (Хп,Yп). Для кожної пари точок Ai і Aj (I <J). Порахуємо кількість точок Ак таких, що К ≠ I, K ≠ J і Ак лежить на прямій, що проходить через точки Ai і Aj і складемо всі ці кількості. Що вийде в результаті?.
Технічні умови. Програма Point читає ціле число N (1 ≤ N ≤ 1000),а далі в наступних N рядках по два цілих числа - на I-му рядку координати точки Ai (Xi, Yi). Координати точок - цілі числа в межах від -106 до 106. Всі числа у рядках розділені пропусками. Програма виводить одне ціле число - відповідь до задачі.
Приклади
Введення Виведення
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) лежить по одній точці.
-------------------------------------------------------
Завдання підготували В.Мельник, Г.Непомнящий, Ю.Пасіхов, Р.Шпакoвич