Clasa a IX-a
Ziua 2
Problema 5

Fractii

Se considera primele N (1<=N<=26) litere mari din alfabetul englez, care reprezinta nume de variabile. Aceste litere se scriu succesiv in ordine alfabetica, delimitate prin operatorul de impartire ":", formand o expresie algebrica. Prin eventuala adaugare la aceasta expresie a unor perechi de paranteze rotunde se obtine o fractie etajata. Fractia poate fi scrisa, in urma eliminarii etajelor, sub forma unei fractii simple (care are la numarator, respectiv numitor, cate un produs de variabile). Cunoscand setul de litere care formeaza produsul de la numarator, se cere sa se indice o modalitate de a aseza parantezele.

Date de intrare: Fisierul text FRACTIE.IN contine doua linii. Pe prima linie se afla N (numarul de litere folosite), iar pe a doua se afla un sir de litere mari, distincte, ordonate alfabetic, fara spatii, reprezentand variabilele de la numarator. Datele de intrare se presupun corecte.

Date de iesire: Fisierul text FRACTIE.OUT contine pe o singura linie expresia cu paranteze, fara nici un spatiu.

Observatii:
1. Expresia trebuie sa fie corect parantezata.
2. Daca nu exista solutie, fisierul de iesire va fi format dintr-o singura linie cu mesajul:
NU

3. Daca exista mai multe solutii, se va tipari in fisierul de iesire una singura.

Exemplu:
Fisierul FRACTIE.IN contine:
5
ACE

Fisierul FRACTIE.OUT poate contine, de exemplu, expresia:
A:(B:(C:D):E)

Timp maxim pentru un test: 5 secunde.
Punctaj: 50 puncte.