Fişierul intrare/ieşire:pom.in, pom.outSursăBaraj Sumen 2013 juniori runda 2
AutorCristian FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inpom.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 sa te autentifici pentru a trimite solutii. Click aici