Меньшиков Задачи из тренировки 12

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

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

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

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

Каждый член последовательности десятичных цифр d1, d2, d3,…, начиная с четвертого, равен последней цифре суммы трех предыдущих. По заданным d1, d2, d3 найти N-й член последовательности. Ограничения: 1 \(\le\)N\(\le\) 1015, время 1 с. Ввод из файла seq2.in. В первой строке находятся цифры d1, d2, d3, разделенные пробелами, во второй — число N. Вывод в файл seq2.out. Вывести одну цифру — dN.
Пример
Ввод
1 4 8
4
Вывод
3

Задача 12B. Гирлянда

Гирлянда состоит из N лампочек на общем проводе (смотрите рисунок). Один ее конец закреплен на заданной высоте А мм (Н1 = А). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (Нi = (Hi-1+ Hi+1)/2 – 1 для 1 < i < N). Требуется найти минимальную высоту второго конца В (В = HN) при условии, что ни одна из лампочек не должна лежать на земле (Hi > 0 для 1 \(\le\) i \(\le\) N). Ограничения: 3 \(\le\)N\(\le\) 1000 — целое, 10 \(\le\) А \(\le\) 1000 — вещественное, время 1 с. Ввод из файла garland.in. В первой строке находятся два числа, N и А. Вывод в файл garland.out. Вывести одно вещественное число В с двумя знаками после запятой.
Примеры
Ввод
8 15
Вывод
9.75  

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

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от нее. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остается только две карты.
Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 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 \(\le\)N\(\le\) 100, числа на картах целые от 1 до 100, время 1 с.
Вывод в файл mpuzzle.out. Вывести одно целое число — минимально возможное число очков.
Пример
Ввод
6
10 1 50 50 20 5
Вывод
3650

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

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

Задача 12E. Водопровод

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (х1, у1), а вторая — в точке (x2, у2). К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90°. Требуется, зная длины отрезков труб L1, L2,…, LK и количество отрезков каждой длины С1, С2,…, СK, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Ограничения: 1 \(\le\)K\(\le\)4, 1 \(\le\)x1, y1, x2, y2, Li\(\le\) 1000, 1 \(\le\)Сi\(\le\)10, все числа целые, время З с.
Ввод из файла wpipe.in. В первой строке находятся числа х1, у1, х2, у2, К, затем 2K чисел: L1, L2,…, LK, С1, С2, …, СK. Вывод в файл wpipe.out. Вывести одно число — минимальное количество нужных отрезков труб или -1, если соединение невозможно. 

Примеры
Ввод
5 5 5 6 1 2 10
Вывод
-1

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

Билл преподает химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство). Ваша задача — написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству  химических элементов в заданной левой части. Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделенных знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Еще более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:
<формула> : := [<число>] <последовательность> {“+” [<число>] <последовательность>}
<последовательность> : :=<элемент> [<число>] {<элемент> [<число>]}
<элемент> : :=<химический элемент> | “(” <лоследовательность> “)”
<химический элемент>:: = <прописная буква>[<строчная буква>]
<прописная 6уква> : := “А”..”Z”
<строчная буква> : = “а”..”z”
<число> : := ”1″. .”9″ {“0”. .”9″}
Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X — сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)
• С встречается всего 2 раза;
• Н встречается всего 6 раз (5+ 1);
• 0 встречается всего 13 раз (1 + 3 • 2 +3 • 2);
• Si встречается всего 3 раза.
Все множители в формулах — целые числа не меньше 2, если заданы явно, или равны 1 — по умолчанию.
Ввод из файла chem.in. В первой строке находится формула — левая часть уравнения, во второй — одно число N — количество рассматриваемых правых частей, в каждой из следующих N строк — одна формула — предлагаемая правая часть уравнения.
Ограничения: 1 \(\le\) N\(\le\) 10, длина формулы не превосходит 100 символов, каждый отдельный химический элемент встречается всего не более 10 000 раз в каждой формуле, время 1 с.
Вывод в файл chem.out. Для каждой из N заданных правых частей выведите одну строку вида
<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> – замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Пример
Ввод
C2H50H+302+3(Si02)
7
2C02+3H20+3Si02
2C+6H+130+3Si
99C2H5OH+3SiO2
3Si04+C2H50H
C2H50H+302+3(Si02)+Ge
3(Si(o)J)+2C0+3H20+02
2C0+3H20+302+3Si
Вывод
C2H50H+302+3(S i 02)==2C02+3H20+3Si 02
C2H50H+302+3(Si 02)==2C+6H+130+3S i
C2H50H+302+3(S i 02)!=99C2H50H+3S i 02
C2H50H+302+3(S i 02)==3S i 04+C2H50H
C2H50H+302+3(S i 02)!=C2H50H+302+3(S i 02)+Ge
C2H50H+302+3(S i 02)-=3(S i(o)J)+2C0+3H20+02
C2H50H+302+3(S i 02)!=2C0+3H20+302+3S i

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

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