infoarena

Aici puteţi discuta despre problema Trompeta (http://infoarena.ro/problema/trompeta).

         Cu deque iau 70p +3 tle. Mai trebuie ceva optimizari?

Asa iau si eu, primele 7 teste.Am implementat stiva ca un vector, poate fi de la asta  ???

Si eu am facut cu deque si am tle pe ultimele 3. Probabil ca si tu folosesti 6 mega de memorie ca mine... si chestia asta cu memoria+operatiile pe deque mananca mai mult timp... solutia mai rapida ar fi aia descrisa in articol, cu stiva. Ea foloseste doar vreo 2 mega de memorie si e mai scurta si mai buna. Succes. :)

Poate sa-mi dea si mie cineva un exemplu de rulare mai marisor decat cel oficial, va rog?

Am facut tot un fel de stiva, jucandu-ma cu pointeri. E prima mea experienta cu pointeri in C, si desi se pot folosi mai eficient decat in Pascal, spre ex, lasa loc liber erorilor. Exceptand TLE-ul de la ultimele 3, imi iau incorrect la celelalte (si 2 Blocked system call: kill. ??), deci mai mult ca sigur e o greseala de implementare.

Deci... aveti vreun exemplu mai cuprinzator pe care sa-mi pot debug-ui programul?

15 9
293658888722814

988887814

          A luat cineva 100p cu sursa in pascal?

Mersi pauldb.

Am descoperit ca sunt blonda. "Ordine initiala" nu inseamna deci neaparat consecutive... adica se poate sari peste niste note... Back to the drawing board...

Pana acum nu...

http://infoarena.ro/job_detail/86753

E cam greu de luat 100 in pascal datorita operatiilor IO. La C/C++ timpul masurat e cel de CPU pe cand la pascal daca se scrie/citeste mult, timpul masurat de evaluator e aproape de cel real. Cam ce a trebuit facut sa mearga:


Editat de moderator: sa nu fim prea expliciti

Incearca sa postezi doar partile de cod care au legatura cu optimizarea, nu cu algoritmul de rezolvare a problemei :). Altfel ar exista riscul ca unii membri sa dea un simplu copy/paste si sa ia 100.

Pentru exemplul


Rezultatul este


?

Trebuie sa afisezi M cifre, deci corect e

Ce optimizari as mai putea aduce la solutia cu stiva? Iau TLE pe ultimele 3 teste. (am implementat stiva din STL deci nu cred ca de acolo e problema)  :sad:

http://infoarena.ro/job_detail/297112

 :shock: problema asta e cam aceasi cu alibaba

Defapt e chiar identica... doar ca la trompeta din N cifre trebuie alese M si la Alibaba din N cifre trebuie sterse K. Si totusi de ce i-au TLE?

Am o problemă, am făcut problema cu o stivă, iar vectorul şi stiva i+am făcut de tip char, însă tot nu reuşesc sa scap de 3 tle. Îmi poate da şi mie cineva un indiciu?

Eu am scapat de TLE pe ultimele 3 teste cand am schimbat citirea caracter cu caracter, in citirea unui vector char, si parcurgerea lui.  :)

 :? salut.. am luat 100 de puncte pe problema asta si am observat ca nu-mi merge pentru un test (dat de mine)
cod:
5 4
54321
imi afiseaza 54321 si corect este 5432

ar trebui modificat sau adaugat si un test pentru cazul asta?:-?? (cand sirul este descrescator) :-k :-' :)

Salut!
Eu nu înţeleg cam cum s-ar comporta soluţia cu stivă ( de aici: [1] ) pe un input de genul (deoarece elimină vârful stivei doar când dă peste numere mai mari decât acesta):

Dacă am schimba abordarea, astfel încât să adauge la stivă şi numerele egale cu cel aflat în vârful stivei, atunci soluţia ar rata inputuri de forma:

Poate să mă lămurească cineva?

[1] http://infoarena.ro/autumn-warmup-2007/solutii/runda-2 (http://infoarena.ro/autumn-warmup-2007/solutii/runda-2)

Ambele exemple date de tine au raspunsuri gresite.
Tu tre sa alegi din sirul acela un numar cat mai mare, format din M cifre, si cifrele trebuie sa ramana in ordine.

Rationamentul e urmatorul: cand poti schimba o cifra cat mai semnificativa cu una mai mare, o schimbi.
Cand o poti schimba? Cand iti mai raman destule cifre ca sa completezi numarul.

Greşeala mea a fost că am crezut că e vorba de un if, dar era vorba de un while.

(stiu ca nu s-a mai postat de mult)
Tot obtin 70pct cu TLE si am incercat de toate : stack din STL,vector din STL,stiva obisnuita(vector char cu un int vf=-1),am despartit for-ul in doua ca sa pot elimina la fiecare cate o conditie din while-ul care imi scoate din stiva,am pus locale sirul si stiva ca sa le acceseze mai rapid,si tot iau 70  ](*,)  Poate sa ma ajute cineva cu 100pct? (sa-i dau sursa prin PM sa vada ce se poate optimiza)


L.E. : s-a rezolvat  :D

Un ajutor pentru optimizare daca o pot numi asa. Am incercat stiva implementata "manual" stiva din stl sirul citit ca un sir de caractere dar degeaba i`au doar 70 de pct cu tle pe ulltimele 3.

Eu luam TLE pe ultimile trei teste cind scriam rezultatul caracter cu caracter, iar cind am retinut solutia intr-un vector si l-am afisat pe tot deodata a mers  :-'

Ideea lui ctlin04 e geniala.
Tine-ti stiva ca un vector de char si afiseaza-l deodata si ia 100 p.  :thumbup:

ce se intampla cand nu pot imbunatatii rezultatul? adaug numerele in continuare? si care este complexitatea optima?

Am lucrat cu vectori din stl si imi dadea 70 afisand element cu element.
Daca afisati geva gen:
"
string strC(vec.begin(), vec.end());
  cout << "Here is strC, which is constructed from a vector:\n";
  cout << strC << endl;
"
primiti 100

Afisarea are legatura cu iteratorii sau cv de genu. Nu stiu daca se putea optimiza altceva, pur si simplu operezi pe o stiva.

pentru exemplul:

20 7
38942095073801240576

nu ar trebui sa dea: 8997876?  :-k
vreau sa ma asigur daca am inteles bine exemplul initial pentru ca pare prea naspa.

raspunsul corect este
9984576