Задача 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, вирішили разом провести час за кухлем пива. Коли пиво було випито, Паскаліс, маючи два однакові набори олівців різної довжини, з кожного з цих наборів виклав на столі дві різних фігури за таким правилом: в кожному з «малюнків» не було спільної частини, що має ненульову довжину для будь-якої пари олівців, тобто олівці могли перетинатися, але не накладалися один на одного. Паскаліс запрпонував Пітонніку, перекладаючи олівці в одному з «малюнків» отримати другий з точністю до паралельного переносу, зробивши мінімальну кількість перекладань. Допоможіть йому, адже, як відомо пиво погано впливає на мислення.
Технічні умови. Програма читає з клавіатури число 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 і через пропуск – скільки різних "дерев" (по одному) можна прибрати з ігрового "лісу", щоб виграти міг Паскаліс при будь-якій грі Пітонніка. Якщо таких немає, вивести 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
Г.Кравець, Е.Любинський, Г.Непомнящий, Ю.Пасіхов, І.Порубльов
|
