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



