Тренировка S11

Тренировка S11
Время тестирования приведено для Intel Celeron 400.
Решения должны быть представлены на Turbo Pascal 7.0. Объём памяти, предоставляемый программе, составляет 500 кб.

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

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

Ввод 1    Ввод 2
4 3       0 2000000000
Вывод 1   Вывод 2
256       0

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

Дано N отрезков провода длиной L₁, L₂, ..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= L_i <= 10 000 000, все числа целые, время 1 с.
Ввод из файла cable.in. В первой строке находятся числа N и К. В следующих N строках - L₁, L₂, ..., L_N, по одному числу в строке.
Вывод в файл cable.out. Вывести одно число - полученную длину отрезков.
Примеры

Ввод 1
4 11
802
743
457
539
Вывод 1
200

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

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

Ввод 1
BAOBAB
Вывод 1
22

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

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

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

Ввод 1
20.0 30.0 15.0 40.0 30.0 30.0
Вывод 1
608.37

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

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения: 1 <= M, N, T <= 1 000 000, все числа целые, время 2 с.
Ввод из файла homer.in. В первой строке находятся три числа - M, N и T, разделённые пробелами.
Вывод в файл homer.out. Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.
Примеры

Ввод 1    Ввод 2    Ввод 3
3 5 54    3 5 55    4 4 6
Вывод 1   Вывод 2   Вывод 3
18        17        1 2

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

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

знак числа (пишется только в случае, когда его отсутствие изменяет число);
целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
пробел (не пишется, если отсутствует целая или дробная часть);
числитель (если он не равен нулю);
знак / (если есть числитель);
знаменатель (если есть числитель).

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

Ввод 1
-3 1/6
+
2/4
Вывод 1
-2 2/3