Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
63. Химические реакции
Грамматики, рекурсивный разборОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 9G) |
| 24/07/2006 | Лето 2006 - 9 (нет результатов) (G) |
| 19/09/2007 | Занятие 2 (C) |
| 18/05/2011 | Занятие 26 (F) |
| 28/04/2015 | Занятие 23 (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Билл преподаёт химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).
Ваша задача – написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:
<формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}<последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
<элемент> ::= <химический элемент> | "(" <последовательность> ")"
<химический элемент> ::= <заглавная буква> [<строчная буква>]
<заглавная буква> ::= "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` заданных правых частей выведите одну строку вида
<формула левой части>==<формула правой части>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> – замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Пример ввода
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
Пример вывода
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
Примечание. Пример не содержит цифры ноль, потому что она выглядит практически так же, как символ химического элемента кислорода. Настоящие тесты могут содержать любые допустимые символы.
Источник: NEERC, 2001