Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Тринадцатая тренировка

содержание задачника

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

Две бесконечные равномерные прямоугольные решетки заданы размерами ячеек x₁ x y₁ и х₂ х у₂. Решетки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решетки относительно узла первой составляет D_x по горизонтали и D_y по вертикали. В результате наложения образуется новая, «составная» решетка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решетки.
Ограничения: 1 $\le$ х₁, у₁, х₂, у₂ $\le$ 100, 0 $\le$ D_x < х₁, 0 $\le$ D_y < у₁, все числа целые, время 1 с.
Ввод из файла dlattke.in. В первой строке находятся числа х₁, у₁, х₂, у₂, Dx, Dy, разразделенные пробелами.
Вывод в файл dlattice.out. В первой строке вывести N — количество получившихся площадей, в следующих N строках — сами площади.
Пример
Ввод
20 20 12 10 2 0
Вывод
4
20
60
100
120

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

(F_k), $k\in (-\infty; +\infty)$ - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k-1 + F_k+1 (для любого целого k). Даны также i, F_i, j, F_j, n ($i\ne j$. Найти F_n. Пример части последовательности:

Ограничения: -1000 $\le$ i, j, n $\le$ 1000, -2 000 000 000 $\le$ F_k $\le$ 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.
Пример
Ввод
3 5 -1 4 5
Вывод
12

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

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

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

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

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

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

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

Анализ временной сложности алгоритмов — важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым. Обычно определяют время выполнения алгоритма по отношению к n — «размеру» входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т. п. Поскольку определение формулы зависимости временной сложности алгоритма от n — непростая задача, было бы замечательно, если бы ее можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:
<Программа> : := "BEGIN" <Список операторов> "END"
<Список операторов> :: = <Оператор> | <Оператор><Список операторов>
<Оператор> ::=<Оператор LOOP> | <Оператор OP>
<Оператор LOOP> ::=<Заголовок LOОР><Список onepaтopoв>"END"
<Заголовок LOOP> : := "LOOP" <число> | "LOOP n"
<Оператор OP> : := "OP" <число>
Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключенный в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, то есть или заданное константное число раз, если задано число, или п раз, если параметром является 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 с.
Пример
Ввод
2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
ОР 1997 LOOP n LOOP n ОР 1 END END
END
Вывод
Program #1
Runtime = 3*n^2+11*n+17
Program #2
Runtime = n^2+1997

содержание задачника