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

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

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

Задача 14А. Марковский цикл

Ограниченный алгоритм Маркова состоит из последовательности предложений s₁s₂...s_N -> d₁d₂...d_N, где s_i и d_i — символы из алфавита А, В, С. Подстрока s₁s₂...s_N  называется левой, a d₁d₂...d_N — правой частью предложения. Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв А, В, С, следующим образом: перебираются все предложения начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.
При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество «ациклических» (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги — ациклическими.
Ввод из файла markovc.in. В первой строке находится исходная текстовая строка, а в следующих строках — предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов. Ограничения: длина исходной текстовой строки и левых частей предложений —от 1 до 12 букв, количество предложений — от 1 до 50, время 3 с. Вывод в файл markovc.out. Вывести два целых числа, разделенных пробелом, — количество ациклических шагов и длину цикла.
Пример
Ввод
АВАВС
С->A
АВ->BA
BAA->ABC
Вывод
3 3

Задача 14B. Д-44

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

Задача 14С. Упаковка символов

Билл пытается компактно представить последовательности прописных символов от А до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD — это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:
• Последовательность, содержащая один символ от А до Z, является упакованной. Распаковка этой последовательности дает ту же последовательность из одного символа.
• Если S и Q — упакованные последовательности, то SQ — также упакованная последовательность. Если S распаковывается в S', a Q распаковывается в Q', то SQ распаковывается в S' Q'.
• Если S — упакованная последовательность, то X (S) — также упакованная последовательность, где X — десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.
Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов. Ограничения: длина исходной последовательности от 1 до 100, время 2 с.
Ввод из файла fotding.in. В первой строке находится последовательность символов от А до Z.
Вывод в файл folding.out. В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.
Примеры
Ввод
AAAAAAAAAABABABCCD
Вывод
9(A)3(AB)CCD
Ввод
NEERCYESYESYESNEERCYESYESYES
Вывод
2(NEERC3(YES))

Задача 14D. Пирамиды

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам ребер пирамиды найти ее объем. Ограничения: длины ребер — целые положительные числа, не превосходящие 1000, время 1 с.
Ввод из файла pyramids.in. В первой строке находятся шесть чисел через пробел — длины ребер пирамиды ABCD. Порядок ребер: AB, AC, AD, ВС, BD, CD. Вывод в файл pyramids.out. Вывести одно вещественное число с четырьмя знаками после запятой — объем пирамиды.
Примеры
Ввод
1 1 1 1 1 1
Вывод
0.1179
Ввод
1000 1000 1000 3 4 5
Вывод
1999.9937

Задача 14E. Поле для крикета

Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложения своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер. Ваша задача — помочь бедному Архитектору сохранить голову, написав программу, которая найдет максимальный размер поля для крикета и его положение внутри парка, удовлетворяющие требованиям Короля. Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север — юг и восток — запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север — юг и восток — запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева.
Оси этой системы координат, конечно, параллельны направлениям север — юг и восток — запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный — координаты (W, Н), где W и Н— длина и ширина парка соответственно (смотрите рисунок). 
В этой задаче вы можете пренебречь диаметром деревьев. Деревья не могут находиться внутри поля для крикета, но могут располагаться на его сторонах. Поле для крикета может также касаться границы парка, но не должно лежать вне парка.
Ввод из файла cricket.in. Первая строка содержит три целых числа, N, W и Н, разделенных пробелами: N — число деревьев в парке, W и Н — длина и ширина парка соответственно. Следующие N строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа х_i и у_i, разделенных пробелом и представляющих собой координаты i-го дерева. Все деревья имеют различные координаты.
Ограничения: 1 $\le$N$\le$100, 1 $\le$ W, H$\le$ 10 000, 0$\le$x_i, $\le$ W, 0 $\le$у_i$\le$Н, время 1 с.
Вывод в файл cricket.out. Вывести через пробел три целых числа, P, Q и L, где (P, Q) — координаты юго-западного угла поля для крикета, L — длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.
Пример
Ввод
7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7
Вывод
4 3 4

Задача 14F. Электронная таблица

Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от А до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например B1, S8. Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки, бинарные операторы +, -, * и / (целочисленное деление). Так, 567, E8/2, (3+B3)*(C4-1) являются правильными выражениями. Все операторы целочисленные. Деление на ноль дает в результате ноль. Если значение ячейки, на которую ссылается некоторое выражение, не определено, оно считается равным нулю. Ситуация, когда две или более ячейки зависят друг от друга, является отдельным случаем — циклической ссылкой.
Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000, время 1 с.
Ввод из файла sprsheet.in. Первая строка содержит число выражений N Следующие N строк имеют формат <Имя клетки>=<выражение>. Все выражения корректные, и каждая ячейка определена не более чем одним выражением. Вывод в файл sprsheet.out. В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.
Пример
Ввод
4
A1=B1+C5 .
B1=20
C5=B1 /D7-E1*E1
E1=(3+1)*2
Вывод
-44

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