|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||39||22||22||66.667%|
Professor Cesium has created a new process to transform some chemical product into another type of chemical with some residues. The process is simple: he just needs to input a given number of molecules of type A, enter the output type B he desires and start the machine. It will create as many molecules of type B as possible. Unfortunately, professor Cadmium was jealous of his work and tried to sabotage the machine by inverting wires on his machine. Professor Cesium, alerted by one of his assistants, was able to repair the mistake. To detect any problem in the future, he is asking you to create an automatic way to compute the number of molecules that the machine should output. With this algorithm, he will be able to detect whether his precious machine was tampered with.
Molecules are written as string composed of upper case letters and numbers. Upper case letters represent atoms. Note that Cesium only uses single letters of the alphabet as abbreviations for atoms, so H, C, A, X, Y, ... can be used but He, Mg, ... can not. If a letter is not followed by a number, it means there is only one atom of it. An atom followed by a number l (1 ≤ l < 103) represents l copies of that atom. Atoms can appear multiple times in a chemical product.
For example: H2OC100H means 2 atoms of H, then 1 of O, then 100 of C then 1 of H again.
The output consists of a single line containing the maximum number n of output molecules we are able to construct using the input molecules.
H 2 O
C2H6 10 C3H8
CH3OH 1 CH4
C6H6OCH2O 10 HCN
C6H14 10 C5H10
AB2CD1 2 A2B3CD2