Решения следует сдать на официальную проверку до 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
Задания подготовили Непомнящий Г., Середенко Д., Пасихов Ю., Порубльов И.