화학량론
시간 제한2초메모리 제한512 MB
각 분자의 원소 개수로 등식을 세워 선형 연립을 풀고, 전체 계수의 최대공약수로 나눈 최소의 양의 정수 계수를 출력합니다.
문제
당신은 Amalgamated Chemical Manufacturing(ACM)과 계약을 맺고 화학자들의 화학량론 계산을 돕게 되었다. 화학량론은 질량 보존 법칙에 따라 화학 반응의 반응물과 생성물을 계산하는 학문이다. 질량 보존 법칙이란 반응물의 총 질량과 생성물의 총 질량이 같다는 법칙이다. 반응물과 생성물의 양 사이의 관계는 보통 양의 정수의 비로 나타난다. 개별 반응물의 양을 알면 생성물의 양을 계산할 수 있고, 그 반대도 가능하다. 반응물과 생성물의 관계는 다음과 같은 화학량론 방정식으로 나타낼 수 있다.
CH4 + 2O2 → CO2 + 2H2O, (1)
이는 "CH4 분자 하나와 O2 분자 두 개가 반응하여 CO2 분자 하나와 H2O 분자 두 개를 생성한다"로 읽을 수 있다. 화학량론 방정식의 왼쪽에 있는 각 원소의 원자 수는 오른쪽에 있는 해당 원소의 원자 수와 같아야 한다. 당신의 임무는 다음과 같은 형태의 방정식이 주어졌을 때
_H2O + _CO2 → _O2 + _C6H12O6, (2)
빈칸을 채워 균형 잡힌 방정식을 만드는 프로그램을 작성하는 것이다. 예를 들어 위 방정식은 다음과 같이 균형을 맞출 수 있다.
6H2O + 6CO2 → 6O2 + 1C6H12O6. (3)
입력
방정식은 M(1 < M ≤ 20)개의 줄로 이루어진 입력으로 주어지며, 각 줄은 화학식의 분자 하나(예: H2O 또는 CO2)에 해당한다. 각 줄 m(1 ≤ m ≤ M)은 다음 필드로 구성된다.
signm Nm elementm,1 countm,1 . . . elementm,Nm countm,Nm
여기서 signm은 +1 또는 -1이며, +1은 이 분자가 방정식의 왼쪽에 나타남을, -1은 오른쪽에 나타남을 뜻한다. Nm(0 < Nm < 20)은 줄에 이어지는 원소/개수 쌍의 수이다. 각 elementm,n(1 ≤ n ≤ Nm)은 대문자 또는 소문자 한두 글자로 이루어진 원소 이름이고, 각 countm,n은 1 ≤ countm,n ≤ 12인 양의 정수이다. 예를 들어 원소/개수 쌍 "Fe 2"는 그 분자가 원소 Fe(철)의 원자 두 개를 포함함을 뜻한다. 한 방정식에 등장하는 고유 원소는 최대 10개이다.
입력의 한 줄에서 원소가 반복될 수 있다. 예를 들어
+1 6 C 1 H 5 C 1 O 1 O 1 H 1
은 CH5COOH 분자가 적어도 하나 방정식의 왼쪽에 나타남을 나타낸다. CH5COOH는 C2H6O2로 쓸 수 있다.
입력은 다음과 같은 줄로 끝난다.
0 0
출력
프로그램은 방정식의 빈칸을 채울 수 C1, . . . , CM(0 < Ci ≤ 1 000)을 순서대로 출력해야 한다. 각 수 Cm(1 ≤ m ≤ M)은 방정식이 균형을 이루는 최소의 수여야 한다. 즉, 모든 Cm 계수를 줄일 수 있는 공약수가 없어야 한다. 모든 입력 테스트 케이스에는 이 조건을 만족하는 유효한 해가 정확히 하나 존재한다고 가정할 수 있다.