Примеры. Задача 6. Умножение многочленов

Задача 6. Умножение многочленов

Ввести в символьной форме два многочлена от x с целыми коэффициентами и вывести их произведение в порядке убывания степеней - также в символьной форме.
Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 10⁴, время 1 с.
Ввод из файла polymul.in. В двух строках находятся многочлены.
Вывод в файл polymul.out. В единственной строке выводится многочлен.
Примеры

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

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x ₁ y ₁ и x ₂ y ₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет D_x по горизонтали и D_y по вертикали. В результате наложения образуется новая, " составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.
Ограничения: 1 < = x ₁, y ₁, x ₂, y ₂ < = 100, 0 < = D_x < x ₁, 0 < = D_y < y ₁, все числа целые, время 1 с.
Ввод из файла dlattice.in. В первой строке находятся числа x ₁, y ₁, x ₂, y ₂, D_x, D_y, разделённые пробелами.
Вывод в файл dlattice.out. В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.
Примеры

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

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

Ограничения: -1000 < = i, j, n < = 1000, -2 000 000 000 < = F_k < = 2 000 000 000 (k = min(i, j, n)... max(i, j, n)), время 1 с.
Ввод из файла fiboseq.in. В первой строке находятся числа i, F_i, j, F_j, n.
Вывод в файл fiboseq.out. Вывести одно число F_n.
Примеры

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

Определим правильные скобочные выражения так:

1. Пустое выражение - правильное.
2. Если выражение S правильное, то (S) и [S] также правильные.
3. Если выражения A и B правильные, то и выражение AB - правильное.

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

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

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

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

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

Задача 12. Статическая сложность

Анализ временн о й сложности алгоритмов - важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым.

Обычно определяют время выполнения алгоритма по отношению к n - " размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временн о й сложности алгоритма от n - непростая задача, было бы замечательно, если бы её можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где < число> может быть любым неотрицательным целым числом:

• < Программа>:: = " BEGIN" < Список операторов> " END"
• < Список операторов>:: = < Оператор> | < Оператор> < Список операторов>
• < Оператор>:: = < Оператор LOOP> | < Оператор OP>
• < Оператор LOOP>:: = < Заголовок LOOP> < Список операторов> " END"
• < Заголовок LOOP>:: = " LOOP" < число> | " LOOP n"
• < Оператор OP>:: = " OP" < число>

Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключённый в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, то есть или заданное константное число раз, если задано число, или n раз, если параметром является n. Время выполнения списка операторов равно сумме времени выполнения его частей. Таким образом, время выполнения программы в целом зависит от n.

Ввод из файла icomplex.in. В первой строке находится целое число k - число программ во входном файле. Затем идут k программ, удовлетворяющих приведённой грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах.

Вывод в файл icomplex.out. Для каждой программы сначала идёт строка с номером программы. В следующей строке записывается время работы программы в терминах n - многочлен степени не более 10. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое с большей степенью должно предшествовать слагаемому с меньшей степенью, слагаемые с коэффициентом 0 не записываются, множители 1 не записываются. Общий вид второй строки " Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k". Если время выполнения нулевое, нужно вывести " Runtime = 0". За строкой с многочленом должна следовать пустая строка.

Ограничения: вложенность операторов LOOP не превышает 10, размер входного файла не более 2 Кбайт, коэффициенты многочлена в ответе не превышают 50 000, время 1 с.