== include(page="template/taskheader" task_id="pom") ==
În grădina lui Ion a crescut peste noapte Pomul de Halloween, fratele cel rău al Pomului de Crăciun. Ion, fiind șomer și având mult timp liber, a studiat copacul și a observat că există doar câteva tipuri de ramuri, pe care le-a codificat prin litere mici ale alfabetului (ca toți românii, Ion nu folosește diacritice). Toate ramurile de același tip $t$ se despart în alte $R[t]$ ramuri. Ion a codificat arborele astfel:
!>problema/pom?tree.png!
* O ramură terminală se codifică doar prin tipul ei
* O ramură interioară se codifică prin tipul ei, apoi o paranteză deschisă, apoi descrierile subarborilor despărțite prin virgule, apoi o paranteză închisă
În grădina lui Ion a crescut peste noapte Pomul de Halloween, fratele cel rău al Pomului de Crăciun. Ion, fiind șomer și având mult timp liber, a studiat copacul și a observat că există doar $N$ tipuri de ramuri, pe care le-a codificat prin litere mici ale alfabetului (ca toți românii, Ion nu folosește diacritice). Toate ramurile de același tip $t$ se despart în alte $R[t]$ ramuri. Ion a codificat arborele astfel:
* O ramură terminală se codifică doar prin tipul ei.
* O ramură interioară se codifică prin tipul ei, apoi, între paranteze și despărțite prin virgule, codificările subarborilor.
* Ramurile sunt întotdeauna enumerate de la stânga la dreapta.
Apoi, Ion s-a apucat să taie copacul, ca să aibă lemne de foc. Ca să nu se prindă Primăria, Ion taie ramurile una câte una. Când are mai multe variante, o alege pe cea mai din stânga. Să se afle ce tipuri de ramuri va obține Ion, în ordine.
Pentru imaginea alăturată, $R[f]$ = 3, $R[g]$ = 1, $R[h]$ = 2, $R[i]$ = 0, $R[k]$ = 1, $R[x]$ = 0, $R[y]$ = 0, iar codificarea arborelui este $f(g(x),h(i,g(y)),k(h(f(x,y,y),i)))$ .
Apoi, Ion s-a apucat să taie copacul, ca să aibă lemne de foc. Ca să nu se prindă Primăria, Ion taie doar ramuri terminale, una câte una. Când are mai multe variante, o alege pe care apare prima în codificare. Să se afle ce tipuri de ramuri va obține Ion, în ordine.
h2. Date de intrare
Fișierul de intrare $pom.in$ ...
Fișierul de intrare $pom.in$ conține, pe prima linie, numărul N de tipuri de ramuri. Următoarele $N$ linii conțin tipul unei ramuri, $t[~i~]$ și numărul de ramuri $R[t[~i~]]$ în care se ramifică acest tip, separate printr-un spațiu. Ultima linie a fișierului conține codificarea arborelui. Aceasta poate conține litere mici, paranteze rotunde, virgule și spații. Spațiile trebuie ignorate. Fișierul se termină cu un caracter $\n$ (linie nouă).
h2. Date de ieșire
În fișierul de ieșire $pom.out$ ...
În fișierul de ieșire $pom.out$ se vor scrie, lipite, tipurile de ramuri în ordinea tăierii. Linia va fi încheiată cu un caracter $\n$ (linie nouă). Dacă Ion și-a notat greșit codificarea arborelui, în fișier trebuie scris numărul -1.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 26$
* $'a' ≤ t[~i~] ≤ 'z'$ pentru $1 ≤ i ≤ N$
* $0 ≤ R[t[~i~]] ≤ 100.000$ pentru $1 ≤ i ≤ N$
* Lungimea codificării, cu spații cu tot, este cel mult 100.000
* Toate cele $N$ tipuri de ramuri sunt distincte
h2. Exemplu
table(example).
|_. pom.in |_. pom.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
| 7
f 3
g 1
h 2
k 1
x 0
y 0
i 0
f(g(x),h(i, g(y) ), k ( h(f(x,y,y),i)))
| xgiyghxyyfihkf |
| 2
f 1
x 0
f(g(x))
| -1 |
| 2
f 1
x 0
f(x,x)
| -1 |
| 2
f 3
x 0
f(x,
| -1 |
== include(page="template/taskfooter" task_id="pom") ==
== include(page="template/taskfooter" task_id="pom") ==
