Алгоритмы

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определённого числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцеплений на каждом конце. У компании также есть один локомотив.

Сцепления и для локомотива, и для вагонов обозначены буквой A или B. Повернуть вагон или локомотив противоположной стороной невозможно.

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

Поезда считаются различными, если при их сравнении от одного конца к другому выявляется хотя бы одно отличие.

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

Входные данные
В первой строке через пробел N - число вагонов, находящихся в распоряжении компании, и K - требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцеплений вагонов. Описания даны как AB, AA, BB или BA.

Ограничения: 1 <= K <= N <= 40.

Выходные данные
В первой строке выводится слово "YES", если можно сформировать хотя бы один поезд, или "NO" - в противном случае.

Если поезд сформировать возможно, во второй строке должно указываться число способов это сделать.

Даны длины трёх отрезков. Если возможно, требуется построить треугольник, в котором один из этих отрезков был бы высотой, один - биссектрисой и один - медианой; все построенные из одной вершины.

Ограничения: длина каждого из трёх отрезков от 0.01 до 100, точность результата должна быть 0.001.

Входные данные
Вводятся три положительных числа, разделённых пробелами, - длины отрезков.

Выходные данные
Выводится одно число - площадь треугольника. Если треугольник нельзя построить, вывести -1. Если может быть построено несколько треугольников с разными площадями, вывести 0.

В калькулятор вводится натуральное число K и нажимается клавиша "+". Калькулятор всё ещё показывает K. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для её достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат K + K, после очередного нажатия результат увеличивается на K. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.

1 <= K <= 999.

Входные данные
В первой строке находится одно число - K.

Выходные данные
Если цели достичь невозможно, вывести "Impossible", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от A до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например, B1, S8.

Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки, бинарные операторы +, -, * и / (целочисленное деление). Например, 567, E8/2, (3+B3)*(C4-1) являются правильными выражениями. Все операторы целочисленные. Деление на ноль даёт в результате ноль.

Если значение ячейки, на которую ссылается некоторое выражение, не определено, оно считается равным нулю. Ситуация, когда две или более ячейки зависят друг от друга, является отдельным случаем - циклической ссылкой.

Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000.

Входные данные
Первая строка содержит число выражений N. Следующие N строк имеют формат <Имя клетки>=<выражение>. Все выражения корректные, и каждая ячейка определена не более чем одним выражением.

Выходные данные
В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.

Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложение своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.

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

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

В этой задаче вы можете пренебречь диаметром деревьев. Деревья не могут находиться внутри поля для крикета, но могут располагаться на его сторонах. Поле для крикета может также касаться границы парка, но не должно лежать вне парка.



Входные данные
Первая строка содержит три целых числа, N, W и H, разделённых пробелами: N - число деревьев в парке, W и H - длина и ширина парка соответственно.

Следующие N строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа xi и yi, разделённых пробелом и представляющих собой координаты i-го дерева. Все деревья имеют различные координаты.

Ограничения: 1 <= N <= 100, 1 <= W, H <= 10 000, 0 <= x_i <= W, 0 <= y_i <= H.

Выходные данные
Вывести через пробел три целых числа, P, Q и L, где (P, Q) - координаты юго-западного угла поля для крикета, L - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

Ограничения: длины рёбер - целые положительные числа, не превосходящие 1000.

Входные данные

В первой строке находятся 6 чисел через пробел - длины рёбер пирамиды ABCD. Порядок рёбер: AB, AC, AD, BC, BD, CD.

Выходные данные

Вывести одно вещественное число с четырьмя знаками после запятой - объём пирамиды.

При решении задач баллистики следует учитывать сопротивление воздуха. Пусть сила сопротивления воздуха пропорциональна квадрату модуля скорости движения снаряда и направлена противоположно скорости. Считая коэффициент пропорциональности силы сопротивления воздуха квадрату скорости постоянной величиной, рассчитать дальность полёта снаряда (с точностью до 10 м) при стрельбе из 85-миллиметровой пушки Д-44 под заданным углом к горизонту, если масса снаряда равна 9.6 кг, а начальная скорость - 800 м/с. Известно также, что при стрельбе под углом 45 градусов дальность стрельбы составляет 15 650 м. Ускорение свободного падения считать равным 9.8 м/с².

Ограничения: угол от 5 до 85 градусов.

Входные данные
В первой строке находится единственное вещественное число - угол в градусах.

Выходные данные
Вывести одно целое число - дальность в метрах.

Ограниченный алгоритм Маркова состоит из последовательности предложений где s_i и d_i - символы из алфавита A, B, C. Подстрока s₁s₂...s_N называется левой частью, а d₁d₂...d_N - правой частью предложения.

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

При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.

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

Ограничения: длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.

Выходные данные
Вывести два целых числа, разделённых пробелом - количество ациклических шагов и длину цикла.

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

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

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

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

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

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

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

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

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

Входные данные
В первой строке находятся числа N и S, разделённые пробелом.

Выходные данные
Вывести одно целое число - количество способов представить S как сумму произведений.

По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.

Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000.

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

Выходные данные
Вывести два числа с двумя знаками после запятой - координаты центра тяжести.

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

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x₁ y₁ и x₂ y₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x₁, y₁, x₂, y₂ <= 100, 0 <= D_x < x₁, 0 <= D_y < y₁, все числа целые.

Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, D_x, D_y, разделённые пробелами.

Выходные данные
В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.

Билл преподаёт химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).

Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.

Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.

Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:

• <формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
• <последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
• <элемент> ::= <химический элемент> | "(" <последовательность> ")"
• <химический элемент> ::= <прописная буква> [<строчная буква>]
• <прописная буква> ::= "A".."Z"
• <строчная буква> ::= "a".."z"
• <число> ::= "1".."9" {"0".."9"}

Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)

• C встречается всего 2 раза;
• H встречается всего 6 раз (5 + 1);
• O встречается всего 13 раз; (1 + 3 * 2 + 3 * 2);
• Si встречается всего 3 раза.

Все множители в формулах - целые числа не меньше 2, если заданы явно, или равны 1 - по умолчанию.

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

Ограничения: 1 <= N <= 10, длина формулы не превосходит 100 символов, каждый отдельный химический элемент встречается всего не более 10 000 раз в каждой формуле.

Выходные данные
Для каждой из N заданных правых частей выведите одну строку вида

<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> - замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Ограничения: 3 <= N <= 10 000, координаты вершин целые и по модулю не превосходят 1 000 000.

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

Выходные данные
Вывести одно число - искомое количество точек.

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.

Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

Входные данные
В первой строке находится число карт N, во второй - разделённые пробелами N чисел на картах.

Ограничения: 3 <= N <= 100, числа на картах целые от 1 до 100.

Выходные данные
Вывести одно целое число - минимально возможное число очков.

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H₁ = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (H_i = (H_i - 1 + H_i + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

Входные данные
В первой строке находятся два числа, N и A.

Выходные данные
Вывести одно вещественное число B с двумя знаками после запятой.

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

Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000.

Входные данные
В первой строке находятся шесть вещественных чисел через пробел - координаты центров и радиусы двух кругов: x₁, y₁, r₁, x₂, y₂, r₂.

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

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

Ограничения: 1 <= N <= 60.

Входные данные
В первой строке записано слово S.

Выходные данные
Вывести одно целое число - количество способов вычёркивания.

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади - точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

На схеме три куска - один без дыр, а два - с одной дырой каждый: первый площадью 8, второй - площадью 12.
Ваша цель - найти кусок с наибольшим количеством дыр в нём. Дыра - это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.

Входные данные
В первой строке содержатся два числа W и H, разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках - или * (ASCII 42), или точка (ASCII 46).

Ограничения: 1 <= W, H <= 100.

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