825 Cerc3

[•DITzoneC]

Aici puteţi discuta despre problema Cerc3.

[•Mishu91]

De ce nu se (mai) pot trimite solutii la problema asta?

[•pauldb]

Acum ar trebui sa mearga.

[•Pepelea_Flaviu]

Nici la problema pm2 nu se pot trimite solutii!

[•alexandru92]

De curiozitate care este complexitatea celui mai eficient algoritm ?

[•Florian]

O(N * logN)

[•alexandru92]

Eu nu inteleg cum pe dreapta d3 sunt 3 cercuri exterioare. D3 trece prin 4 cercuri, dar cercul mare "inghite" 2 => raman 2 cercuri exterioare, sau eu inteleg gresit  .

[•Florian]

Nu lua in considerare cercul mare. Raman trei care nu se intersecteaza? 

[•alexandru92]

Deci pe scurt daca  cercul A include B , nu le tratez ca si cum s-ar intersecta ?  

[•Florian]

Trebuie sa gasesti numarul maxim de cercuri de pe o dreapta, intre care nu exista suprapunere. Pe dreapta d3 ai 4 cercuri. Daca alegi cele trei cercuri "mici", ai numar maxim de cercuri exterioare ( pentru ca astea trei nu se suprapun intre ele ). Intelegi ?

[•alexandru92]

Aham, thanks   

[•PavelRazvan]

Are careva vreo idee de ce iau numa 97 de puncte ?
http://infoarena.ro/job_detail/348109

Multumesc anticipat ...

[•cristiprg]

aici is aceleasi teste ca la oji ?

[•alexandru92]

aici is aceleasi teste ca la oji ?

Da

[•Andreid91]

"ultima valoare gresita" la toate testele ...cu toate ca cele de la oji imi merg...
Pe ultimu test imi da  1977 4 2... (asta e si raspunsu corect din teste)
Trebuie sa fie de la evaluator ? ..sau nu afisez eu corect ? (am ceva gen    g<<niv[n]<<' '<<getnr()<<' '<<nrmax; )

[•wefgef]

E de la afisare. Tu presupui ca intai se va apela functia getnr(), apoi se vor printa valoarea returnata si variabila nrmax. Standardul C++ nu precizeaza nimic legat de ordinea de evaluare.

O afisare care ia 100 de puncte:

Cod:

    g << niv[n];
    g << ' ' << getnr();
    g << ' ' << nrmax;

[•Andreid91]

Da...intradevar o afisare de 100 pct 

Mersi!

[•stocarul]

La ultima restricție din enunț apare:

Pentru rezolvarea primei cerinţei se acordă 20% din punctaj, pentru cerinţă 50% din punctaj şi pentru a treia cerinţă 30% din punctaj.

Cred că ar trebui să apară:

... pentru a doua cerinţă 50% din punctaj şi ...

[•soriyn]

La problema asta pentru a 2a cerinta am incercat sa fac asa : iau fiecare dreapta distincta si retin pt fiecare cerc cu centru pe ea punctele(abscisele) in care se intersecteaza cu dreapta si obtin astfel niste intervale. Problema e ca punctele astea n-au coordonate intregi. Am incercat sa fac cu numere reale dar iau incorect. Voi cum ati facut ?

[•maritim]

Te poti folosi si de suma razelor si de distantele dintre centrele a doua cercuri ce se afla pe aceeasi linie pentru vedea daca se intersecteaza.

[•nbibest]

De ce ati pus limita de timp atat de mica? La judeteana era o secunda. Din cauza asta imi pica 2 teste.

[•visanr]

Limita e pusa in asa fel incat sa iei 100 cu o rezolvare in complexitate optima.  Poti sa o faci in O(N log N).

[•nbibest]

Se pare ca impartirea era problema... repetam o impartire care putea fi calculata inainte.
O intrebare: cum verific daca doua impartiri sunt egale daca una o calculez inainte. Daca f=x/y si apoi verific f daca e egal cu impartirea nu merge de fiecare data, iau 57 de puncte. Ca sa fie bine am pus (abs(f-g)<0.000001) dar poate nici asa nu o sa fie bine mereu. Cum as putea face sa iasa ok, adica care e metoda "clasica"?

Off: Se pare ca blestemul numerelor cu virgula (double, float, ce-or fi) continua. "Multumita" unui sqrt, care pe compilatorul de la evaluare nu primea decat double, am pierdut nationala anul trecut...

[•stardust]

Poti sa le pastrezi ca fractii si compari fractiile, astfel eviti impartirea.

[•nbibest]

Poti sa le pastrezi ca fractii si compari fractiile, astfel eviti impartirea.

Mersi mult, nu m-am gandit la asta