[===UKR===]
Завдання другого туру NetOI-2006 
Для зручності скопіюйте в БЛОКНОТ через буфер обміну
Розв'язки приймаються до 0 годин 01.12.06.
Чат-консульатації 15.12.05 та 17.12.05 з 19-00 до 19-30
за адресою http://www.vinnica.ua/netoi
Умови задач розміщено на сайті олімпіади.  
Журі олімпіади.
======================================================================

Задача 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


[===RUS===]
Завдания второго тура NetOI-2006 
Для удобства скопируйте в БЛОКНОТ через буфер обмена
Условия размещены на сайте олимпиады.
Решения принимаются до 0 часов 01.12.06.
Чат-консульатации 15.12.06 и 17.12.06 з 19-00 до 19-30
за адресою http://www.vinnica.ua/netoi
Жури олимпиады.

======================================================================

Задача 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). Все числа 
вводятся  одной  строкой  через  пробелы.  Прoграмма  выводит на экран 
единственное число  - искомую величину. 
Пример
Ввод 
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
==============================================
Г.Кравец, Г.Непомнящий, Ю.Пасихов, А.Присяжнюк
==============================================

