•filipb
|
|
« : 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
|
|
« 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.
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« 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: for (i = 1; i <= strlen(s); i++) , pentru ca strlen(s) este mare consumatoare de timp. mai bine faci l = strlen(s); for (i = 1; i <= l; i++) Oricum, vad ca ai rezolvat deja problema cu TLEul...
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« Răspunde #3 : Iulie 09, 2006, 14:44:23 » |
|
sau, daca problema iti permite sa o iei invers, poti sa faci: 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
|
|
« 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? ? , 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
|
|
« 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.
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•devilkind
|
|
« 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
Mesaje: 4
|
|
« Răspunde #7 : Martie 15, 2007, 21:25:33 » |
|
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
Mesaje: 19
|
|
« 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
Mesaje: 62
|
|
« 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.. 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
|
|
« 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
Mesaje: 62
|
|
« Răspunde #11 : Octombrie 08, 2007, 22:08:07 » |
|
eu am mari probleme cu citirea .. la ceva de genu freopen("euler.in","r",stdin); scanf("%ld",&n); while (!feof(stdin)) scanf("%ld",v[i++]); primesc sigsegv
|
|
|
Memorat
|
|
|
|
•Dastas
|
|
« 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
Mesaje: 62
|
|
« 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
|
|
« 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 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
Mesaje: 62
|
|
« Răspunde #15 : Octombrie 08, 2007, 22:18:27 » |
|
multumesc ! (spam ) L.E. : a sarit la 100 de puncte
|
|
« Ultima modificare: Octombrie 08, 2007, 22:19:59 de către Alex Iuga »
|
Memorat
|
|
|
|
•dornescuvlad
|
|
« 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. L.E : Vad ca am exact aceeasi problema pe care o avea devilkind acum 4 ani.
|
|
|
Memorat
|
|
|
|
•skull
Client obisnuit
Karma: 17
Deconectat
Mesaje: 75
|
|
« 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.
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« 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
|
|
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #19 : Iulie 04, 2012, 00:14:12 » |
|
Trebuie parsare pt 100 p
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« 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
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #22 : Iulie 04, 2012, 09:34:20 » |
|
Tie iti intra pentru ca ai citirea cu streamuri si e mai rapida ca cea cu cstdio.
|
|
|
Memorat
|
|
|
|
•mvcl3
Strain
Karma: 0
Deconectat
Mesaje: 22
|
|
« 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 multumesc!
|
|
|
Memorat
|
|
|
|
•B__M__D
Strain
Karma: -3
Deconectat
Mesaje: 2
|
|
« 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
|
|
|
|
|