Розв'язки слід здати на офіційну перевірку до 0 годин 30 січня 2010 року
Чат - консультації за умовами задач на //www.vinnica.ua/netoi
11 січня 2010 року 18-00 - 18-30
15 січня 2010 року 18-00 - 18-30
Оркомітет та журі олімпіади
Задача CD
На заводі, який виробляє чисті CD-диски, їх
складають в "піраміди" один на одного по N
штук, робочою стороною вниз. Але зрідка трапляється, що диски
складено неправильно, робочою стороною то вниз, то вгору. На заводі є
спеціальний автомат, який може зняти з вершини піраміди будь-яку кількість
дисків і, перевернувши зняту стопку, поставити її на місце так, що нижній знятий
диск опиниться вгорі стопки, не порушуючи порядок розташування дисків, що
перекладаються. За яку мінімальну кількість таких операцій можна всі диски в "піраміді"
розташувати правильно, тобто робочою стороною вниз?
Технічні умови. Програма читає кількість дисків
N (1≤N≤100000), а далі N
чисел (1,
якщо диск лежить робочою стороною вниз і 0,
якщо робочою стороною вгору), починаючи з верхнього диска в "піраміді". Всі числа розділені пропусками. Програма виводить
на екран одне число - мінімальну кількість необхідних операцій. Якщо "піраміду"
"привести в порядок" неможливо, програма виводить -1.
Приклад
Введення
6 1 0 0 0 1 0
Введення
4
Задача
DVD
У Петі з'явилася нова комп'ютерна гра. Друзі, дізнавшись про це, принесли
Петі чисті DVD диски і
попросили переписати гру, чим він і зайнявся, пообіцявши, що все буде готово
через M + 1 секунд. Але як тільки Петя почав запис першого диска, він
пригадав, що в його будинку зараз йдуть ремонтні роботи, у зв'язку з якими
відбуватимуться відключення електрики, тому він може і не встигнути записати гру
на всі диски. Оскільки друзі Петі знають, що він дуже відповідальний, то вони
образяться, якщо він не встигне завершити роботу вчасно.
Гра повністю займає вільне місце на одній DVD-болванці. Привід Петі і
StrangeDVD підтримує запис на швидкостях 4x, 8x і 16x і
має одну дивну особливість: величина X має значення, відмінне від
загальноприйнятого стандарту, тому швидкості 4x у приводі
StrangeDVD і будь-якому іншому можуть і не співпасти. Вважатимемо, що
лоток приводу висувається і засувається миттєво, і виймає диск з приводу і
вставляє диск в привід Петя теж миттєво, тобто час витрачається тільки
безпосередньо на запис чергової копії гри. Привід StrangeDVD не
підтримує мультісесію, тому запис на диск проводиться безперервно.
При запису на швидкості 16x значення якості записаного диска дорівнює
1 на швидкості 8х — дорівнює 2, на швидкості 4х —
дорівнює 3. Потрібно дізнатися, скільки часу витратить Петя на запис
дисків за умови, що сумарна якість дисків буде максимальною з можливих, а якщо
таких варіантів декілька, то знайти такий, при якому витрачений час мінімальний.
Відключення електрики, як у нас водиться, не узгоджені між працюючими
бригадами, і вони можуть накладатися один на одне. У випадку, якщо в даний
момент електрика відключена, а інша бригада планувала у цей момент його
відключити, то, природно, вона цього не робить. Тобто, якщо заплановано три
відключення електрики: з 1 по 10 секунду, з 5-ої по
20-ту і з 15-ої по 30-ту, на початок 1-ї секунди
відключили електрику, на 5-ій нічого не станеться, оскільки електрика
вже відключена, на початок 11-ї електрику включать, на початок 15-ї відключать,
на початок 31-ій включать. Жодні дві бригади не відключають електрику одночасно.
Відлік часу проводиться з нульової секунди. Всього M + 1 секунд (0, 1
..., M).
Технічні умови. Програма читає з
клавіатури число M (номер останньої з секунд, що є у Петі), N —
кількість дисків, які потрібно записати, Q — час в секундах для запису
однієї копії на швидкості 16х (відповідно для швидкості 8х цей час
дорівнюватиме 2Q для швидкості 4х — час 4Q), K — кількість
відключень електрики. Далі йдуть K пар чисел P1, P2 - початок і
кінець відключення (номери секунд). Ці пари чисел не обов'язково розташовані в
хронологічному порядку, але завжди P1≤P2. Всі
числа розділено пропусками.
0≤M, N, P1і,
p2і ≤
2 000 000 000
1≤Q≤500
000 000 (або 1≤4Q≤2
000 000 000)
0≤K≤10000
Програма виводить на екран -1, якщо Петя не встигне записати всі
диски. Якщо встигне, то вивести спочатку номер останньої секунди, яку Петя
витратить на запис і через пропуск — сумарну якість, яку досягнуто при запису.
Приклад
Введення
6 4 1 1 4 5
Виведення
6 5
Коментар до прикладу
У нас сім секунд: 0, 1, 2, 3, 4, 5, 6. Секунди 4—5 зайняті, залишаються 0, 1, 2,
3, 6. Є чотири диски, для запису на швидкості 16х потрібна одна секунда. Петя
закінчить запис на останній, шостій секунді, і сумарна якість дорівнюватиме 5.
Задача Case
Як відомо, люди часто
мають відразу декілька захоплень. Наприклад, одна і та ж людина може виступати
на олімпіаді з програмування, грати в аматорському театрі і ходити в
туристичні походи. Нехай кількість можливих захоплень дорівнює m і
всі ці захоплення пронумеровані числами від 1 до m.
Гарантовано, що для кожного з m захоплень існує своя «група за інтересами», кожна людина належить хоча б до однієї з груп і до кожної з m
груп належить хоча б одна людина.
Одного дня Начальник-Забороняльник вирішив, що m груп — забагато, призначив якийсь час "Ч" і велів зібратися представникам кожної групи в
окремому обумовленому місці. Якщо на якомусь з обумовлених місць нікого не
буде, Начальник-Забороняльник дасть собі волю і заборонить відповідну
групу. У такій ситуації не можна, щоб кожен діяв сам по собі, не радячись з іншими. Тому
люди вирішили домовитися між собою. Зрозуміло, що ніхто не піде підтримувати
групу, до якої не належить. Але кожен згоден вибирати одну зі своїх груп так,
щоб жодна з груп не була заборонена. Напишіть програму, яка знайде спосіб
розподілити людей по вказаних місцях Начальником-Забороняльником (або
повідомить, що це неможливо). Достатньо досягти (якщо можливо), щоб на кожне місце
прийшла хоч би одна людина. Якщо є декілька різних способів, які дозволяють
врятувати всі групи від заборони, програма повинна вивести будь-який з їх.
Технічні
умови. Программа читає з клавіатури
кількість груп m (2 ≤ m ≤ 150),
кількість людей n (m ≤ n ≤ 200),
далі n блоків такої структури: перше число блоку Кі
- кількість груп, до якої належить і-й людина (1 ≤ Кі ≤ m)
потім задано Кі номерів тих груп, до яких він належить (в
порядку зростання). Всі вхідні дані записані в одному рядку через пропуски.
Начальник-Забороняльник не належить до жодної з m груп і не є
жодним із згаданих n людей.
Програма повинна вивести
на екран спочатку відповідь 1, якщо зберегти всі групи
можна, або 0 якщо ні. В разі відповіді 1 далі
потрібно вивести в тому ж рядку n чисел (значенням
від 1 до m кожне), які позначають, на збори якої
групи піде відповідний (1-а, 2-а ..., n-а) людина. Якщо є декілька
різних розподілів, які дають можливість врятувати всі групи від заборони,
виводьте будь-який.
Приклади
Введення
3 3 1 1 1 1 2 2 3
Виведення
0
Введення
3 4 1 1 2 2 3 1 3 2 1 3
Виведення
1 1 2 3 1
Задача Border
Сад складається з дерев, стовбури яких в
точності циліндри, причому радіуси різних циліндрів можуть бути дуже різними.
Цей сад потрібно захистити огорожею як можна меншої сумарної довжини, причому
відстань від кожного стовбура до огорожі повинна складати не менше 1.
Напишіть програму для знаходження довжини такої огорожі.
Технічні умови. Програма повинна
прочитати з клавіатури спочатку кількість дерев у саду N (3≤N≤1000)
далі N груп по три числа в кожній — x- і у- координати
центра чергового стовбура і його радіус. Всі координати є цілими числами, які
не перевищують по модулю мільйон, радіуси, — натуральними числами, які
не перевищують тисячу. Гарантовано, що стовбури різних дерев не перетинаються і
не дотикаються. Програма
повинна вивести на екран єдине дійсне число — знайдену мінімальну довжину
огорожі. Округлювати відповідь не потрібно.
Приклад
Введення
6 0 1000 4 1000 0 4 0 0 4 33 47 1 500 500 321 1000 1000 4
Виведення
4.0314159265359E+0003
Задача Woods
Фермери - герої завдань Garden і Newgarden знову отримали у спільне володіння сад прямокутної форми розміром 2*N, розділений стежинами на однакові квадратні ділянки 1*1. На цей раз було вирішено вирощувати фруктові дерева. У фермерів є достатня кількість саджанців K видів, серед яких є такі, що заважають один одному, якщо їх садити на сусідніх (що мають загальну сторону) ділянках. Щоб фруктові дерева плодоносили, на кожній ділянці потрібно садити рівно по одному дереву, і на сусідніх ділянках не повинні рости дерева, що "заважають". Допоможіть фермерам підрахувати кількість способів посадки дерев так, щоб вони всі плодоносили.
Технічні умови. Програма Woods читає з клавіатури через пропуски цілі числа N і К (1<=N<=100, 2<=K<=5), далі кількість пар видів дерев, які не можна садити на сусідніх ділянках S (0<=S<K*(K+1)/2) далі S пар номерів видів дерев. Жодна пара не повторюється. Можливо, що однакові дерева заважають один одному. Програма виводить на екран шукану кількість способів по модулю 2010.
Приклади
Введення 3 2 0
Виведення 64
Введення 2 4 4 2 2 1 2 1 3 3 4
Виведення 37
Завдання підготувили Непомнящий Г., Середенко Д., Пасіхов Ю., Порубльов І.