SnarkNews Winter Series-2008, Round 3

Объём памяти, предоставляемый программе, составляет 64 мб.

        Задача A. Двойная решётка

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x1 y1 и x2 y2. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.
Ограничения: 1 <= x1, y1, x2, y2 <= 100, 0 <= Dx < x1, 0 <= Dy < y1, все числа целые, время 2 с.
Ввод из файла dlattice.in. В первой строке находятся числа x1, y1, x2, y2, Dx, Dy, разделённые пробелами.
Вывод в файл dlattice.out. В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.
Примеры 
Ввод 1
20 20 12 10 2 0
Вывод 1
4
20
60
100
120

        Задача B. Последовательность Фибоначчи

{Fk} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи Fk = Fk - 1 + Fk - 2 (для любого целого k). Даны i, Fi, j, Fj, n (i <> j). Найти Fn. Пример части последовательности:

k-2-10123456
Fk-54-132571219

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= Fk <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)), время 2 с.
Ввод из файла fiboseq.in. В первой строке находятся числа i, Fi, j, Fj, n.
Вывод в файл fiboseq.out. Вывести одно число Fn.
Примеры 
Ввод 1
3 5 -1 4 5
Вывод 1
12

        Задача C. Скобки (3)

Определим правильные скобочные выражения так:
  1. Пустое выражение - правильное.
  2. Если выражение Sправильное, то (S)и [S]также правильные.
  3. Если выражения Aи Bправильные, то и выражение AB- правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.
Ограничения: исходная последовательность содержит не более 100 скобок, время 2 с.
Ввод из файла bracket3.in. В первой строке находятся символы (, ), [и ]без пробелов.
Вывод в файл bracket3.out. Выводится искомая последовательность скобок без пробелов.
Примеры 
Ввод 1 Ввод 2 Ввод 3 Ввод 4
([(]      ([[)]]    (([))]    (([[[))]]]
Вывод 1 Вывод 2 Вывод 3 Вывод 4
()[()]    ([[()]])  (([]))[]  ()()[[[()()]]]

        Задача D. Центр тяжести

По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.
Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000, время 2 с.
Ввод из файла centgrav.in. В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод в файл centgrav.out. Вывести два числа с двумя знаками после запятой - координаты центра тяжести.
Примеры 
Ввод 1 Ввод 2
4              4
5 0            1 1
0 5            11 1
-5 0           11 11
0 -5           1 11
Вывод 1 Вывод 2
0.00 0.00      6.00 6.00

        Задача E. Сумма произведений

Дан набор переменных x1, x2, ..., xN. Каждая переменная xi может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным xi значения так, чтобы сумма всех возможных произведений xi * xj была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число xi = 0.
Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000, время 2 с.
Ввод из файла prodsum.in. В первой строке находятся числа N и S, разделённые пробелом.
Вывод в файл prodsum.out. Вывести одно целое число - количество способов представить S как сумму произведений.
Примеры 
Ввод 1 Ввод 2
5 0       3 -2
Вывод 1 Вывод 2
3         0

        Задача F. Д-44

При решении задач баллистики следует учитывать сопротивление воздуха. Пусть сила сопротивления воздуха пропорциональна квадрату модуля скорости движения снаряда и направлена противоположно скорости. Считая коэффициент пропорциональности силы сопротивления воздуха квадрату скорости постоянной величиной, рассчитать дальность полёта снаряда (с точностью до 10 м) при стрельбе из 85-миллиметровой пушки Д-44 под заданным углом к горизонту, если масса снаряда равна 9.6 кг, а начальная скорость - 800 м/с. Известно также, что при стрельбе под углом 45 градусов дальность стрельбы составляет 15 650 м. Ускорение свободного падения считать равным 9.8 м/с2.
Ограничения: угол от 5 до 85 градусов, время 2 с.
Ввод из файла d44.in. В первой строке находится единственное вещественное число - угол в градусах.
Вывод в файл d44.out. Вывести одно целое число - дальность в метрах.
Примеры 
Ввод 1
45
Вывод 1
15649