infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Filip Cristian Buruiana din Iulie 09, 2006, 08:47:47

Titlul: 259 Euler
Scris de: Filip Cristian Buruiana din Iulie 09, 2006, 08:47:47

Aici puteÅ£i discuta despre problema Euler (http://infoarena.ro/problema/euler).

Titlul: Raspuns: 259 Euler
Scris de: Savin Tiberiu din 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:

Titlul: Raspuns: 259 Euler
Scris de: Filip Cristian Buruiana din 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:

Titlul: Re: 259 Euler
Scris de: Valentin Stanciu din 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)

Titlul: Raspuns: 259 Euler
Scris de: Savin Tiberiu din 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.

Titlul: Raspuns: 259 Euler
Scris de: Vlad Berteanu din 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. :thumbup:

Titlul: Raspuns: 259 Euler
Scris de: Savin Tiberiu din 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.

Titlul: RÄƒspuns: 259 Euler
Scris de: Stanica Andrei din 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

Titlul: RÄƒspuns: 259 Euler
Scris de: Trimbitas Viorel Stefan din Martie 23, 2007, 11:35:24

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

Titlul: RÄƒspuns: 259 Euler
Scris de: Alexandru Pana din 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++;
    }
}

Titlul: RÄƒspuns: 259 Euler
Scris de: Ionescu Vlad din 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.

Titlul: RÄƒspuns: 259 Euler
Scris de: Alexandru Pana din 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

Titlul: RÄƒspuns: 259 Euler
Scris de: Ionescu Vlad din 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.)

Titlul: RÄƒspuns: 259 Euler
Scris de: Alexandru Pana din Octombrie 08, 2007, 22:12:47

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

Titlul: RÄƒspuns: 259 Euler
Scris de: Ionescu Vlad din 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 :P

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

Titlul: RÄƒspuns: 259 Euler
Scris de: Alexandru Pana din Octombrie 08, 2007, 22:18:27

\:D/ multumesc ! (spam :peacefingers:)

L.E. : a sarit la 100 de puncte =D>

Titlul: RÄƒspuns: 259 Euler
Scris de: Vlad Eugen Dornescu din 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.

Titlul: RÄƒspuns: 259 Euler
Scris de: Lepadat Mihai-Alexandru din 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:

Titlul: RÄƒspuns: 259 Euler
Scris de: UAIC.VlasCatalin din 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 :)

Titlul: RÄƒspuns: 259 Euler
Scris de: Petru Trimbitas din Iulie 04, 2012, 00:14:12

Trebuie parsare pt 100 p #-o

Titlul: RÄƒspuns: 259 Euler
Scris de: Adrian Budau din 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.

Titlul: RÄƒspuns: 259 Euler
Scris de: FMI Ciprian Olariu din 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 (http://infoarena.ro/job_detail/764130)) :-k

Titlul: RÄƒspuns: 259 Euler
Scris de: Simoiu Robert din Iulie 04, 2012, 09:34:20

Citat din mesajul lui: Olariu Ciprian din 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 (http://infoarena.ro/job_detail/764130)) :-k

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

Titlul: RÄƒspuns: 259 Euler
Scris de: Marian Iacob din Decembrie 12, 2012, 17:07:40

imi zice cineva ce gresesc ca nu-mi dau seama de ce iau incorect pe ultimul test ](*,) ](*,)
multumesc!

Titlul: RÄƒspuns: 259 Euler
Scris de: Danutz2uuu din 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)

Titlul: RÄƒspuns: 259 Euler
Scris de: Radu-Andrei Szasz din Martie 20, 2013, 10:49:59

Ideea e ca tu vei avea cu siguranta un arbore si trebuie doar sa spui daca parcurgerea euler e valida :)

Titlul: RÄƒspuns: 259 Euler
Scris de: Arhire Andrei din Decembrie 30, 2018, 17:08:46

Salut.

Cu riscul de a lua prea multe puncte cei ce fac asta :

Cod:

#include <fstream>
using namespace std ;
ofstream g ( "euler.out" ) ;
int main () { return g <<"NU" , 0 ; } :-'

Ar mai merge cateva teste ce nu contin lanturi euleriene. Conditia suficienta pentru a trece singurul test care returneaza "NU" e ca 2 numere alaturate sa fie distincte. Spre exemplu conditia ca un nod sa mai apara odata dupa ce a iesit din parcurgerea corecta.

apropo

Citat

Date de Intrare
In fisierul de intrare euler.in se va afla pe prima linie numarul N, iar pe a doua linie o succesiunea de numere naturale cuprinse intre 1 si N. Numarul de numere este necunoscut.

Sunt 2 * n - 1 numere ( n - flux + n - 1 la reflux ( fara radacina ) )