Задачи за вознаграждение

Здраствуйте,задачи за вознаграждения:
1)
Задача 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.

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

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

Контакты
icq 566-934-872
mail andrikstrelok@bigmir.net

Цена Договорная