Примеры

Задача 19. Последовательность (2)

Каждый член последовательности десятичных цифр d ₁, d ₂, d ₃..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d ₁, d ₂, d ₃ найти N -й член последовательности.
Ограничения: 1 < = N < = 10¹⁵, время 1 с.
Ввод из файла seq2.in. В первой строке находятся цифры d ₁, d ₂, d ₃, разделённые пробелами, во второй - число N.
Вывод в файл seq2.out. Вывести одну цифру - d_N.
Примеры

Задача 20. Гирлянда

Гирлянда состоит из 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 - вещественное, время 1 с.
Ввод из файла garland.in. В первой строке находятся два числа, N и A.
Вывод в файл garland.out. Вывести одно вещественное число B с двумя знаками после запятой.
Примеры

Задача 21. Головоломка умножения

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

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

Например, если карты содержат числа 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.

Ввод из файла mpuzzle.in. В первой строке находится число карт N, во второй - разделённые пробелами N чисел на картах.
Ограничения: 3 < = N < = 100, числа на картах целые от 1 до 100, время 1 с.
Вывод в файл mpuzzle.out. Вывести одно целое число - минимально возможное число очков.
Примеры

Задача 22. Точки в многоугольнике

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 < = N < = 10 000, координаты вершин целые и по модулю не превосходят 1 000 000, время 1 с.
Ввод из файла polygonp.in. В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод в файл polygonp.out. Вывести одно число - искомое количество точек.
Примеры

Задача 23. Водопровод

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x ₁, y ₁), а вторая - в точке (x ₂, y ₂).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L ₁, L ₂,..., L_K и количество отрезков каждой длины C ₁, C ₂,..., C_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 < = K < = 4, 1 < = x ₁, y ₁, x ₂, y ₂, L_i < = 1000, 1 < = C_i < = 10, все числа целые, время 3 с.
Ввод из файла wpipe.in. В первой строке находятся числа x ₁, y ₁, x ₂, y ₂, K, затем 2 K чисел: L ₁, L ₂,..., L_K, C ₁, C ₂,..., C_K.
Вывод в файл wpipe.out. Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно.
Примеры

Задача 24. Химические реакции

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

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

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

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

• < формула>:: = [< число> ] < последовательность> {" +" [< число> ] < последовательность> }
• < последовательность>:: = < элемент> [< число> ] {< элемент> [< число> ]}
• < элемент>:: = < химический элемент> | " (" < последовательность> ")"
• < химический элемент>:: = < прописная буква> [< прописная буква> ]
• < заглавная буква>:: = " 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 - по умолчанию.

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

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

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

если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:

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