Fişierul intrare/ieşire:1expr.in, 1expr.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

1expr

Continutul acestei pagini nu este formatat conform recomandarilor de formatare.
Daca aveti permisiunile necesare, va rugam sa il imbunatatiti.

Gigel, student in anul II (desi a inceput facultatea acum 4 ani - ce sa-i faci, Electronica asta..), tocmai a invatat despre expresii aritmetice ce contin operatorii '+','*','^' si '!', precum si paranteze ('(' si ')'). Totusi, fiind abia in anul II, el se incurca cand trebuie sa lucreze cu numere prea mari, de aceea singurul numar care apare in mod direct (adica nu doar ca rezultat al unei operatii) in cadrul unei expresii este numarul 1. Vom numi o astfel de expresie 1-expresie. De exemplu, "(1+(1*1))^(1+1+1*1)^(1+(1+1)!)" este o 1-expresie, dar "2+5*7+6!+3^4^3!+1*6" nu este o 1-expresie (deoarece apar in mod direct numerele 2, 3, 4, 5, 6 si 7). O 1-expresie poate fi privita ca un sir format din caracterele '1','+','*','^','!','(',')' si care poate fi descris cu ajutorul urmatoarelor reguli gramaticale:

1-expresie =

  • '1'
  • '(' 1-expresie ')'
  • 1-expresie '+' 1-expresie
  • 1-expresie '*' 1-expresie
  • 1-expresie '^' 1-expresie
  • 1-expresie '!'

Desi in cadrul expresiei apare in mod direct doar numarul 1, rezultatele evaluarii operatiilor pot fi numere mai mari decat 1, astfel ca Gigel va trebui sa invete sa foloseasca si aceste numere. Pentru a evalua o expresie aritmetica, trebuie cunoscute prioritatile operatorilor.

  • Operatorul cu cea mai mica prioritate este '+' si realizeaza operatia de adunare. Rezultatul 1-expresiei "1+1+1" este 3.
  • Operatorul '*' este mai prioritar decat operatorul '+' si realizeaza operatia de inmultire. Rezultatul 1-expresiei "1+1*(1+1)*(1+1+1)+(1+1)*(1+1)" este 1+1*2*3+2*2=1+6+4=11. Operatorul '^' este mai prioritar decat operatorii '+' si '*' si realizeaza operatia de ridicare la putere (A^B reprezinta A ridicat la puterea B). Rezultatul 1-expresiei "(1+1)*(1+1+1)^(1+1)*(1+1+1)+(1+1)" este 2*3^2*3+2=2*9*3+2=54+2=56.
  • Spre deosebire de operatorii '+' si '*' care au proprietatea ca A+B=B+A si A*B=B*A, in cazul '^' nu este neaparat adevarat ca A^B=B^A (decat in unele cazuri speciale). O alta particularitate a acestui operator este ordinea de aplicare in cazul absentei parantezelor: el este asociativ dreapta. De exemplu, A^B^C^D este echivalent cu A^(B^(C^D)). Rezultatul 1-expresiei "(1+1)^(1+1)^(1+1+1)" este 2^2^3=2^(2^3)=2^8=256 si nu (2^2)^3=4^3=64. Astfel, daca exista mai multi operatori '^' neseparati de paranteze, ordinea de efectuare a operatiilor este de la dreapta catre stanga.
  • Operatorul cu prioritatea cea mai mare este '!' si realizeaza operatia "factorial". Rezultatul 1-expresiei "(1+1+1)!" este 3!=6. Factorialul unui numar X, notat X!, este definit ca fiind 1*2*..*X. Rezultatul 1-expresiei "(1+1)*(1+1+1+1)!^(1+1+1)!!" este 2*4!^3!!=2*(4!)^(3!!)=2*(4!)^((3!)!)=2*24^(6!)=2*(24^720) (rezultatul este un numar prea mare pentru a fi afisat aici).

Lungimea unei 1-expresii este definita ca fiind egala cu numarul de caractere ale sirului ce reprezinta 1-expresia. Lungimea 1-expresiei "(1+1)!^(1+1)*(1+1)+1" este 20. Tema pe care a primit-o Gigel la scoala este urmatoarea: dandu-se un numar N, gasiti o 1-expresie de lungime minima al carei rezultat sa fie egal cu N. Ajutati-l pe Gigel sa isi rezolve tema.

Date de Intrare

Prima linie a fisierului de intrare 1expr.in contine numarul intreg T. Pe urmatoarele T linii se afla cate un numar intreg N.

Date de Iesire

In fisierul de iesire 1expr.out veti afisa T linii. Pe a K-a linie veti afisa o 1-expresie de lugime minima al carei rezultat este egal cu al K-lea numar dintre cele T date in fisierul de intrare. Daca exista mai multe 1-expresii de lungime minima, puteti afisa oricare dintre ele.

Restrictii si precizari

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 38

Exemplu

1expr.in1expr.out
3
1
3
200
1
1+1+1
(1+1)^(1+1+1)*(1+(1+1+1+1)!)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content