Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 259 Euler  (Citit de 6921 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Iulie 09, 2006, 08:47:47 »

Aici puteţi discuta despre problema Euler.
« Ultima modificare: Iulie 10, 2006, 18:06:42 de către svalentin » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #1 : Iulie 09, 2006, 12:35:49 »

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.  Annoyed
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #2 : Iulie 09, 2006, 13:29:16 »

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...  Ok
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #3 : Iulie 09, 2006, 14:44:23 »

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)
« Ultima modificare: Iulie 09, 2006, 17:42:13 de către svalentin » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : Iulie 09, 2006, 16:36:19 »

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?Huh? , 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.
« Ultima modificare: Iulie 09, 2006, 18:34:31 de către devilkind » Memorat
vladcyb1
Vorbaret
****

Karma: 33
Deconectat Deconectat

Mesaje: 166



Vezi Profilul
« Răspunde #5 : Iulie 10, 2006, 13:39:43 »

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.   Thumb up
Memorat

Vlad Berteanu
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : Iulie 10, 2006, 16:03:30 »

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.
Memorat
snaked31
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #7 : Martie 15, 2007, 21:25:33 »

Citat
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
Memorat
Aymd
Strain


Karma: -29
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #8 : Martie 23, 2007, 11:35:24 »

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

Karma: -26
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #9 : Octombrie 08, 2007, 21:19:01 »

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++;
    }
}
« Ultima modificare: Octombrie 08, 2007, 21:26:39 de către Alex Iuga » Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #10 : Octombrie 08, 2007, 21:53:11 »

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.
Memorat
recviem
Client obisnuit
**

Karma: -26
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #11 : Octombrie 08, 2007, 22:08:07 »

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
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #12 : Octombrie 08, 2007, 22:11:03 »

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.)
Memorat
recviem
Client obisnuit
**

Karma: -26
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #13 : Octombrie 08, 2007, 22:12:47 »

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

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #14 : Octombrie 08, 2007, 22:15:22 »

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 Tongue

Oricum, cu citirea de mai sus nu ar trebui sa ai probleme.
« Ultima modificare: Octombrie 08, 2007, 22:16:53 de către Ionescu Vlad » Memorat
recviem
Client obisnuit
**

Karma: -26
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #15 : Octombrie 08, 2007, 22:18:27 »

 Dancing multumesc ! (spam  peacefingers)

L.E. : a sarit la 100 de puncte  Applause
« Ultima modificare: Octombrie 08, 2007, 22:19:59 de către Alex Iuga » Memorat
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #16 : August 05, 2010, 16:12:57 »

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

L.E : Vad ca am exact aceeasi problema pe care o avea devilkind acum 4 ani.
Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #17 : Noiembrie 27, 2010, 14:04:44 »

Fii atent ca fiecare nod din [1,n] sa se gaseasca in parcurgerea din fisierul de intrare. Eu asta uitam sa fac. Fool
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #18 : Iunie 24, 2012, 19:46:03 »

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  Smile
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #19 : Iulie 04, 2012, 00:14:12 »

Trebuie parsare pt 100 p d'oh!
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« Răspunde #20 : Iulie 04, 2012, 09:07:41 »

Pe C, C++ nu trebuie parsare. Pentru Pascal insa nu stiu ce sa zic, o parasare ar trebui sa fie suficienta.
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #21 : Iulie 04, 2012, 09:16:29 »

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

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #22 : Iulie 04, 2012, 09:34:20 »

Nu trebuie neaparat parsare doar ca intra cam la limita ultimul test (mie imi intra fix in 200ms http://infoarena.ro/job_detail/764130) Think
Tie iti intra pentru ca ai citirea cu streamuri si e mai rapida ca cea cu cstdio.
Memorat
mvcl3
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #23 : Decembrie 12, 2012, 17:07:40 »

imi zice cineva ce gresesc ca nu-mi dau seama de ce iau incorect pe ultimul test Brick wall Brick wall
multumesc!
Memorat
B__M__D
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #24 : Martie 19, 2013, 19:36:19 »

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)
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines