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

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

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

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

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

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

Гирлянда состоит из N лампочек на общем проводе (смотрите рисунок). Один ее конец закреплен на заданной высоте А мм (Н₁ = А). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (Н_i = (H_i-1+ H_i+1)/2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца В (В = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 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. Водопровод

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (х₁, у₁), а вторая — в точке (x₂, у₂). К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90°. Требуется, зная длины отрезков труб L₁, L₂,..., L_K и количество отрезков каждой длины С₁, С₂,..., С_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Ограничения: 1 $\le$K$\le$4, 1 $\le$x₁, y₁, x₂, y₂, L_i$\le$ 1000, 1 $\le$С_i$\le$10, все числа целые, время З с.
Ввод из файла wpipe.in. В первой строке находятся числа х₁, у₁, х₂, у₂, К, затем 2K чисел: L₁, L₂,..., L_K, С₁, С₂, ..., С_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

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

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