293 Expresii min-max

[ditzone]

Aici puteţi discuta despre problema Expresii min-max.

[•cristy]

va rog...dati un exemplu mai complicat...sa vad ce nu imi iese...iau 40 de pct....restu WA

[•Binary_Fire]

Fii atent la codurile pe care le-ai atribuit operatorilor 'm' , 'M' si parantezelor, s-ar putea sa fie aceleasi cu unele numere din fisier.   
Uite si un mic test:

Cod:

Input:
((345m(3)m(56m(3M(8m4)))))M(343m93M(((5m4))))

Output:
93

Nu prea sunt teste complicate , trebuie doar sa fi atent la implementare. Sper sa ajute.

[•bogdan88]

Buna am facut si eu problema asta si am o mica problema. Iau TLE la 7 teste ma poate ajuta cineva? id-ul meu de mess este bogdanpopescu88

[•peanutz]

7 TLE? Faci recursivitate? Adica cum dai de o "(" mai apelezi odata functia care rezolva o expresie gen "5m3M1"? Chiar nu vad cum ai putea sa iei TLE, mi se pare destul de liniara treaba

Later edit: Vezi sa nu-ti ruleze la infinit pe anumite cazuri, mai fa niste teste.

[•bogdan88]

Da asa am facut.....cand am gasit o paranteza am apelat inca o data functia

[•cos_min]

Atunci incearca un test de genu

Cod:

(((((((((7M8)))))))))

[•bogdan88]

Am folosit recurenta! Am testat si cu teste de genu cum ai spus Cosmin, imi da bine, dar depaseste timpu.....ce pot face pt a optimiza? id-ul meu de mess este bogdanpopescu88

[•bogdan88]

Ma ajuta si pe mine cineva?

[•Dastas]

Poate te ajuta http://en.wikipedia.org/wiki/Shunting_yard_algorithm. Poti transforma sirul in notatie poloneza, care se evalueaza foarte usor si intra in timp.

[•gabitzish1]

Unul dintre exemplele din enunt este
12m23M13m192)M(90m89m88m87)m((298M7)M2)     si raspunsul e 87....

nu ar trebui sa fie parantezat corect,  avand in vedere ca prima paranteza intalnita este ")" ?

[•DITzoneC]

Ba da, am corectat.

[•bogdan88]

M-am saturat am facut problema in toate felurile si iau TLE (numa 65 de puncte). Imi poate da si mie cineva vreo idee cum o pot face fara sa mai iau TLE? (cineva care a facut-o va rog)

[•Dastas]

Ti-am dat un link unde practic ai algoritmul de rezolvare... ai incercat sa-l implementezi?

[•bogdan88]

De transformat in expresie poloneza e usor...dar imi spui dup-aia cum fac? ca imi va depasi timpul daca fac cu un vector

[•Dastas]

Pai descrie exact cum faci. Transformarea o faci nerecursiv, iar evaluarea la fel. Pentru evaluare iti mai iei o stiva, parcurgi vectorul in care ti-ai format sirul in notatie poloneza, iar in momentul in care pui un operator in acea stiva, vei avea operanzii deja adaugati, deci ii scoti din stiva, calculezi, adaugi rezultatul inapoi in stiva, iar la sfarsit stiva va contine o singura valoare: rezultatul care te intereseaza.

Ideea asta e, cu asta am luat 100... poate te complici pe undeva, da si tu mai multe detalii si incerc sa te ajut.

[•peanutz]

Sau in aproape orice culegere gasesti evaluarea unei expresii(folosind recursivitate)... e cam aceeasi chestie, daca urmezi modelu' iti iasa sigur!

[•bogdan88]

Deci eu am incercat asa: am facut o procedura care sa calculeze rezultatul de la pozitia i pana la j. cand am dat de o paranteza deschisa am apelat procedura, dupa care stergeam tot ce era in paranteza din sir si adaugam numai rezultatul.......programul mergea foarte bine numai ca imi da TLE la 7/20 de teste

[•peanutz]

Eu am o variabila i globala  care imi zice pana la ce pozitie am evaluat, si o functie recursiva care returneaza rezultatul pana in acel moment daca  intalneste ')' sau daca i = n. Ea rezolva o operatie gen 1m2, sau 4M5, si daca da peste o situatie gen 1m(...... face rez = min(rez, solve()), inainte sa apelez solve() trec cursorul i dupa '(' .. Deci am O(n), atat doar ca se cam incarca stiva. Sper ca ai inteles, asa tre sa mearga. 

[•Dastas]

Desi cel mai elegant e cu notatie poloneza Si trebuie sa intre in timp.

[•bogdan88]

Am implementat in expresie poloneza asa cum mi-ai spus...si de ex pt testul 178m66m234M89m54M13M22m67 in expr poloneza da 178 66 234 89 54 13 22 67 m M M m M m m nu? e bine pana acum.......si acum daca evaluez expresie si iau pentru fiecare m sau M intalnit numerele cele 2 din fata imi da alte rezultate decat cele de la teste!!! Ce nu e bine? Unde gresesc?

[•Dastas]

Nu e buna forma poloneza, citeste mai cu atentie algoritmul. Trebuie sa-ti dea 178 66 -1 234 -1 89 -2 54 -1 13 -2 22 -2 67 -1, unde -1 = m, -2 = M. Operatorii au aceeasi prioritate.

[•GrammerProf]

Chiar daca nu are legatura cu subiectul in discutie, vreau si eu sa stiu cum pot accesa solutii ale problemelor din arhiva.  M-am lovit de urmatorul mesaj in incercarea mea de a ma uita la evaluator (nu stiu daca e unul si acelasi lucru cu rezolvarea unei p robleme):

"Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ..."

Si normal ca asa-zisa
"redirectare" nu a mai avut loc.

Multumesc anticipat,
Bogdan.

[•Florian]

Calmeaza-te! Probabil problema urmeaza sa fie pusa in arhiva. De fapt, problemele. Akum cred k se fak ultimile "retusuri". 

[•sima_cotizo]

Chiar daca nu are legatura cu subiectul in discutie, vreau si eu sa stiu cum pot accesa solutii ale problemelor din arhiva.  M-am lovit de urmatorul mesaj in incercarea mea de a ma uita la evaluator (nu stiu daca e unul si acelasi lucru cu rezolvarea unei p robleme):

Daca zici ca vrei sa accesezi solutii ale altor concurenti, nu ai voie din cate stiu eu...  Daca e vorba de solutia ta, atunci e o problema... asta o primesc si eu uneori, e posibil sa fi modificat oarecum regulile legate de securitate de pe site ... Si redirectarea trebuie sa vina, nu te duce pe pagina principala?