Сбалансированные химические уравнения
Одна из сложных задач в химии — это уравнивание числа атомов в химическом уравнении. Наша задача связана с этой проблемой.
Химики следуют следующим правилам при составлении химических уравнений:
Название каждого элемента сокращается до двух букв. Первая буква всегда заглавная, а вторая, если она есть, — строчная (например, кальций обозначается как Ca, кислород как O, а хлор как Cl).
Каждая молекула состоит из определенного числа атомов. Чтобы представить молекулу, мы объединяем сокращенные названия её составных атомов. Например, NaCl обозначает хлорид натрия. Каждое название атома может сопровождаться числом частоты. Например, хлорид кальция CaCl2 состоит из одного атома кальция и двух атомов хлора. Если частота не указана, она считается равной 1 (так что HCl эквивалентно H1Cl1). Для упрощения можно предположить, что частота появления атома не превышает 9 (поэтому в задаче нет C11H22O11). Обратите внимание, что в формуле молекулы может быть несколько вхождений одного и того же атома, как, например, атом H в CH3COOH.
В обычных химических реакциях несколько молекул соединяются и образуют несколько других молекул. Например, известный пример нейтрализации:
2HCl + CaO2H2 → CaCl2 + 2H2O
Это означает, что две молекулы хлороводородной кислоты (HCl) с одной молекулой гидроксида кальция образуют одну молекулу хлорида кальция (CaCl2) и две молекулы воды.
В каждой химической реакции общее количество каждого атома на правой стороне уравнения равно общему количеству этого атома на левой стороне (поэтому это называется уравнением!).
Ваша задача — написать программу, которая найдет подходящие коэффициенты x_1, x_2, …, x_{M }и y_1, y_2, …, y_{N }, чтобы уравновесить (несбалансированное) уравнение вида
A_1+A_2+A_3+ … +A_M → B_1+B_2+B_3+ … +B_N
следующим образом:
x_1 A_1+ x_{2 }A_2+ x_{3 }A_3+ … + x_{M }A_M → y_{1 }B_1+ y_{2 }B_2+ y_{3 }B_3+ … + y_{N }BN
Входные данные
Первая строка содержит целое число t (1 ≤ t ≤ 10), количество тестовых случаев. Каждый тестовый случай состоит из одной строки, содержащей выражение вида:
A_1+A_2+A_3+ … +A_{M }= B_1+B_2+B_3+ … +B_N
Каждое A_{i }или B_{i }— это формула молекулы в соответствии с правилами, изложенными в пунктах 1 и 2.
Входные уравнения даны таким образом, что если они могут быть уравновешены, коэффициенты x_{i }и_{ }y_i_{ }могут находиться в диапазоне от 1 до 9. В уравнении менее 10 молекул и менее 10 различных типов атомов. Кроме того, можно предположить, что молекулы содержат не более 3 различных видов атомов. Также можно предположить, что в входном файле нет пробелов, а максимальная длина входных строк составляет 200 символов.
Выходные данные
Вывод будет содержать одну строку на каждый тестовый случай, содержащую список необходимых коэффициентов, разделенных пробелами, в следующем порядке:
x_{1 } x_{2 } … x_{M } y_{1 } y_{2 } … y_N
Коэффициенты должны быть целыми числами в диапазоне от 1..9. Очевидно, что для тестового случая может быть более одного ответа. В таких ситуациях напечатайте ответ, который минимизирует число:
(Это (M+N)-значное десятичное число, цифры которого — коэффициенты x_i и y_i). Если уравнение невозможно уравновесить, строка вывода должна быть IMPOSSIBLE.