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

========================================================
Задача AreaPlus
Партія Юлі Т. та Петі П. недовго  була найбільшою. Після 
її  розколу  найбільшою  стала  партія  ФІНГАЛ  і одразу 
прийняла  рішення:  компенсувати  внесок  фірми   «Еліт-
Околиця»  у  партійну   казну   ФІНГАЛ-у  шляхом надання 
значних    податкових   та   інших  пільг.  Зокрема, був 
прийнятий  закон,  за  яким власники ділянок, куплених у 
цієї фірми, мають право оскаржувати свої межі  лише коли
хоча  б   якась  частина   ділянки має відразу трьох або 
більше   господарів;  якщо ж якусь ділянку чи її частину 
продали  не   більше  ніж  двом  власникам,  то за новим 
законом  це  не  є порушенням. Економісти «Еліт-Околиці» 
підрахували, що навіть такий закон (створений спеціально
«під  них»)  все  ж  не  компенсує  всіх витрат, тому до 
закону  було  внесено доповнення. Суть його зводиться до
того,   що    «Еліт-Околиці»   тимчасово    дозволяється 
дотримуватися  закону  не щодо абсолютно всіх ділянок, а 
лише  щодо  90%  (а 10% ділянок можуть перетинатися і по 
три одночасно, і по чотири, і т.д.).Журналіст С.Паскаліс
зацікавився   подальшою    долею   «Еліт-Околиці»,   тож 
звернувся   в    НІЩО    (Науковий   Інститут  Щасливого 
Оболванювання).  Науково обґрунтований прогноз інституту
стверджував: політична ситуація стабільна, а отже пільги
«Еліт-Околиці»,  (тобто  закон та доповнення)  діятимуть 
довго,  навіть тоді, коли майже всю землю буде продано і 
доведеться  перейти від торгівлі земельними ділянками до 
торгівлі    частинами    простору  у вигляді прямокутних 
паралелепіпедів  з ребрами, паралельними осям координат. 
Журналіст   попросив   приятеля- програміста Б.Пітонніка 
керуючись   цим прогнозом,    написати  програму, яка за 
заданими    координатами   N   паралелепіпедних  ділянок 
з’ясовує,   який  сумарний об’єм вони фактично займають. 
Але Б. Пітоннік ніколи не брав участі в NetOI і не зумів 
цього зробити. Допоможіть йому. 

Технічні   умови:   Програма    зчитує    з   клавіатури  
натуральне   число  N  (2<=N<=100),  а далі  N груп по 6 
цілих  чисел  –  координати  протилежних  вершин ділянок 
(-10000<Хі,  Уі,  Zі <10000).  Всі числа вводяться одним 
рядком    через    пропуск.  Вхідні   дані   гарантовано 
відповідають обмеженням, накладеним згаданими законом та 
доповненням.  Програма  має  вивести  на екран одне ціле 
число – шуканий сумарний об’єм.

Приклад 
Введення
3 0 0 0 10 10 10 19 19 19 9 9 9 20 30 20 30 20 30
Виведення
2999

Задача Conflict
З полярниками – героями задачі Ferry сталася звична  для 
дослідників  історія – про них забули. Добре, що запасів 
продовольства  та  пального  було  на  довгі роки. Так і 
працювали  –  не  зважаючи  ні  на  що день за днем. Але  
почав   спрацьовувати  фактор  психологічної сумісності: 
люди,  що  мусять  довго спілкуватися в межах замкненого 
кола  осіб,  з часом інколи починають не сприймати  один 
одного.  Психологи  вважають,  що  таке ставлення завжди 
взаємне і завжди проявляється між парами осіб, незалежно 
від  присутності  чи  відсутності  інших.  Для виконання 
чергової    серії    досліджень   полярникам    потрібно 
розділитися  на  дві групи, які певний час працюватимуть 
окремо   одна   від   одної.  Допоможіть  з’ясувати,  як 
розподілити   всіх   полярників  по двом групам так, щоб 
всередині  кожної  групи  не було потенційно конфліктних 
пар. 

Технічні умови:   Програма  читає з клавіатури кількість 
полярників  N (3<=N<=10000), потім  кількість потенційно 
конфліктних пар M (0<=M<=20000), потім самі пари, в яких 
полярники  задані  їхніми  номерами від 1 до N. Програма 
виводить  на  екран  у першому рядку 0 (якщо розподілити 
полярників  потрібним   чином   неможливо)  або  1 (якщо 
можливо). Якщо розподіл  можливий, то 2-ий та 3-ій рядки 
повинні  містити розділені пропусками списки полярників, 
віднесених  до  відповідної  групи.  Дбати  про  те, щоб 
розміри  груп   були  (хоча  б приблизно) однаковими, не 
потрібно, але обидві групи мають виявитися не порожніми. 
Якщо  правильних відповідей кілька, виводьте  будь-яку з 
них.

Приклад_1
Введення
5 3 1 2 1 4 3 5
Виведення
1
1 3
2 4 5

Приклад_2
Введення
5 5 1 5 1 4 1 3 2 5 5 3
Виведення
0



Задача NewFerry
Група  бізнесменів вирішила поєднати ділові переговори з 
екстремальними  розвагами   у   дикому  лісі.  Запросили 
фахівців  з   організації  подібних заходів, ті принесли 
сценарій,  частину  якого запозичили  з  задачі  Ferry - 
переправу  групи  річкою на надувному човні на дві особи 
за мінімальний час. Для кожного бізнесмена відомий  час, 
за   який  він може переправитися на човні; якщо у човні 
перебувають  2  бізнесмени,  час переправи дорівнює часу 
менш  розторопного  з них.  Але героям задачі Ferry було 
легко!  Вони на час переправи забули про все, крім того, 
що    потрібно   переправитися   якомога  швидше.  А для 
бізнесменів  дуже  суттєво,  щоб протягом хоча б деякого 
часу ніхто з  них не проводив змов (особистих сепаратних 
переговорів  з метою нажитися за рахунок решти колег). З 
цієї   причини,   деякі  пари  бізнесменів ніяк не можна 
залишати  без  нагляду  конкурентів —  ні у човні, ні на 
якомусь  із  берегів.  За  який мінімальний час всі вони 
зможуть   переправитися,   якщо  головне  —  гарантувати 
відсутність  змов, а вже у другу чергу слід мінімізувати 
час? 

Технічні  умови.  Програма  читає  з клавіатури загальну 
кількість  бізнесменів N (4<=N<=12); потім N натуральних 
чисел  —  час,  необхідний  кожному  з них на переправу; 
потім вказується число M — кількість тих пар, які можуть 
проводити  сепаратні  переговори;  потім  йдуть M описів 
наступного  формату.  Перші  два  числа   кожного  опису 
вказують  тих двох бізнесменів, які можуть наважитися на 
змову;  далі   йде   кількість  та  перелік  конкурентів 
(присутність  хоча  б одного  з конкурентів гарантує, що 
змова  не   відбудеться).  Оскільки  у  бізнесменів нема 
друзів і ворогів, а є лише ділові інтереси, не виключена 
ситуація,   коли   одна   й   та   сама пара бізнесменів 
виявляється  і потенційними  змовниками, і конкурентами, 
які  слідкують  один  за  одним, щоб не допустити  інших 
змов. Всі дані вводяться однією стрічкою через пропуски.
Програма  виводить на екран -1 якщо бізнесменам так і не 
вдасться  переправитися  через річку, інакше — знайдений 
мінімальний   час   (він   гарантовано   не    перевищує 
2000000000).

Приклад
Введення
4 7 3 2 5 2 1 2 1 4 2 3 2 1 4
Виведення
24


Задача Pencils
Журналіст С.Паскаліс   та  програміст  Б .Пітоннік,  які 
стали   добрими   друзями   після   спільної  роботи над 
проблемою з задачі AreaPlus, вирішили разом провести час 
за кухлем пива. Коли пиво було випито,  Паскаліс,  маючи 
два однакові набори олівців різної довжини,  з кожного з 
цих  наборів виклав на  столі дві різних фігури за таким 
правилом:  в  кожному  з  «малюнків»  не  було  спільної 
частини,  що  має  ненульову довжину  для будь-якої пари 
олівців,  тобто   олівці  могли   перетинатися,  але  не 
накладалися   один  на   одного.  Паскаліс   запрпонував 
Пітонніку,  перекладаючи  олівці  в  одному з «малюнків» 
отримати   другий   з точністю до паралельного переносу, 
зробивши  мінімальну  кількість  перекладань. Допоможіть 
йому, адже, як відомо пиво погано впливає на мислення.

Технічні  умови. Прoграма читає з клавіатури  число N (1 
(1<=N<=1000) – кількість  олівців в кожному з наборів. В 
наступних    N 	  четвірках     цілих   чисел   записані 
координати   x1i,  y1i,  x2i,  y2i    початку  та  кінця 
відповідного олівця, Наступні N четвірок чисел  описують 
другий набір олівців в тому ж форматі. Всі координати за 
абсолютною  величиною  не перевищують 10000 . Всі олівці 
мають  ненульову  довжину    (тобто    x1i <> x2i    або 
y1i <> y2i).  Програма  виводить  на екран єдине число – 
шукану величину.

Приклад
Введення
5 0 0 1 2 1 0 0 2 2 0 2 2 4 0 3 2 4 0 5 2 9 -1 10 1 10 1
9 3 8 1 10 1 8 1 9 -1 8 1 9 3
Виведення
3



Задача Trees
Паскаліс  та Пітоннік  вирішили зіграти в нову гру. Вони 
накреслили поле для гри в вигляді "лісу", що складається 
з N  "дерев",  в  "корінь"  кожного  "дерева"  поставили 
фішку. За один хід гравець може перемістити одну фішку з 
вершини  на вершину  по одному з "дерев" по ребру вгору. 
Програє  той, хто не може зробити черговий хід. Паскаліс 
завжди  ходить  першим.  Треба  дізнатися,  хто виграє – 
Паскаліс   чи Пітоннік, при правильній грі суперника, що 
програв.  Якщо  виграє  Паскаліс,  то визначити, скільки 
існує для нього варіантів  першого ходу, щоб виграти при 
будь-якій  грі  Пітонніка.  Якщо  ж  виграє Пітоннік, то 
вивести,  скільки  різних  "дерев"  (по  одному)   можна 
прибрати з ігрового "лісу", щоб виграти міг Паскаліс при 
будь-якій  грі  Пітонніка  (таких  дерев може і не бути).

Технічні умови.  Програма  читає  з клавіатури кількість 
"дерев"  N (1<=N<=20), а потім N послідовностей, кожна з 
яких - кількість  вершин P (1<=P<=50) чергового "дерева" 
і   P-1  пар   цілих  чисел – номери вершин, що з’єднані 
відповідним   ребром   (   "коренева"   вершина,  з якої 
починається   гра,   завжди   має   номер  1). Всі числа 
вводяться   однією   стрічкою   через пропуски. Програма 
виводить   два  числа.  Якщо виграв  Паскаліс- то   1, і 
через  пропуск – кількість можливих для нього початкових 
ходів,   які   привели  б   до  успіху при будь-якій грі 
Пітонніка.  Якщо ж виграв Пітоннік – програма виводить 2 
і  через  пропуск  –  скільки різних "дерев" (по одному) 
можна   прибрати   з   ігрового  "лісу", щоб виграти міг 
Паскаліс при будь-якій грі Пітонiнка. Якщо  таких  немає,
вивести 0 
Приклад_1. 
Введення                                                          
2 3 1 2 2 3 3 1 2 1 3
Виведення 
1 3      

Приклад_2.
Введення                                                         
3 3 1 2 2 3 2 1 2 3 1 2 1 3
Виведення 
2 2      





========================================================
[===RUS===]

С наступающим Новым Годом!
Задания 3-го тура NetOI-2006 
Решения принимаются до 0 часов 05.01.07.
Чат-консульатации 18.12.06 и 25.12.06 с 19-00 до 19-30
по адресу  http://www.vinnica.ua/netoi
Для удобства скопируйте этот текст через буфер  обмена
в БЛОКНОТ

Жюри олимпиады.
=========================================================

Задача AreaPlus
Партия Юли Т. и Пети П. недолго  была наибольшей.  После 
ее  раскола  наибольшей   стала  партия  ФИНГАЛ  и сразу 
приняла  решения:  компенсировать   вклад  фирмы  «Элит-
Окраина» в партийную казну ФИНГАЛ-а путем предоставления
значительных налоговых и  других льгот. В частности, был 
принят  закон,  согласно  которому   владельцы участков, 
купленных  у  этой  фирмы,  имеют  право обжаловать свои 
границы только если какая-либо часть участка имеет сразу 
трех или больше  хозяев; если же какой-либо участок либо 
его  часть  продали не более чем двум  владельцам, то по 
новому закону  это  не  является  нарушением. Экономисты 
«Элит-Окраины»   подсчитали,   что   даже  такой   закон 
(созданный специально «под  них») все же не компенсирует  
всех затрат, поэтому в закон внесли дополнение. Суть его 
сводится к тому, что <Элит-Окраине» временно разрешается 
соблюдать закон не для абсолютно всех участков, а только 
для  90%  (а 10% участков могут  пересекаться  и  по три 
одновременно, и по четыре, и т.д.). Журналист С.Паскалис 
заинтересовался дальнейшей судьбой  «Элит-Окраины»,  для 
чего  обратился  в  НИЧО  ( Научный   Институт  Честного 
Оболванивания).  Научно  обоснованный  прогноз института
гласил: политическая ситуация стабильна, и потому льготы
«Элит-Окраины», (то  есть  закон  и  дополнение)   будут 
действовать  долго,  даже  тогда,  когда почти вся земля 
будет продана и придется  перейти от торговли земельными 
участками  к  торговле   частями   пространства  в  виде 
прямоугольных паралеллепипедов  с ребрами, параллельными 
осям координат. Журналист попросил приятеля-программиста 
Б.Питонника  руководствуясь   этим   прогнозом, написать 
программу,  которая    по    заданным   координатам    N   
параллелепипедных участков определяет,  какой  суммарный 
объем они фактически занимают. Но Б. Питонник никогда не 
участвовал в NetOI и не сумел это сделать. Помогите ему. 

Технические условия: Програма  считывает  с   клавиатуры  
натуральное  число  N (2<=N<=100), а далее  N групп по 6 
целых чисел – координаты противоположных вершин участков
(-10000<Хi,  Уi,  Zi <10000).  Все числа вводятся  одной 
строкой через пробел.  Входные   данные   гарантированно 
соответствуют ограничениям,  наложенным  вышеупомянутыми 
законом и дополнением. Программа должна вывести на экран 
одно целое число – искомый суммарный объем.

Пример
Ввод
3 0 0 0 10 10 10 19 19 19 9 9 9 20 30 20 30 20 30
Вывод
2999

Задача Conflict
С полярниками  –  героями задачи Ferry произошла обычная  
для исследователей  история  – о них забыли. Хорошо, что 
запасов продовольствия и топлива хватало на долгие годы. 
Так и работали – не обращая внимания ни  на  что день за 
днем. Однако  начал проявляться  фактор  психологической 
совместимости: люди, вынужденные  долго общаться в узком 
кругу,  со  временем  иногда начинают не переносить друг 
друга. Психологи считают,  что  такое  отношение  всегда 
взаимно  и  всегда  проявляется   между   парами  людей, 
независимо  от  присутствия или  отсутствия других.  Для 
проведения очередной серии исследований полярникам нужно    
разделиться на две группы, которые некоторое время будут 
работать отдельно одна от другой. Помогите  распределить   
всех полярников на две группы так,чтобы в составе каждой  
группы не было потенциально конфликтных пар. 

Технические  условия:  Программа  читает   с  клавиатуры 
количество полярников  N (3<=N<=10000), затем количество 
потенциально конфликтных пар M (0<=M<=20000), затем сами 
пары, в которых полярники заданы их  номерами от 1 до N. 
Программа выводит  на  экран  в  первой  строке  0 (если 
распределить полярников нужным образом  невозможно) либо  
1 (если возможно). Если распределение возможно,то вторая 
и третья  строки  должны содержать разделенные пробелами 
списки полярников, относящихся к соответствующей группе.  
Заботиться о том, чтобы размеры  групп   были  (хотя  бы 
приблизительно)  одинаковыми,  не  нужно,  но обе группы 
должны  оказаться  не пустыми.  Если  правильных ответов 
несколько, выводите  любой из них.

Примеры
Ввод
5 3 1 2 1 4 3 5
Вывод
1
1 3
2 4 5

Ввод
5 5 1 5 1 4 1 3 2 5 5 3
Вывод
0


Задача NewFerry
Группа  бизнесменов решила объединить деловые переговоры 
с экстремальными развлечениями  в диком лесу. Пригласили 
специалистов  по  организации  подобных  мероприятий, те 
принесли  сценарий,  часть  которого  позаимствовали  из 
задачи  Ferry - переправу группы через речку на надувной 
лодке на два  человека за минимальное время. Для каждого 
бизнесмена   известно    время,  за   которое  он  может 
переправиться   на  лодке;  если  в  лодке  находятся  2  
бизнесмена,   время   переправы   равно  времени   менее  
расторопного  из них. Но героям задачи Ferry было легко! 
Они на время переправы забыли обо всем, кроме  того, что  
необходимо   переправиться  как  можно  быстрее.  А  для 
бизнесменов   очень   важно,  чтобы  даже   в  небольшой 
промежуток  времени  никто  из  них  не  сговорился  (не 
проводил личных сепаратных переговоров  с целью нажиться 
за счет остальных коллег). По этой   причине   некоторые  
пары  бизнесменов никак нельзя оставлять  без  присмотра  
конкурентов — ни в лодке, ни на любом  берегу. За  какое 
минимальное время все они смогут   переправиться,   если 
главное  — гарантировать отсутствие сговора, а во вторую 
очередь следует минимизировать время? 

Технические условия. Программа читает с клавиатуры общее 
количество бизнесменов N (4<=N<=12); затем N натуральных 
чисел — время, необходимое каждому  из них на переправу; 
затем указывается  число M — количество тех пар, которые 
могут  проводить  сепаратные  переговоры;  затем  идут M 
описаний следующего  формата. Первые  два  числа каждого  
описания указывают  тех двух  бизнесменов, которые могут 
решиться на сговор; далее идет количество и перечисление  
конкурентов (присутствие хотя  бы одного  из конкурентов 
гарантирует, что  сговор  не   состоится).  Поскольку  у  
бизнесменов нет  друзей и врагов,  а есть только деловые 
интересы, не исключена ситуация, когда одна и та же пара 
бизнесменов является  и потенциальными  заговорщиками, и 
конкурентами, которые  следят друг  за  другом, чтобы не 
допустить  других сговоров.  Все  данные  вводятся одной 
строкой через пробелы. Программа  выводит  на  экран -1, 
если бизнесменам так и  не удалось  переправиться  через 
речку,   иначе  —  найденное   минимальное   время  (оно  
гарантированно не превосходит 2000000000).                                                

Пример
Ввод
4 7 3 2 5 2 1 2 1 4 2 3 2 1 4
Вывод
24


Задача Pencils
Журналист С.Паскалис и программист  Б .Питонник, ставшие 
верными друзьями  после   совместной  работы над задачей 
AreaPlus,  решили вместе провести время за кружкой пива. 
Когда пиво было  выпито,  Паскалис, имея  два одинаковых 
набора карандашей разной длины, из каждого набора сложил 
на столе две разных фигуры согласно  следующему правилу: 
в каждом из «рисунков»  не  было  общей  части,  имеющей  
ненулевую длину  для  любой  пары  карандашей,  то  есть 
карандаши могли пересекаться, но  не  накладывались друг 
на друга.  Паскалис  предложил  Питоннику,  перекладывая  
карандаши  в  одном из «рисунков», получить   другой   с 
точностью до параллельного переноса, сделав  минимальное 
количество   перекладываний.  Помогите  ему,  ведь,  как 
известно, пиво плохо влияет на мышление.

Технические условия: Программа читает с клавиатуры число 
N (1 <= N <= 1000)  –  количество карандашей в каждом из 
наборов. В последующих N четверках целых чисел  записаны
координаты   x1i,   y1i,   x2i,   y2i   начала  и  конца  
соответствующего карандаша,  следующие  N четверок чисел  
описывают  второй набор карандашей в том же формате. Все 
координаты по абсолютной величине не превосходят  10000. 
Все карандаши имеют ненулевую длину (то есть  x1i <> x2i    
или y1i <> y2i). Программа выводит на экран единственное 
число – искомую величину.

Пример
Ввод
5 0 0 1 2 1 0 0 2 2 0 2 2 4 0 3 2 4 0 5 2 9 -1 10 1 10 1
9 3 8 1 10 1 8 1 9 -1 8 1 9 3
Вывод
3



Задача Trees
Паскалис  и Питонник  решили сыграть в новую игру. Они 
начертили поле для игры в виде "леса", состоящего из N  
"деревьев",  в  "корень"  каждого  "дерева"  поставили 
фишку. За один ход игрок  может переместить одну фишку 
из вершины в вершину  по одному из "деревьев" по ребру 
вверх. Проигрывает тот, кто не может сделать очередной 
ход. Паскалис всегда ходит первым. Необходимо  узнать,  
кто выиграет - Паскалис  или  Питонник, при правильной 
игре проигравшего соперника. Если выигрывает Паскалис,  
то определить, сколько  существует  для него вариантов  
первого хода, чтобы выиграть при любой игре Питонника.  
Если  же  выиграет  Питонник,  то   вывести,   сколько  
различных  "деревьев"   (по одному)   можно  убрать  с 
игрового "леса", чтобы выиграть мог Паскалис при любой  
игре Питонника (а таких деревьев может и не быть).

Технические условия.   Программа  читает  с клавиатуры 
количество  "деревьев"  N (1 <= N <= 20),  а  затем  N 
последовательностей,  каждая  из  которых - количество  
вершин P(1<=P<=50) очередного "дерева" и P-1 пар целых  
чисел  -  номера  вершин,  соединенных соответствующим   
ребром ("корневая" вершина, с которой начинается игра,   
всегда  имеет  номер  1).  Все  числа  вводятся  одной  
строчкой  через пробелы. Программа выводит два  числа.  
Если  выиграл  Паскалис  -  то 1,  и  через   пробел - 
количество возможных для него начальных ходов, которые   
привели бы к успеху при любой игре Питонника.  Если же 
выиграл Питонник - программа выводит 2 и  через пробел  
-  сколько разных "деревьев" (по одному) можно  убрать   
с игрового "леса",  чтобы  выиграть  мог  Паскалис при 
любой игре Питонника. Если таких нет, вывести 0.
 
Пример_1. 
Ввод                                                          
2 3 1 2 2 3 3 1 2 1 3
Вывод 
1 3      
Пример_2.
Ввод  
3 3 1 2 2 3 2 1 2 3 1 2 1 3                                                       
Вывод 
2 2      



