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

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

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

Задача 11А. Последовательность

В последовательности чисел а₁, а₂, а₃,... задан первый член, а остальные вычисляются по формуле a_i = (a_i-1)² mod 10 000. Найти N-й член последовательности. Ограничения: 0 $\le$ а₁ $\le$ 10 000, 1 $\le$ N$\le$ 2 000 000 000, время 1 с. Ввод из файла seq.in. В первой строке находятся числа а₁ и N, разделенные пробелом. Вывод в файл seq.out. Вывести одно число — a_N.
Примеры
Ввод
4 3
Вывод
256

Задача 11B. Провода

Дано ^отрезков провода длиной L₁, L₂,..., L_N сантиметров. Требуется разрезанием получить из них Травных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить К отрезков длиной даже 1 см, вывести 0.
Ограничения: 1 $\le$ N$\le$10 000, 1 $\le$K$\le$ 10 000, 100$\le$ L_i $\le$ 10 000 000, все числа целые, время 1 с. Ввод из файла cable.in. В первой строке находятся числа N и К. В следующих N строках — L₁, L₂,..., L_N, по одному числу в строке. Вывод в файл cable.out. Вывести одно число — полученную длину отрезков.
Пример
Ввод
4 11
802
743
457
539
Вывод
200

Задача 11С. Палиндромы

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычеркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычеркивания из данного слова некоторого (возможно, пустого) набора таких символов, что полученная в результате строка является палиндромом. Способы, различающиеся только порядком вычеркивания символов, считаются одинаковыми.
Ограничения: 1 $\le$ N$\le$ 60, время 1 с. Ввод из файла palindr.in. В первойстроке записано слово S.
Вывод в файл palindr.out. Вывести одно целое число — количество способов вычеркивания.
Пример
Ввод
ВАОВАВ
Вывод
22

Задача 11D. Круговая площадь

Два круга заданы координатами центров в прямоугольной декартовой системе координат и радиусами. Найти площадь их пересечения. 

Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000, время 1 с. Ввод из файла circarea.in. В первой строке находятся шесть вещественных чисел через пробел — координаты центров и радиусы двух кругов: х₁, у₁, r₁, х₂, y₂, r₂. Вывод в файл circarea.out. Вывести одно вещественное число с двумя знаками после запятой — площадь пересечения кругов.
Пример
Ввод
20.0 30.0 15.0 40.0 30.0 30.0
Вывод
608.37

Задача 11Е. Гомер Симпсон

Обеденный перерыв Гомера Симпсона составляет T мс. Один гамбургер Гомер съедает за N мс, один чизбургер — за М. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения: 1 $\le$ M, N, T$\le$1 000 000, все числа целые, время 2 с. Ввод из файла homer.in. В первой строке находятся три числа — М, N и T, разделенные пробелами. Вывод в файл homer.out. Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остается какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остается как можно меньше.
Примеры
Ввод 1
3 5 54
Вывод 1
18
Ввод 2
3 5 55
Вывод 2
17
Ввод 3
4 4 6
Вывод 3
1 2

Задача 11F. Дробная арифметика

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:
• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).
Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0,11.
Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю, время 1 с. Ввод из файла frac-ar.in. В первой строке вводится дробь (первый операнд), во второй — знак операции («+» — сложение, «-» — вычитание, «*» — умножение, «/» — деление), в третьей строке — дробь (второй операнд). Обе дроби могут быть сократимы. Вывод в файл frac-ar.out. В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.
Пример
Ввод
-3 1/6
+
2/4
Вывод
-2 2/3

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