XX Всеукраїнська олімпіада з інформатики

Перший тур

І знову ланцюг

Є ланцюг, що складається з N кілець. Яку мінімальну кількість кілець потрібно розчепити, щоб зі шматків, що  залишилися, можна було б зібрати ланцюг будь-якої довжини від 1 до N кілець? При утворенні нових ланцюгів можна використовувати кільця, які було розчеплено.

Наприклад, при N=21, достатньо розчепити всього 2 кільця таким чином, щоб утворилися шматки довжиною 3, 5 та 11. Два кільця, які було розчеплено вважаються за шматки одиничної довжини.

Завдання

Напишіть програму CHAIN, що за натуральним N – довжиною вихідного ланцюга, знаходить мінімальну кількість кілець, які необхідно розчепити задля досягнення описаної цілі.

Вхідні дані

Єдиний рядок вхідного файлу CHAIN.DAT містить одне ціле число N (1≤N≤10⁹).

Вихідні дані

Єдиний рядок вихідного файлу CHAIN.SOL має містити одне ціле число – знайдену мінімальну кількість кілець.

Приклад вхідних та вихідних даних

Дерева у саду

Центральний сад країни Олімпія настільки великий, що один садівник не в змозі його обслуговувати. Було прийнято рішення розділити сад на дві частини. Певні дерева буде віднесено до першої частини, а решта – до другої. Одна з частин саду може залишитися порожньою.

                Між кожною парою дерев у саду протоптані стежки. Коли садівники ідуть від дерева до дерева вони обов’язково ідуть стежкою, що з’єднує безпосередньо ці два дерева. Довжина стежки однакова при переміщенні в обидва боки.

Для спрощення роботи садівникам, розділення вирішили провести так, щоб довжина найдовшої стежки між парою дерев, що належать до однієї і тієї ж самої частини, була мінімальна.

Завдання

Напишіть програму TREES, що за інформацією про довжини стежок між усіма парами дерев знаходить довжину найдовшої стежки між деревами з однієї частини саду, при оптимальному розділенні саду на частини.

Вхідні дані

Перший рядок вхідного файлу TREES.DAT містить ціле число N (2≤N≤1000) – кількість дерев у саду. Кожен i-ий з наступних N-1-го рядків містить N-i чисел, які послідовно представляють довжини стежок між i-им деревом і деревами з i+1-го до N-го. Всі числа цілі, невід’ємні, та не перевищують 10⁶.

Вихідні дані

Єдиний рядок вихідного файлу TREES.SOL має містити одне ціле число – мінімальну для всіх можливих розбиттів саду довжину найдовшої стежки між деревами в одній з частин саду.

Приклад вхідних та вихідних даних

Доставка

Місто Прямий Ріг являє собою одну пряму вулицю. У місті працює компанія, що займається доставкою товарів. Для зручності, адреси доставки надані у вигляді чисел, що задають відстань від офісу компанії. Додатні числа в один бік, а від’ємні – в інший. Замовлення на доставку виконуються компанією послідовно, у тому порядку, в якому вони були задані.

В компанії працює два кур’єра. На початку робочого дня замовлення розподіляються між ними, і кожен вирушає за своїм маршрутом. Компанії необхідно так спланувати розподілення замовлень, щоб сумарна відстань, яка буде пройдена кур’єрами на момент виконання останнього замовлення, була мінімальною.

Завдання

Напишіть програму ORDER, що за відстанями адресатів від офісу компанії знаходить найменшу сумарну відстань, що пройдуть її робітники.

Вхідні дані

Перший рядок вхідного файлу ORDER.DAT містить ціле число N (1≤N≤100 000) – кількість замовлень. Далі слідує N рядків, кожен з яких містить єдине ціле число – відстань від офісу до адресата. Якщо відстань додатня – то адресат знаходиться у одній частині міста відносно офісу компанії, а якщо від’ємна, то у іншій. Відстані за модулем не перевищують 10⁸.

Вихідні дані

Єдиний рядок вихідного файлу ORDER.SOL має містити одне ціле число, яке є мінімальною можливою сумарною відстанню, що пройдуть обидва робітники компанії.

Приклад вхідних та вихідних даних

XX Всеукраїнська олімпіада з інформатики

Другий тур

Розділення багатокутників

На площині задано дві фігури, що обмежені опуклими багатокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно 2 точки перетину.

Довільним чином розділимо площину прямою. Будемо вважати, що півплощина з одного боку прямої відповідає першій фігурі, а з іншого боку – другій фігурі. Визначимо поняття дефекту розділення – сума площі першої фігури, що розташована на півплощині другої фігури, та площі другої фігури, що розташована на півплощині першої фігури. З двох можливих відповідностей півплощин до фігур оберемо таку відповідність, де значення дефекту менше.

Наприклад, на рисунку зображена пряма, що задає певне розділення багатокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D)+(C+E) та (A+D)+(B+C). З рисунку, D+C+E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D+C+E.

Завдання

Напишіть програму DIVIDE, що за заданими двома багатокутниками знаходить пряму, що утворює розділення з найменшим дефектом.

Вхідні дані

Перший рядок вхідного файлу DIVIDE.DAT містить одне ціле число N (3≤N≤20) – кількість вершин першого багатокутника. Наступні N рядків містять пари цілих чисел – координати вершин першого багатокутника у порядку обходу. (N+2)-й рядок файлу містить число M (3≤M≤20) – кількість вершин другого багатокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого багатокутника. Координати точок додатні та не перевищують 1000.

Вихідні дані

Єдиний рядок вихідного файлу DIVIDE.SOL має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x₁ y₁ x₂ y₂. Координати потрібно виводити з точністю 10^-3. Координати точок мають бути додатні та не більші за 1000. 

Приклад вхідних та вихідних даних

Мудреці

В королівстві Олімпія живуть N мудреців, що мають досконалі інтелектуальні здібності. Для підтримання творчого настрою серед інтелектуального осередку королівства король ввів таку традицію.

Кожен вечір M ковпаків розфарбовуються в один з K різних кольорів. Таким чином M_i ковпаків розфарбовано у i-й колір (i=1..K). Мудрецям ці дані відомі. Поки мудреці сплять, кожному з них на голову чіпляють один з ковпаків, а решту ховають. Коли мудреці прокидаються, вони сідають у круг, так щоб кожен з них бачив ковпаки усіх інших, і починають думати про колір свого ковпаку. Це відбувається таким чином. Кожен мудрець пише на папірці чи знає він колір свого ковпака. Після того усі демонструють свої папірці. Якщо хтось написав, що знає колір – процедура закінчується, та усі йдуть на сніданок. Якщо ніхто не зміг визначити колір, то мудреці починають думати знову, операція з папірцями повторюється.

Завдання

Напишіть програму WISEMEN, що за інформацією про колір усіх ковпаків та розподіленням ковпаків серед мудреців визначає які з них першими визначать колір свого ковпака та скільки разів для цього потрібно буде демонструвати папери, або встановить, що ніхто не зможе цього зробити.

Вхідні дані

Перший рядок вхідного файлу WISEMEN.DAT містить цілі числа N (1≤N≤10⁶) – кількість мудреців, M (N≤M≤10⁶) – кількість ковпаків, та K (1≤K≤10⁶) – кількість різних кольорів. Другий рядок містить K цілих чисел, кожне з яких визначає кількість ковпаків певного кольору. Третій рядок складається з N цілих чисел, що являють собою кольори ковпаків кожного з мудреців. Кольори пронумеровані від 1 до K.

Вихідні дані

Перший рядок вихідного файлу WISEMEN.SOL має містити впорядковані за зростанням номери мудреців, що першими дізнаються кольору свого ковпака. Другий рядок має містити одне число, що визначає, скільки разів для цього будуть демонстровані папери. Якщо дізнатися про це неможливо, то єдиний рядок вихідного файлу має містити цифру 0 (нуль).

Приклад вхідних та вихідних даних

Пояснення. Нехай в королівстві всього три мудреця, два з яких мають білий ковпак (колір 1) та один – чорний (колір 2). При цьому ще один білий та один чорний ковпак сховані. На першому етапі ніхто не зможе визначити колір свого ковпаку. На другому етапі кожен з володарів білого ковпаку буде розмислювати так: «Якщо б я мав чорний ковпак, то колега, що має білий, здогадався б про колір свого ковпаку ще на першому кроці, але ж цього не відбулося, тому мій ковпак білий!». А володар чорного ковпака все ще не зможе визначитися. Тобто, першими здогадаються мудреці 1 та 2 з білими ковпаками і папірці для цього будуть продемонстровані два рази.

Живопис

В країні Олімпія дуже розвинутий живопис. Картиною вважається будь-який прямокутник, що складається з чорних і білих одиничних квадратів. Художник Олімпус вирішив радикально покращити свої картини. Для цього він планує до білого та чорного кольорів додати ще й сірий відтінок. За його задумом, границя між кожними чорним і білим квадратом має містити сіру лінію, щоб утворився ефект плавного переходу.

                Але, перед початком роботи, він визначив, що сіра фарба дуже дорого коштує. Щоб заощадити гроші художник вирішив оцінити, чи не вигідніше спочатку перефарбувати деякі білі квадрати в чорні, а чорні в білі для того, щоб мінімізувати витрати на фарбу.

Завдання

Напишіть програму DRAWING, що за інформацією про існуючу картину визначить мінімальну суму грошей, що знадобляться на її покращення.

Вхідні дані

Перший рядок вхідного файлу DRAWING.DAT містить п’ять натуральних чисел N, M, w, b, g. 1≤N, M≤70 – висота та ширина картини, 1≤w,b,g≤1000 – ціна малювання одного білого одиничного квадрата, чорного одиничного квадрата та сірої лінії довжиною одиниця, відповідно. Далі слідує N рядків, кожен з яких складається з M літер. Літера B відповідає чорному квадрату, а W – білому.

Вихідні дані

Єдиний рядок вихідного файлу DRAWING.SOL має містити одне ціле число, яке є мінімальною сумою витрат на покращення картини.

Приклад вхідних та вихідних даних

Пояснення: необхідно перефарбувати нижню праву чорну клітку у білу.