infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Filip Cristian Buruiana din Decembrie 06, 2008, 19:51:13

Titlul: 023 Trie
Scris de: Filip Cristian Buruiana din Decembrie 06, 2008, 19:51:13

Aici puteti discuta despre problema Trie (http://infoarena.ro/problema/trie).

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Mihai Alex Ionescu din Decembrie 30, 2008, 18:40:50

pt cei ce folositi streamuri si eventual nu luati 100 aveti grija la citire ... ceva genul

Cod:

while(!fin.eof()) 
 fin>>op>>cuv

poate cauza buguri de ex daca nu gaseste cifre/caractere compatibile sau ajunge la sf fisierului si atunci citirea nu mai are loc si raman vechile valori si algoritmul le foloseste pe acelea / calc de 2 ori pt aceleasi valori ... pt aceasta prob puteti folosi ceva gen

Cod:

if( fin.good() ) { op1() op2() etc}

acest mic detaliu a facut la mn dif dintre 30p si 100p

[edit] e o idee buna sa faci bucatile de cod vizibile folosind tagul "[ code ]"

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Alexandru-Iancu Caragicu din Martie 21, 2010, 12:56:53

De ce nu s-au reglat restrictiile problemei sa suporte cei 50MB limita, pt ca testele de evauare sa fie de toate genurile, nu neaparat omogene. Mi se pare ciudat sa favorizezi o metoda de rezolvare prin intermediul testelor.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Paul-Dan Baltescu din Martie 21, 2010, 13:12:24

Aceasta problema este in scop educational. Este normal sa fie evidentiata o anumita rezolvare pe care le-o propunem ca exercitiu utilizatorilor.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Dragos din Iulie 04, 2010, 21:11:31

A mai luat cineva 100 folosind '\n' in afara de Lucian?
Eu iau 0 puncte asa si 100 daca folosesc strlen() sau '\0'.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Lucian Boca din Iulie 04, 2010, 22:25:39

Te referi, probabil, la caracterul in functie de care te opresti din recursivitate, iar asta e un detaliu strict legat de implementarea algoritmului tau.
Trebuie sa te uiti mai atent peste notiunile de null-terminated string (http://en.wikipedia.org/wiki/String_(computer_science)#Representations) si line break (http://en.wikipedia.org/wiki/Newline#In_programming_languages) si vei vedea ca iti vei putea face sursa, cu cateva modificari minore de indici, sa functioneze si cu '\n' :wink:

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Dragos din Iulie 05, 2010, 11:20:12

Citat din mesajul lui: Lucian Boca din Iulie 04, 2010, 22:25:39

Am inteles de ce mergea la tine, fgets citeste si '\n', iar .getline() citeste '\n' dar il da afara dupa.
La ce te referi prin "indici"?

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Lucian Boca din Iulie 05, 2010, 15:20:22

Nu m-am uitat atent peste funcia ta de citire, imi pare rau.
Initial crezusem ca e vorba despre cum accesezi caracterele in array-ul in care le memorezi, facand un pas suplimentar pentru a trece de la '\n' la '\0'.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Dragos din Iulie 05, 2010, 16:03:28

Citat din mesajul lui: Lucian Boca din Iulie 05, 2010, 15:20:22

Nu-i nici o problema! :ok:

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Nicolae Titus din Iulie 19, 2010, 22:13:42

La metoda bruta stergerea nu e O(L*N) ?

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Zabolai Zsolt din Iulie 22, 2010, 14:36:29

"Pentru toate operatiile, cuvantul w este format din maxim 20 de caractere din intervalul 'a'..'z'"
Ar trebui corectat, ca testele contin si numere...

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Gabriel Bitis din Iulie 22, 2010, 15:12:07

M'am uitat peste cateva teste si nu am vazut cifre in interiorul cuvintelor. Care teste contin cifre?

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Zabolai Zsolt din Iulie 22, 2010, 18:13:49

scz am gresit eu... miam dat seama care era problema...
Asa apare la mine in notepad: 0 ab0 abac3 qfksxe2 (...) De fapt notepadul era de vina, ca in alte aplicatii se vede normal...

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Petru Trimbitas din Septembrie 20, 2010, 19:08:34

~~La problema iau 30 de puncte cu multe sigsegv si incorecturi. Banuiesc ca e din cauza citirii deoarece atunci cand nu am newline la sf fis. merge orice test. Citesc asa:~~

Cod:

for( ;!f.eof();f.get()) {
        f>>ce;
        f.getline(cuv,50);
        if(cuv[strlen(cuv)]!='\0')
            cuv[strlen(cuv)]='\0';
        if(!ce) t->insert(t,cuv);
        else if(ce==1) t->del(t,cuv);
        else if(ce==2) g<<t->query(t,cuv)<<'\n';
        else if(ce==3) g<<t->prefix_comun(t,cuv,0)<<'\n';
    }

sursa e asta:http://infoarena.ro/job_detail/486230?action=view-source

Ma poate ajuta cineva sa o fac sa mearga de 100?
Nu mai am nevoie. Celor carora nu le iese sa foloseasca

Cod:

if(fin.good){
switch (op) etc
}

(daca fol streamuri de c++)

Titlul: RÄƒspuns: 227 Geometrie
Scris de: livica din Februarie 04, 2011, 14:01:11

Stie cineva ce face *s - 'a' ?
Ca eu nu inteleg.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Paul-Dan Baltescu din Februarie 04, 2011, 20:51:32

Inseamna a cata litera din alfabet e caracterul catre care indica pointer-ul s.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: livica din Februarie 05, 2011, 15:53:55

Merci!
Mi-am dat si eu seama de asta la scurt timp dupa ce am pus intrebarea.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Cristian Lambru din Iulie 08, 2011, 22:42:52

Salut :) !

Ma puteti ajuta si pe mine va rog, sa inteleg care este problema implementarii mele? Iau numai 10 puncte, cu toate ca am luat cateva teste, le-am comparat si toate rezultatele imi dau ok :) .

Multumesc!

L.E. : Multumesc frumos PlayLikeNeverB4 ca ai incercat sa ma ajuti! Se pare ca nu initializam o valoare din Trie cu 1, cea care pastra numarul de prefixe din fiecare elemnt!

Titlul: RÄƒspuns: 227 Geometrie
Scris de: razyelx din Octombrie 13, 2011, 00:46:33

rog pe cineva care are putin timp sa se uite peste sursa mea. in mare parte am segmentation fault si incorect. merge pe exemplu.
:thumbdown:

Titlul: bug!!
Scris de: Nume Fals din Martie 24, 2012, 23:29:08

Va rog frumos daca poate cineva sa isi dea seama ce nu e in regula cu implementarea mea (http://infoarena.ro/job_detail/723137?action=view-source), ma streseaza de mai mult de o ora.
Mai precis, pentru

Cod:

struct nod
{
    nod* nlist[26];
    int ap;
    nod()
    {
        memset(nlist,0,sizeof(nlist));
        ap=0;
    }
};
void insert(nod* pN, string &a)
{
    for (int i=0;i<a.size();i++)
    {
        if (pN->nlist[alf(a[i])]==0)
        {
            nod* pTmp = new nod;
            pN->nlist[alf(a[i])]=pTmp;
            pN=pTmp;
        }
        else pN=pN->nlist[alf(a[i])];
    }
    pN->ap++;
}
int pre_com(nod* pN, string &a)//prefix comun
{
    for (int i=0;;i++)
    {
        if (pN->nlist[alf(a[i])]==0) return i; //asta e singura verificare pt incheierea
        pN=pN->nlist[alf(a[i])]; // buclei; frunza are nlist nula
    }
}

cu alf(x)==x-'a'
efectuarea

Cod:

nod trie; insert(&trie,"aa");  pre_com(&trie,"aa");

da segmentation fault. pe gdb nu apare problema.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Stefan-Alexandru Filip din Martie 25, 2012, 00:35:10

Nu imi este clar de ce iti da KBS 11 in cazul pe care l-ai trecut tu acolo, dar din restul codului observ ca nu folosesti variabila ap in mod consistent. In unele cazuri consideri ca este numarul de aparitii al cuvintelor iar in alte cazuri consideri ca este numarul de cuvinte dintr-un subarbore. Cred ca vrei sa folosesti 2 variabile separate pentru asta. Asta explica de ce iei incorect, dar sunt sanse mari ca KBS-ul sa fie din aceiasi cauza.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Nume Fals din Martie 25, 2012, 09:07:06

Citat din mesajul lui: Stefan-Alexandru Filip din Martie 25, 2012, 00:35:10

Da, ai dreptate, trebuia sa numar cate aparitii au ascendentii fiecarui nod. Nu mi-am dat seama ca fara stergerea se face prea dificil. mersi!

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Alexandru Popescu din Octombrie 07, 2012, 14:34:31

what the hell is this? http://infoarena.ro/job_detail/795049
Nu prea le am cu pointerii dar sursa ruleaza fara probleme pe calculatorul meu.
Dupa ce am scos asserturile am luat iar killed by signal 11 http://infoarena.ro/job_detail/795053, deci banuiesc ca se declanseaza vreunul din ele. Dar la mine pe calc nu se declanseaza nici unul.
Later Edit: Nu mai este nevoie i-am dat de cap pana la urma.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: Coder Coder din Martie 23, 2013, 19:53:32

Am rezolvat problema si primesc doar 5 puncte. Am verificat fisierul meu .out cu fisierele de test si da bine pe cel putin 4(atat am verificat, atat manual cat si folosind un program). E cineva binevoitor sa se uite peste sursa?Poate fac vre-o afisare gresit. Multumesc!

Titlul: RÄƒspuns: 227 Geometrie
Scris de: George Marcus din Martie 23, 2013, 20:36:21

Vezi ca ai niste warning-uri la compilare. Posibil ca de acolo sa vina diferenta.

Titlul: RÄƒspuns: 227 Geometrie
Scris de: UAIC Alexandru Ionita din Ianuarie 28, 2014, 16:24:43

Imi poate spune cineva de unde primesc kbs 6? la mine pe pc ruleaza foarte bine...

Titlul: RÄƒspuns: 023 Trie
Scris de: GinguIonut din Septembrie 09, 2015, 22:43:13

Salut! Poate sa imi explice cineva va rog ce inseamna secventa asta? pas cu pas

struct Trie
{
int cnt, nrfii;
Trie *fiu[26];
Trie()
{
cnt=nrfii=0;
memset(fiu, 0, sizeof(fiu));
}
};
Trie *T = new Trie;

Cu tot cu importanta pointerilor de acolo

Titlul: Răspuns: 023 Trie
Scris de: theprdv din Septembrie 10, 2015, 10:27:44

struct restrange la un loc mai multe variabile (arrays, pointeri.. etc) numite membrii ( http://www.cplusplus.com/doc/tutorial/structures/ ). Pointerii *fiu[] (initial declarati nuli din constructor) vor retine adresa altei structuri tot de tip Trie, iar acea functie e constructorul (cu ea se fac initializarile), adica se apeleaza automat la declararea unei noi structuri ( http://www.dev-hq.net/c++/11--constructors-and-destructors )