Fișierul intrare/ieșire pom.in, pom.out Sursă Baraj Sumen 2013 juniori runda 2
Autor Cristian Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 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.

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.

Date de intrare

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, ti și numărul de ramuri R[ti] î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ă).

Date de ieșire

Î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.

Restricții

  • 1 ≤ N ≤ 26
  • ‘a’ ≤ ti ≤ ‘z’ pentru 1 ≤ i ≤ N
  • 0 ≤ R[ti] ≤ 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

Exemplu

pom.in pom.out
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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii