`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Задания 2-го тура( 12.11.06-01.12.06 )

Задача NewArea

Відома з задачі  першого туру  Area фірма «Еліт-Околиця» знову  з’явилась  на ринку торгівлі землею.  І знову вони при продажу вказували неправильні  межі  ділянок, хоча  ділянки завжди  мали форму прямокутника  зі сторонами, паралельними осям координат. Кожному покупцеві продавалося не більше  однієї ділянки. Після завершення розпродажу виявилось, що серед тих, хто заплатив за одну і ту ж землю, не тільки Юля Т. і Петя П. (а їх ділянки,  природно, перетиналися), але й інші їх товариші. Петя і Юля вирішили з покупців організувати партії, причому за новим принципом. Якщо дві ділянки мали хоча б одну спільну точку, то їх власники потрапляли в одну партію. У цю ж партію потрапляли всі власники ділянок, які мали хоча б одну спільну точку з ділянкою хоч би одного раніше прийнятого партійця (межі належать ділянкам).  Природно, що партія Юлі та Петра  виявилася найчисельнішою. Але через причини, що відомі з задачі "Area", вони не змогли порахувати кількість членів  своєї партії. Допоможіть їм і цього разу. 

Технічні умови: Програма зчитує з клавіатури натуральне число N (2<=N<=200), а далі N груп по 4 цілих числа – координати протилежних вершин ділянок (-1000<Хі, Уі<1000). Всі числа вводяться одним рядком через пропуск. Програма  виводить на екран одне число – шукану величину.

Приклад 
Введення
6 30 100 -40 120 60 40 40 90 -90 30 -20 - 40 -30 50 50 20 20 80 -20 110 -50 80 -70 20
Виведення 4

Задача Ferry

Учасників полярної експедиції, які зимували на крижині, спіткало велике нещастя: крижина розкололася, і всі вони опинилися на маленькому її уламку. Потрібно було якнайшвидше переправитися через широку тріщину. У їх розпорядженні є двомісний надувний човен. Для кожного полярника відомий час, за який він може переправитися на цьому човні через тріщину. Якщо ж у човні  перебувають 2 полярники, час переправи дорівнює часу менш розторопного з них. За який мінімальний час всі полярники можуть переправитися на велику крижину? 
Технічні умови: Програма зчитує з клавіатури натуральне  число N (3<=N<=10000) – кількість полярників, а далі N натуральних чисел не більших 10000 – час переправи кожного полярника. Всі числа вводяться одним рядком через пропуск.  Програма виводить на екран одне число – шукану величину.
Приклад
Введення 4 1 6 7 8
Виведення 23

Задача Mayor

Мер міста Балдуйська вирішив вимостити міські тротуари плиткою.  Всі тротуари в місті мають ширину 3 метри. Завод, яким, як повелося, володів «мерський» син, випускав плитку 1x1 і 1x2 метри, а іншу плитку, звичайно, міські власті не купували. Фірма «Балдстрой» отримала завдання вистилати шматок тротуару довжиною N метрів. Скількома різними способами  вони можуть це зробити?
Технічні умови: Програма читає  з клавіатури одне ціле число N  (2<=N<=1000) – довжину тротуару. Програма виводить на екран єдине число – шукану величину.
Приклад:
Введення 2
Виведення 22

Задача Mayor2

Вже відомий нам мер Балдуйська вирішив зменшити витрати на організацію автобусних маршрутів. Саме місто мало N вулиць, що розміщені строго з півдня на північ, і N вулиць, що їх перетинають і розташовані із заходу на схід. Всі вулиці, природно, однакової довжини з одностороннім рухом (тобто їхати можна або з півдня на північ, або із заходу на схід). Вранці на деяких перехрестях збираються люди. Їх забирають автобуси "безрозмірної" місткості, щоб відвезти на роботу за місто. Та ось одна маленька проблема: всі автобуси починають свій маршрут з самого південно-західного перехрестя. Яку мінімальну кількість автобусів слід  випускати на маршрут вранці, щоб підібрати всіх пасажирів, що стоять на перехрестях? 
Технічні умови:  Програма зчитує з клавіатури два натуральні числа :N – кількість вулиць у кожному напрямку (N<=1000), P – кількість перехресть із пасажирами (1<P<=1000000),  а далі P груп по 2 числа – координати перехрестя з пасажирами. Зрозуміло, що "саме південно-західне" перехрестя має координаті (1,1).  Всі числа вводяться одним рядком через  пропуски. Програма виводить на екран одне число – шукану величину.
Приклад
Введення 8 8 3 1 4 2 7 3 2 4 5 4 3 6 4 7 7 6
Виведення 3

Задача Zigzag

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

Технічні умови: Програма зчитує з клавіатури кількість елементів послідовності N (3<=N<=10000) і N чисел-елементів послідовності (кожен не більший 1000 за абсолютною  величиною). Всі числа вводяться одним рядком через пропуск. Програма виводить на екран одне число – шукану величину.

Приклад: 
Введення: 6 1 4 7 9 7 4
Выведення: 3


Г.Кравець, Г.Непомнящий, Ю.Пасіхов, А.Присяжнюк

© LIKT 1998-2024