•filipb
|
|
« : Decembrie 24, 2008, 13:42:15 » |
|
Aici puteti discuta despre problema Heapuri.
|
|
|
Memorat
|
|
|
|
•jupanubv92
Client obisnuit
Karma: 19
Deconectat
Mesaje: 74
|
|
« Răspunde #1 : Iulie 09, 2009, 21:36:39 » |
|
Am doua surse care iau 100 de p si am facut un test care da rezultate diferite pe ambele surse . Ar trebui un pic imbunatatite testele sa vad si eu care e sursa gresita (stiu care e gresita dar ar trebui sa fiu atentionat si de evaluator ).Daca nu ma uitam la solutia oficiala eram convins ca prima sursa este corecta si puteam sa o busesc rau in timpul concursurilor. De exemplu pe testu asta prima sursa imi da 6 si a doua 5 si ambele au obtinut 100 de p . http://infoarena.ro/job_detail/330396http://infoarena.ro/job_detail/33042322 1 1 1 6 1 2 1 7 1 8 1 3 1 4 1 10 1 11 1 12 1 13 1 5 2 10 2 3 1 20 2 6 1 30 2 7 1 40 2 1 1 50 3
|
|
« Ultima modificare: Iulie 09, 2009, 22:05:48 de către Popescu Marius »
|
Memorat
|
|
|
|
•AnDrEwBoY
Strain
Karma: 4
Deconectat
Mesaje: 36
|
|
« Răspunde #2 : Iulie 10, 2009, 17:08:13 » |
|
Eu primesc pe sursa mea 5 si ma bazez pe acelasi sistem ca la a doua varianta Editat de admin: Foloseste butonul "Modifica"
|
|
« Ultima modificare: Iulie 10, 2009, 18:05:03 de către Andrei Grigorean »
|
Memorat
|
|
|
|
•jupanubv92
Client obisnuit
Karma: 19
Deconectat
Mesaje: 74
|
|
« Răspunde #3 : Iulie 11, 2009, 10:34:51 » |
|
Pai 5 este raspunsul corect .. doar am vrut sa atrag atentia ca sunt teste pe care unele surse de 100 de p iau incorect . Adica eu cand aveam o operatie de stergere inlocuiam nodul pe care vreau sa il sterg cu ultimul nod si micsoram numaru de elemente din heap si nu sa construit nici un test in care atunci cand trebuie sa sterg un nod sa fiu nevoit sa fac si upheap .
|
|
« Ultima modificare: Iulie 11, 2009, 20:38:48 de către Popescu Marius »
|
Memorat
|
|
|
|
•robigi
Strain
Karma: 5
Deconectat
Mesaje: 40
|
|
« Răspunde #4 : Noiembrie 18, 2009, 19:08:22 » |
|
salut, imi poate da cineva o idee de ce sursa asta : http://infoarena.ro/job_detail/365422?action=view-sourcela testul 7 unde ar trebui sa afiseze 1 2 3 ... 50001 mie mai afiseaza bine doar pana la aprox 33000 dupa care afiseaza gresit, deci ceea ce nu-nteleg eu cum poate merge corect pana la mai mult de jumatate cu acelasi algoritm si acelasi proces doar cu alte numere in plus in rest ia toate testele corect
|
|
|
Memorat
|
|
|
|
•popoiu.george
|
|
« Răspunde #5 : Ianuarie 27, 2010, 20:24:18 » |
|
Imi puteti spune cum ar trebui sa retin ordinea in care sunt introduse valorile?...Ca nu reusesc sa inteleg.
|
|
« Ultima modificare: Ianuarie 27, 2010, 21:32:52 de către Popoiu George »
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #6 : Ianuarie 28, 2010, 09:30:19 » |
|
Pai sa zic ca in v[ i ] ti minte al i-lea element In Heap[ i ] <- ti minte pozitia elementului din vectorul v, iar in vectorul Position[ i ] ti minte positia elementului i in Heap. Odata ce adaugi/stergi un element in Heap Position se va schimbat, trebuie sa vezi cum
|
|
|
Memorat
|
|
|
|
•popoiu.george
|
|
« Răspunde #7 : Ianuarie 28, 2010, 15:54:37 » |
|
Iti multumesc mult alexandru ! Chiar am inteles, si iti marturisesc ca daca nu imi explicai tu cred ca mai dura muulta vreme pana aflam ce semnifica acei vectori. Cred ca ar trebui comentate sursele oficiale de la problemele din arhiva educationala, deoarece unei persoane care nu are alte surse de informare ii este foarte greu (sau imposibil) sa inteleaga o sursa necomentata.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #8 : Ianuarie 28, 2010, 19:40:57 » |
|
Cred ca ar trebui comentate sursele oficiale de la problemele din arhiva educationala, deoarece unei persoane care nu are alte surse de informare ii este foarte greu (sau imposibil) sa inteleaga o sursa necomentata.
Da, n-ar strica niste mici comentarii ale surselor prezentate Dar din acelasi motiv presupun ca exista forumul
|
|
|
Memorat
|
|
|
|
•johsonsbabi
Strain
Karma: 2
Deconectat
Mesaje: 10
|
|
« Răspunde #9 : Februarie 18, 2010, 01:46:33 » |
|
ce face assert? e folosit de mai multe ori in sursa oficiala va rog ms
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #10 : Februarie 18, 2010, 06:32:45 » |
|
ce face assert? e folosit de mai multe ori in sursa oficiala va rog ms assert( conditie ) - daca conditia este falsa opreste din exectuie programul returnand o valoare de eroare. Este folosit pentru a vedea daca anumite valori respecta limitele impuse http://www.cplusplus.com/reference/clibrary/cassert/assert/
|
|
|
Memorat
|
|
|
|
•cezy
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #11 : Februarie 23, 2010, 20:37:53 » |
|
Cum as putea rezolva problema folosind priority_queue din stl ? practic cum pot sterge un el x cu priority_queue exista vreo functie ? caci pop imi sterge doar el de prioritate maxima sau se poate folosi si pt a sterge un el oarecare?
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #12 : Februarie 23, 2010, 23:09:37 » |
|
Priority Queue este o structura de data abstracta (poate fi implementate in mai multe moduri) ce permite doar operatiile push, pop si top. Deci nu-l poti folosi pentru ce vrei tu.
|
|
|
Memorat
|
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #14 : Decembrie 19, 2010, 00:11:05 » |
|
Cred ca e (si mai mult decat probabil) de la modalitatea in care afli "elementul intrat al x-lea in multime". Tu lucrezi in Heap direct cu valoarea elementelor si strici pozitia lor cronologica. Ceea ce trebuie sa faci e sa memorezi pentru fiecare element din sir pozitia lui in Heap si pentru fiecare element din Heap pozitia lui in sir.
|
|
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #15 : Decembrie 19, 2010, 09:15:52 » |
|
da dar cum, nu vad cum ar putea intra in memorie (nr sunt pana la 1000000000) deci nu pot lua un vector in care fac ap[v] = i;
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #16 : Decembrie 19, 2010, 11:20:57 » |
|
Te poti folosi ca informatie intermediara de numarul de ordine al operatiei de insert. Poti introduce aceste valori in heap, sa le compari in functie de valoarea efectiva (pe care o retii in alt vector) si sa mai tii un vector care iti spune pentru fiecare operatie pozitia curenta din heap.
|
|
|
Memorat
|
Am zis
|
|
|
•vladtarniceru
|
|
« Răspunde #17 : Decembrie 19, 2010, 14:16:45 » |
|
paul, tu vrei sa zici ca iau un vector v[] in care v[ i ] e al i-lea inserat si mai iau un vector t[] in care t[ i ] este pozitia in heap a celui de-al i-lea inserat? si daca e asa, ca sa fac elementul al 2-lea inserat sa zicem fac: int element = v[2]; int pozitie = t[2];
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #18 : Decembrie 19, 2010, 15:52:07 » |
|
M-am exprimat putin prost. Fie faci cum ai scris, dar atunci in heap tii al indicele operatiei la care a fost un element si compari elementele din heap folosindu-te de vectorul v. Fie folosesti vectorul v pe post de heap, dar atunci ca sa accesezi valoarea celui de-al i-lea inserat element, faci element = v[t[2]].
|
|
|
Memorat
|
Am zis
|
|
|
•vladtarniceru
|
|
« Răspunde #19 : Decembrie 19, 2010, 18:45:38 » |
|
acum am inteles ideea, dar iau 10 puncte cu sursa implementata asa i-am mai dat teste si ies toate, am facut si cu debuggerul ca sa fiu sigur ca trece bine in t[] si intr-adevar e bine , iar testele de la atasamente sunt cam mari .. as ramane recunoscator celui care m-ar ajuta multumesc
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #20 : Decembrie 19, 2010, 18:51:06 » |
|
Eu asa am facut: v[ i ]= elementul intrat al i-lea in multime (deci, practic sirul pe care il citesc) H[ i ]= pozitia in sirul v a elementului de pe pozitia i in heap poz[ i ]= pozitia in heap a elementului de pe poztia i in sirul v v[H[ i ]]= valoarea elementului de pe pozitia i in heap Si de aici lucrezi cu v[H[ i ]] cand compari valorile. Vectorul poz il folosesti ca sa stii instant care element il stergi. Nu poate fi chiar atat de greu daca si eu am inteles )
|
|
« Ultima modificare: Decembrie 19, 2010, 19:20:04 de către George Marcus »
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #21 : Decembrie 23, 2010, 11:31:56 » |
|
mi-a iesit in cele din urma, multumesc tuturor pentru ajutor totusi, cautarea aceea (sa cauti al i-lea elem intrat) nu se poate face si cu hashing?
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #22 : Decembrie 23, 2010, 15:08:28 » |
|
mi-a iesit in cele din urma, multumesc tuturor pentru ajutor totusi, cautarea aceea (sa cauti al i-lea elem intrat) nu se poate face si cu hashing? Nu cred ca se poate cu hashing... intr-un hash nu ai o ordine ...sunt random asezate in memorie
|
|
|
Memorat
|
|
|
|
•blue_phoenix
Client obisnuit
Karma: 0
Deconectat
Mesaje: 57
|
|
« Răspunde #23 : Noiembrie 10, 2011, 16:10:08 » |
|
Salut! Am tot incercat sa fac o sursa de 100p, dar iau TLE pe ultimele doua teste. sursa mea e aici http://infoarena.ro/job_detail/632209 . Nu-mi dau seama ce ar trebui sa fac s-o imbunatatesc. (am schimbat si citirea, acum e cu freopen, ca in sursa oficiala) Oarecum legat de subiect, intr-o prima versiune a programului heap-ul meu continea struct-uri (deci pentru push si pop, interschimbam obiecte de tip nod). Ia mai mult timp sa interschimbe doua struct-uri decat doua int-uri? sau totul se face la nivel de pointeri si deci ia la fel? Multumesc anticipat!
|
|
|
Memorat
|
|
|
|
•DraStiK
|
|
« Răspunde #24 : Noiembrie 10, 2011, 17:17:19 » |
|
E cam stransa limita de timp. Ca sa iti raspund la intrebare, teoretic lucreaza mai bine cu un tip cunoscut decat cu o structura. Ca sa obtii 100 de puncte poti incerca sa parsezi citirea.
|
|
|
Memorat
|
|
|
|
|