O expresie corect parantezată (prescurtat ecp) este un sir format din caracterele (,),[,],{,} si care se formează după următoarele reguli:

• (), [],{} sunt ecp
• dacă A este ecp, atunci (A), [A] si {A} sunt ecp
• dacă A si B sunt ecp, atunci AB este ecp

Exemple de ecp: ({}{}[(())]), ((([]))), {({()}[])}. Exemple de siruri care nu sunt ecp: ([]], {(}). Costul unei ecp se calculează astfel:

• () este o ecp de cost 2
• [] este o ecp de cost 3
• {} este o ecp de cost 5
• dacă A este ecp de cost k, atunci (A) are costul 2²*k, [A] are costul 3³*k, iar {A} are costul 5⁵*k
• dacă A si B sunt ecp de costuri k si p, atunci expresia AB este o ecp de cost k*p.

De exemplu, costul expresiei ()[(()){}()] este 2*3³*(2²*(2)*5*2)=2⁵*3³*5¹=4320.

Cerinţă

Dându-se o ecp, să se determine costul acesteia.

Date de intrare

Fişierul de intrare ecp.in conţine pe prima linie expresia corect parantezată. Această expresie nu conţine niciun caracter spaţiu.

Date de ieşire

Fişierul de ieşire ecp.out va conţine costul x al ecp. Deoarece x poate fi un număr foarte mare, se vor afisa numai exponenţii factorilor 2, 3 si 5 din descompunerea în factori primi a lui x. Acesti exponenţi se vor afisa pe o singură linie, separaţi prin câte un spaţiu.

Restricţii

• Expresia din fisierul de intrare este o ecp. Lungimea ei este de cel mult 1000.

Exemplu

ecp.in	ecp.out	Explicaţii
()[(()){}()]	5 3 1	Costul ecp este 25*33*51
ecp.in	ecp.out	Explicaţii
([[[]]])	2 7 0	Costul ecp este 22*(33*(33*(3)))=22*37*50

prof. Dan Pracsiu

Liceul "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com