528 Trompeta

[•wefgef]

Aici puteţi discuta despre problema Trompeta.

[•gurney]

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

[•coderninu]

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

[•CezarMocan]

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.

[•valkyria]

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?

[•pauldb]

Cod:

15 9
293658888722814

Cod:

988887814

[•gurney]

          A luat cineva 100p cu sursa in pascal?

[•valkyria]

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...

[•gabitzish1]

          A luat cineva 100p cu sursa in pascal?

Pana acum nu...

[•gogu]

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:

Cod:

var i,k,n,m:longint;
a,st:array[1..1 shl 20] of char;
f:file of char;
begin
assign(input,'trompeta.in'); reset(input);
assign(f,'trompeta.out');rewrite(f,1);
readln(n, m);
readln(a);
... 
blockwrite(f, st, m);
close(f);
end.

Editat de moderator: sa nu fim prea expliciti

[•wefgef]

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.

[•pheon23]

Pentru exemplul

Cod:

6 5
009090

Rezultatul este

Cod:

9090

?

[•stef2n]

Trebuie sa afisezi M cifre, deci corect e

Cod:

09090

[•gabor_oliviu1991]

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) 

http://infoarena.ro/job_detail/297112

[•hysep]

  problema asta e cam aceasi cu alibaba

[•gabor_oliviu1991]

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?

[•funkydvd]

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?

[•gabor_oliviu1991]

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

[•bugy]

  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)

[•mordred]

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):

Cod:

Exemplu #1:
7 3
9999911
Output:
911

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:

Cod:

Exemplu #2:
7 3
5555999
Output:
559

Poate să mă lămurească cineva?

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

[•gabitzish1]

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.

[•mordred]

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

[•scipianus]

(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 

[•vendetta]

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.

[•ctlin04]

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