Задача F. Химические реакции
Билл преподаёт химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).
Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать: <формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>} <последовательность> ::= <элемент> [<число>] {<элемент> [<число>]} <элемент> ::= <химический элемент> | "(" <последовательность> ")" <химический элемент> ::= <прописная буква> [<прописная буква>] <заглавная буква> ::= "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 заданных правых частей выведите одну строку вида
<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> - замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Примеры Ввод 1
C2H5OH+3O2+3(SiO2)
7
2CO2+3H2O+3SiO2
2C+6H+13O+3Si
99C2H5OH+3SiO2
3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)+Ge
3(Si(O)2)+2CO+3H2O+O2
2CO+3H2O+3O2+3Si
Вывод 1
C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2
C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si
C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2
C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge
C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
C2H5OH+3O2+3(SiO2)!=2CO+3H2O+3O2+3Si
Примечание. Пример не содержит цифры ноль, потому что она выглядит практически так же, как символ химического элемента кислорода. Настоящие тесты могут содержать любые допустимые символы.
Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H1 = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (Hi = (Hi - 1 + Hi + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = HN) при условии, что ни одна из лампочек не должна лежать на земле (Hi > 0 для 1 <= i <= N).
Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x1, y1), а вторая - в точке (x2, y2).