Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 13:30:17.
Revizia anterioară   Revizia următoare  

 

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

Vezi solutiile trimise | Statistici

1expr

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.
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
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.
)" este o 1-expresie, dar "2+5*7+6!+3
43!+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' sau `(` 1-expresie `)' sau 1-expresie `+' 1-expresie sau

1-expresie `*' 1-expresie sau 1-expresie `^' 1-expresie sau

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 (AB reprezinta A ridicat la puterea B). Rezultatul 1-expresiei "(1+1)*(1+1+1)(1+1)*(1+1+1)+(1+1)" este 2*32*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 AB=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, ABCD este echivalent cu A(B(CD)). Rezultatul 1-expresiei "(1+1)(1+1)(1+1+1)" este 223=2(23)=28=256 si nu (22)3=43=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

o 1 ≤ T <= 100
o 1 <= N <= 3^8

Exemplu

1expr.in1expr.out
31
11+1+1
3(1+1)^(1+1+1)*(1+(1+1+1+1)!)
200

References

Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/1expr/enunt_files/filelist.xml

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?