Решения принимаются до 0 часов

20 декабря 2014 г.

Задача Diamonds. Приглашая гостей на день рождения, Ее Величество Королева Франции (ЕВКФ) прозрачно намекнула, что каждый гость должен подарить ей четыре бриллианта, суммарная масса которых ровно N карат - для королевских подвесок. При этом ЕВКФ добавила обязательные условия:

1) все массы камней - натуральные числа карат;

2) каждый набор отличается от любого другого набором масс камней (хотя бы двух!);

3) в наборе массы камней могут быть какими угодно, если они удовлетворяют первым двум условиям.

Каким может быть при этих условиях наибольшее количество гостей S?

Технические условия. Программа Diamonds считывает из стандартного устройства ввода значение N (4<=N<=6761) и выводит на устройство стандартного вывода значение S.

Примеры

КОММЕНТАРИЙ. Для N=7 имеем наборы: 1+1+1+4, 1+1+2+3, 1+2+2+2 і S=3.

Задача Cake. Мама испекла на день рождения Малыша пирог в форме выпуклого многоугольника. После окончания праздника гости начали упрекать, что им досталось мало пирога, а все съел Карлсон. Малыш знает, что Карлсон всегда ест только один треугольный кусок, но режет пирог так, чтобы получить как можно больше. Помогите посчитать, сколько пирога съел Карлсон.

Технические условия. Программа Cake читает с клавиатуры количество вершин многоугольника N, которые задают пирог (3<=N<=2000) и дальше через пробел N строчек по 2 разделенных пробелом целых числа, не превышающих 10000000 по абсолютной величине - координаты вершин в порядке обхода по или против часовой стрелки. Программа выводит на экран одно вещественное число - площадь треугольного куска, который съел Карлсон.

Примеры.

Ввод

4

2 2

5 1

7 4

4 7

Вывод 10.5000000000

Ввод

3

0 0

0 5

12 5

Вывод 30.0000000000

Комментарий. Во втором примере Карлсон действительно съел весь пирог.

Задача Pill. Коротышки из Цветочного города внезапно заболели. Доктор Пилюлькин, как всегда, измерил у каждого коротышки температуру, но забыл, какая температура считается нормальной, главное, чтобы у всех была одинаковая. У Пилюлькина есть красные и синие таблетки. Красная таблетка повышает температуру тела на один градус, а синяя снижает (тоже на один градус). Какое минимальное количество таблеток понадобится доктору, чтобы вылечить всех коротышек?

Технические условия. Программа Pill читает с клавиатуры количество коротышек N (1<=N<=100000) и далее N чисел через пробел - температуру очередного коротышки t_i (1<=i<=N, 1<=t_i<=1000000000). Программа выводит на экран искомое количество таблеток.

Примеры

Ввод
2 3 7

Вывод
4

Ввод
3 1 6 4

Вывод
5

Комментарий. В первом примере один из способов: даем первому коротышке три красные таблетки, а второму - одну синюю. Во втором примере первый коротышка получает 3 красных таблетки, второй - 2 синие.

Задача Diode. Проблема энергосбережения является очень актуальной. И в этом смысле перспективными представляются светодиодные светильники. Пусть мы имеем светильник в виде прямоугольной матрицы N x M. В каждой ячейке находится светодиод, который может светиться или нет. Генеральный Конструктор (ГК) может выбрать любую ячейку и сделать переключение - поменять состояние всех светодиодов в ее строке и ее столбце на противоположное. Например, если ГК выбрал ячейку (2,2), светильник, имеющий вид (см. рис.1), затем будет выглядеть (см рис.2).

Таким образом, за 1 переключение изменят свое состояние на противоположное N+M-1 светодиод. Выполняя такую операцию определенное количество раз, ГК хочет достичь состояния, чтобы все светодиоды светились. Интересно, что у него получится.

Технические условия. Программа Diode читает с устройства стандартного ввода количество тестов Т (от 2 до 10), а дальше Т групп строк: в первой строке каждой группы 2 числа N и M (2<=N,M<=1000), а дальше N по M чисел 0 или 1 через пробел: 0, если соответствующий светодиод светится, и 1 – если нет. Программа выводит одной строкой без пробелов последовательность из Т цифр 2 и 3. (2 – если соответствующий светильник удалось включить полностью, 3- если нет).

Пример

Задача Schools. В нашем районе n сел, некоторые из них соединены дорогами, которые нигде не пересекаются. В каждом селе одна школа. Директор департамента образования получил приказ, согласно которому в целях экономии в районе должна остаться только одна школа, а из других школ учеников должны возить школьные автобусы. Райгосадминистрация выделяет один литр бензина на один километр на каждого ученика. Директор знает, сколько учеников учится в каждой школе. Также известны расстояния между сёлами. Помогите определить, какую школу нужно оставить, чтобы минимизировать расходы бензина.

Технические условия. Программа Schools читает с клавиатуры целые числа n (1<=n<=100) - количество сёл, и через пробел m - количество дорог. Далее программа читает через пробел m троек чисел - номера сёл i, j (1<=i,j<=n, i<>j), соединенных дорогой, и s – длину дороги (s натуральное число, не превышающее 100). Далее через пробел программа вводит n натуральных чисел a_i, не превышающих 100 – количество учеников в і-й школе. Гарантируется, что по дорогам можно проехать из любого села в любое другое. Любые два села соединены не более чем одной дорогой. Каждая дорога описывается один раз. На всех дорогах разрешается движение в двух направлениях. Если несколько школ обеспечат минимум затрат бензина, директор выбирает школу с наименьшим номером.

Пример

Ввод
3 3 1 2 8 2 3 2 3 1 6 10 6 4

Вывод
1

Комментарий. Если выбрать первую школу, нужно 8*6+6*4=72, если вторую – 8*10+2*4=88, если третью – 6*10+2*6=72 литров бензина.