121 Expresii algebrice

[ditzone]

Aici puteţi discuta despre problema Expresii algebrice.

[•PuMa]

Cat e rezultatul pentru testul "((1))" si ce conditii trebuie puse pentru ca expresia sa fie incorecta?? Eu am luat cazurile:
-"+)", "(+", "(*", "*)", "++", "**", "()", ")(". De asemenea verificam pentru fiecare prefix al expresiei ca numarul de paranteze ')' sa fie mai mic sau egal cu numarul de paranteze. '('  

[u-92]

pentru (((1))) imi da 1.. eu am verificat in timpul calculului daca e corecta.. ai folosit tipuri de date pe 64 biti ?

[•PuMa]

hmmm. si mie tot atat imi da si am folosit long long.  

[u-92]

uite un test, poate te ajuta

Cod:

1
(1+2*(3+5*9+4)*3*4)*(2+3)*5*5*5*((5))+3+4+5+6*7

Cod:

5880

[•PuMa]

Ms mult! testu m-a ajutat fff mult. Eu nu evaluam ultima parte a expresiei.  

[•cypry]

Am rezolvat problema, pe toate cazurile incercate imi da bine, dar cand trimit solutia, apare un singur test, la care scrie Incorect. Nu pot sa bag mana in foc ca am rezolvat corect, dar e normal sa aiba un singur test?

[•astronomy]

Da, problema a fost data la un concurs pe infoarena si toate problemele de atunci aveau un singur fisier de test.

[•Marius]

Vrea sa imi spuna cineva o idee ?

[•pauldb]

Dinamica pe intervale. Pot sa mai detaliez daca vrei.

[•Marius]

Mai povesteste-mi.

[•pauldb]

Tinem o dinamica C[p][q] = numarul de posibilitati de a evalua expresia pe intervalul p,q.
C[p][q]=C[p+1][q-1], daca A[p]='(' si A[q]=')'. Daca nu, cautam semnul cu prioritatea cea mai mica din interval (evident, care nu e inclus intr-o paranteza). Apoi parcurgem intervalul si de fiecare daca cand gasim semnul pe o pozitie k, adunam la C[p][q] produsul C[p][k-1]*C[k+1][q]. 

[•danalex97]

Iau WA. Am rezolvat problema cu o dinamica si m-am uitat in solutia oficiala. Ideile coincid , deci ma gadesc ca ideea de baza e buna. (imi dau toate exemplele din enunt si cele date mai sus la comentarii).

La verificarea corectitudinii unei expresii eu verific sa nu am "(*" , "*)" , "(+" , "+)" , "()" , ")(" , "++" , "**" , "+*" , "*+" , ")0". Daca mi-a scapat ceva sa spuneti. De asemenea ma uit la perecile de paranteze sa fie puse corect.
 
Are idee cineva ce particularitati ar mai avea problema asta ?

[•AlexandruValeanu]

Cat ar trebui sa dea pe testul acesta:

Cod:

9
+3+2
3*(+2)
(2*3)*(3*(3+3)+2)+9+(2+3+(((3+2))))
2++3
+1
(3)*(1)+(1)*(2)+(3)
(+2)
3+(3+4+(1+1+1*(3+4)))+(8+0*(3+3))
(1+2*(3+5+9+4)*3*4)*(2+3)*5*5*5*((5))+3+4+5+6*7

[•misino]

Mie imi da:

Numarul de arbori = 0.
Numarul de arbori = 0.
Numarul de arbori = 4.
Numarul de arbori = 0.
Numarul de arbori = 0.
Numarul de arbori = 2.
Numarul de arbori = 0.
Numarul de arbori = 8.
Numarul de arbori = 14700.

Imi da si mie cineva un test in care raspunsul sa depaseasca int?

[•FlorinHaja]

Raspunsurile depasesc unsigned long long-ul?

Ca pe testul
1
2*3*4*5*6*7*2*3*4*5*6*7*2*3*4*5*6*7*2*3

imi da 1, iar pe
1
2*3*4*5*6*7*2*3*4*5*6*7*2*3*4*5*6*7*2

477638700.

[•klamathix]

Păi e parte din soluție să-ți răspunzi la asta. Sau în orice caz, îți îmbunătățește înțelegerea subiectului. Ți-ai găsit worst case-ul: toți operatorii au aceeași prioritate și orice arbore binar cu acel număr de noduri este corect. Cum poți număra câți arbori binari cu N noduri există? Cât dă pentru 24? (nu poți avea mai mulți operatori de atât). Dacă nu-ți iese număratul de arbori, e o chestie destul de cunoscută, o găsești ușor. Dar încearcă singur  .