259 Euler

[•filipb]

Aici puteţi discuta despre problema Euler.

[•devilkind]

Ce se intampla cu problema asta? parcurg o singura data succesiunea de numere si determin vectoru de tati si totusi nu iau decat 30 pct, TLE pe restu. Citesc cu fgets si apoi parcurg stringu citit o singura data si apoi afisez. 

[•filipb]

Daca citesti cu fgets, ai grija ca numarul de caractere sa fie suficient de mare ( sunt maxim 500 000 numere * 6 cifre + spatii ). In plus, nu face niciodata ceva de genul:

Cod:

for (i = 1; i <= strlen(s); i++)

, pentru ca strlen(s) este mare consumatoare de timp. mai bine faci

Cod:

l = strlen(s);
for (i = 1; i <= l; i++)

Oricum, vad ca ai rezolvat deja problema cu TLEul... 

[•svalentin]

sau, daca problema iti permite sa o iei invers, poti sa faci:

Cod:

for (i = strlen(s); i>0; i--)

(strlen se apeleaza o singura data, la initializarea lui i, si nici nu folosesti o variabila in plus)

[•devilkind]

Mda asta era problema oricum am rezolvat-o folosind o variabila auxiliara, am 80 de pct, tre sa verific dak raspunsul este DA sau NU, dak este afirmativ imi da, akuma tre sa vad ptr NU.

[later edit] Mi-ar putea da cineva o idee despre cum sa verific dak este sau nu posibil ca acea parcurgere sa fie a unui graf cu N noduri?? , poate suna stupid din moment ce am luat deja 80 pct cu refacerea arborelui sa nu stiu cum sa verific chestia asta dar toate ideile pe care le-am avut nu au dat roade.

[•vladcyb1]

Atunci cand construiesti vectorul de tati verifici daca pentru nodul curent i-ai stabilit deja tatal...daca tatal deja stabilit nu coincide cu cel pe care vrei sa i-l atribui in prezent inseamna ca la un momentdat ceva a mers prost, deci nu exista arborele.
Si trebuie sa mai verifici ca sirul citit are lungime 2 * N - 1. Si cam asta ar fi de ajuns.   

[•devilkind]

ma gandisem si eu la asta insa scapam din vedere o chestie si aveam impresia ca e gresit insa la o privire mai atenta mi-am dat seama ca era corect, doar ca trebuia sa mai verific ceva, si chiar si asa tot iau numai 90 pct.

[•snaked31]

arborele cu 7 noduri, cu radacina in nodul 5 si cu lista de muchii , (5 7), (3 6), (3 1), (3 2), (7 4),

ar trebui inserata muchia (5 3) in enunt

[•Aymd]

Problema se rezolva in O(n), daca ai terminat citirea nu mai urmeaza decat o tiparire.

[•recviem]

Eu cu citirea asta si un algoritm de complexitate O(n) iau doar 30 de puncte .. pe 'NU' imi dau toate bine, si imi mai da primul test.
Imi explica si mie cineva cum as putea face o citire .. 'corecta' ? Asta daca tine de citire..

Cod:

    char c[7654321];

void citire()
{
    long long l,i;
    freopen("euler.in","r",stdin);
    scanf("%lld",&n);
    getc(stdin);
    gets(c);
    l=strlen(c);
    while (i<l)
    {
        v[k]=v[k]*10+c[i++]-'0';
        while (c[i] != ' ' && i<l)
        {
            v[k]=v[k]*10+c[i++]-0;
        }
        k++;
        i++;
    }
}

[•Dastas]

Nu ai nevoie de citire parsata la problema asta... poti citi pur si simplu cu scanf daca crezi ca de la citire ti se trage.

[•recviem]

eu am mari probleme cu citirea .. la ceva de genu

Cod:

    freopen("euler.in","r",stdin);
    scanf("%ld",&n);
    while (!feof(stdin))
        scanf("%ld",v[i++]);
 

primesc sigsegv

[•Dastas]

Cel mai elegant e sa verifici valoarea intoarsa de scanf:

while ( scanf("%d", &v[i++]) == 1 ) ... fa ce ai de facut cu v[i ] ...

Partea in rosu la tine lipseste apropo. Probabil de la aia ai sigsegv.

In plus, numarul de numere eu zic ca e cunoscut, daca te gandesti ce inseamna de fapt parcurgere euler (nu am testat, eu am citit ca mai sus, dar cred ca e adevarat ce am zis.)

[•recviem]

defapt nu e cunoscut .. pot sa-ti dea mai putin decat 2*n-1 numere ..

[•Dastas]

Caz in care nu ai solutie, deci daca mai merge un scanf la sfarsit afisezi 0 sau -1 sau ce ti se cere, la fel daca is mai putine

Oricum, cu citirea de mai sus nu ar trebui sa ai probleme.

[•recviem]

  multumesc ! (spam  )

L.E. : a sarit la 100 de puncte 

[•dornescuvlad]

E ceva deosebit la testul 7? Am facut testarile pentru fiecare tata[nod] (adica daca ajung ptr. un nod al carui tata deja l-am calculat, la alta valoare, afisez "NU" si ies din program (un nod nu poate avea 2 tati diferiti).Am facut inca un test, ca prima valoare citita sa fie egala cu ultima, in cazul in care numarul de valori citite este egal cu 2 * N - 1.
Nu imi dau seama care caz il omit.

L.E : Vad ca am exact aceeasi problema pe care o avea devilkind acum 4 ani.

[•skull]

Fii atent ca fiecare nod din [1,n] sa se gaseasca in parcurgerea din fisierul de intrare. Eu asta uitam sa fac.

[•ctlin04]

Ma poate ajuta si pe mine cineva sa nu mai iau TLE la ultimile 2 teste, eu la fel fac o singura parcurgere si apoi afisez rezultatul, problema e ca lucrez in pascal si de asta merge mai greu, am pus buffer si am parsat citirea si astfel de la 50 am ajuns la 80, daca are cineva vreun sfat, as fi recunoscator, ms anticipat 

[•S7012MY]

Trebuie parsare pt 100 p

[•freak93]

Pe C, C++ nu trebuie parsare. Pentru Pascal insa nu stiu ce sa zic, o parasare ar trebui sa fie suficienta.

[•scipianus]

Nu trebuie neaparat parsare doar ca intra cam la limita ultimul test (mie imi intra fix in 200ms http://infoarena.ro/job_detail/764130)

[•SpiderMan]

Nu trebuie neaparat parsare doar ca intra cam la limita ultimul test (mie imi intra fix in 200ms http://infoarena.ro/job_detail/764130)

Tie iti intra pentru ca ai citirea cu streamuri si e mai rapida ca cea cu cstdio.

[•mvcl3]

imi zice cineva ce gresesc ca nu-mi dau seama de ce iau incorect pe ultimul test
multumesc!

[•B__M__D]

Eu inca nu am inteles cum imi dau seama daca sirul ala nu reprezinta o parcurgere Euler
Sa zicem ca avem grafful alaturat (1,2) (2,3) (3,4) (2,4)
si avem in fisierul de intrare:
4
1 2 3 4 3 2 4 2 1(facem abstractie de faptul ca nu avem 2*4-1 nr)
cum ne dam seama ca nu e arbore?(avem ciclul 2 3 4)