С наступающим Новым Годом!

Задания принимаются до 0 часов 28 января 2017 года

Задача Bell. В полусферический колокол, края которого плотно прилегают к горизонтальной поверхности стола, наливают жидкость через отверстие вверху. Когда жидкость доходит до некоторого уровня h, она приподнимает колокол и начинает из-под него течь. Найдите этот уровень воды, если масса колокола равна m, его внутренний радиус R, плотность жидкости .

Технические условия: Программа BELL читает с устройства стандартного ввода действительные числа m, R и через пробел (измеренные в кг, м и кг/м³ соответственно) и  выводит на устройство стандартного вывода единственное число – ответ.  Ответ не должен отличаться от правильного больше, чем на =10^-6. Если колокол не всплывет, выведите -1.

Ограничения: 0.01 <= m <= 10¹⁰, 0.1 <= R <=100, 100.0 <= <=15000.

Пример:

Задача COOKIES. Бабушка готовила печенье. Для этого она раскатала тесто в большой пласт в форме круга и стаканчиками различных диаметров выдавила в нём круглые кусочки, чтобы потом запечь их и получить из них вкусное печенье. Известно, что никакие два круглых выреза не пересекаются между собой, кроме того, все вырезы полностью содержатся внутри пласта теста. Однако вырезы могут касаться друг друга и края пласта теста.

Любимый внук из корыстных соображений решил помочь бабушке: он решил выдавить в оставшейся части пласта круглую заготовку для печенья как можно большего размера. Однако он не знает, какой диаметр должен быть у стаканчика, которым нужно выдавливать такую заготовку. Помогите ему.

Технические условия: Напишите программу COOKIES, которая читает с устройства стандартного ввода размеры пласта теста, а также положение и размеры вырезанных заготовок, и выводит на устройство стандартного вывода радиус максимальной по размеру заготовки, которую еще можно вырезать из этого пласта теста.

В первой строке данных находится действительное число R – радиус пласта теста. Считается, что центр пласта находится в начале координат – в точке с координатами (0,0). Вторая строка содержит число N – количество уже вырезанных заготовок. Следующие N строк содержат по 3 действительных числа x_k, y_k, r_k – координаты центра и радиус очередного выреза (k = 1, 2,..., N).

Единственная строка вывода должна содержать искомый радиус максимальной по размеру заготовки, которую еще можно вырезать из пласта теста. Ответ не должен отличаться от правильного больше, чем на =10^-3.

Ограничения: 0.0 < R <=1000.0, 1 <= N <= 100.

Пример: смотри рисунок

Задача Spruce. Фермер Иван Петрович купил участок, состоящий из m квадратных грядок з юга на север и из n грядок с запада на восток. Он хочет посадить на участке ели, которые, когда они вырастут, он выгодно продаст под Новый Год. Однако   ели   можно садить лишь по таким правилам:

1. На каждой  грядке может расти не более трех елей.
2. Нельзя оставлять  грядки пустыми.
3. На каждом квадрате, образованном четырьмя соседними грядками, должно расти ровно восемь елей.

Помогите фермеру посчитать, сколькими способами он может посадить ели на своем участке.

Технические условия. Программа Spruce читает с устройства стандартного ввода через пробел числа m, n (2<=m,n<=30) и выводит на устройство стандартного вывода искомое количество способов.

Примеры

Ввод 2 2
Вывод 19
Ввод 2 3
Вывод 45

Задача HOPPER. Исследователи, изучающие интеллект насекомых, провели следующий эксперимент. Длинную ленту разбили на N клеток одинакового размера и на первую клетку посадили кузнечика. Цель кузнечика – достичь последней клетки ленты. Часть клеток ленты закрашены в красный цвет, которого кузнечик боится – на такие клетки он становиться не может. Известно, что первая и последняя клетки ленты никогда не закрашиваются в красный цвет.

Кузнечик перемещается по ленте прыжками. Он может прыгать только из клетки в клетку. Кузнечик может прыгать по ленте как вперед, так и назад.

Сперва кузнечик может перепрыгнуть только на соседнюю клетку. Это прыжок длины 1. После каждого прыжка кузнечик выбирает направление следующего прыжка (вперед или назад), а также может увеличить длину прыжка на одну клетку, уменьшить длину прыжка на одну клетку, либо оставить длину прыжка неизменной. Кузнечик не может прыгать на красные клетки или выпрыгивать за пределы ленты.

Определите, сможет ли кузнечик добраться до последней клетки ленты, и если сможет, то какое наименьшее количество прыжков ему придется для этого совершить.

Технические условия. Напишите программу HOPPER, которая читает с устройства стандартного ввода число N – количество клеток в ленте. Вторая строка ввода содержит последовательность из N нулей и единиц, разделенных пробелами, которая показывает, как раскрашена лента. При этом 0 означает обычную клетку, а 1 – закрашенную в красный цвет. Программа выводит на устройство стандартного вывода  одно число – наименьшее количество прыжков, необходимое кузнечику, чтобы достигнуть последней клетки ленты, или число -1, если это невозможно.

Ограничения: 1 < N <= 1000.

Пример

Задача Virus2016. Имеется большой квадрат с длиной стороны 2n+1, разбитый на клетки 1х1. В начальный момент времени (t=0) в центре квадрата (клетка с координатами (0, 0)) поселился вредный вирус. Через секунду он, распадаясь, заражает четыре соседних клетки с координатами (-1,-1), (-1, 1), (1, -1), (1, 1). Еще через секунду все четыре распадаются так же, как и первый, заражая соседей, но если в одной клетке может появиться не один, а несколько вирусов, то они взаимно уничтожаются.  Далее указанные действия повторяются. Процесс размножения вируса прекращается, если вирусы появились в клетках, которые прилегают к сторонам квадрата. Определить, сколько клеток с вирусом будет в большом квадрате в этот  момент.

Технические условия. Программа Virus2016 читает с устройства стандартного ввода целое число n (0<n<200). Программа выводит на устройство стандартного вывода искомое количество зараженных клеток.

Пример

Задание подготовили Й.Энтин, Г.Непомнящий, Ю.Пасихов