OJI 2009

[•bogdan2412]

La problema Cerc mergea si greedy si putea fi rezolvata in O(N log N) astfel. Pentru fiecare dreapta, cercul i, aflat la distanta D_i = sqrt(X_i^2 + Y_i^2) de origine, ocupa intervalul (D_i - R_i, D_i + R_i). Pentru a determina numarul de cercuri exterioare 2 cate 2 este corect sa alegi la fiecare pas intervalul cu capatul din dreapta cel mai mic si care nu se intersecteaza cu nici un alt interval deja ales. Poti determina usor numarul, sortand intervalele crescator dupa capatul al doilea.

[•Pepelea_Flaviu]

Sima Cotizo...eu am facut aceasi dinamica pe fiecare dreapta si a intrat in 0 ms

[•DraStiK]

extreme si jupanu, era cel mai sigur daca puneai citirea pana la end of file sau parsai citirea pentru ca specifica ca e doar un rand de maxim 1000 caractere

[•wefgef]

Pentru ce aveati nevoie sa cititi pana la '\n'? Cum era enuntul?

[•jupanubv92]

      Pai era un string pe care trebuia sa il evaluezi , iar stringu era pe o singura linie .
      Eu am citit cu fgets ... cu citire din c si asta a fost problema ca mi-a citit tot siru + \n de la sfarsitul liniei , si cand mi-am dat teste in borland n-am dat enter dupa prima linie si n-am vazut ca cicleaza si ca am uitat sa pun \n . Iar programu meu era unul recursiv si am uitat sa pun conditia sa iasa din recursivitate cand intalneste \n .
 Dragos : mie nu imi cicla citirea ci programul din cauza ca imi citea sirul cu tot cu \n

[•xtreme]

pentru Andrei Antonescu : a raspuns si pentru mine "jupanubv" , deci aceeasi problema.
pentru "jupanubv " : mersi la fel
pentru "wefgef" : in enunt nu scrie ca la sfarsitul fiecarei expresii se afla caracterul '\n' si desi scrie la rubrica date de intrare "pe prima linie..." , eu tot pot sa creez un fisier care are pe prima linie o expresie si fara caracteru '\n' la sfarsit si si cu....era o chestie de ales(ghicit) si noi am ales(ghicit) cum nu trebuia...

[•andrei-alpha]

Da ce sa zic.. nasol  dar in general la orce problema, chiar daca nu zice se termina cu carcaterul '\n', e standard.
Stie cineva cine este autorul de la problema Reteta, clasa X-a ca trebuie ceruta permisiunea lui ca puneam problema in arhiva. 

[•warangel]

La problema cerc (clasele XI-XII) am folosit x1/y1=x2/y2 (x1*y2=x2*y1) pentru pct a iar pt b si c am folosit programare dinamica. Am luat fiecare dreapta in parte si pentru fiecare am retinut in vector numarul maxim de cercuri exterioare ce se pot forma cu cercul i si cercurile precedente. Complexitatea ar fii cam o(m*n*log(n)) (cred... nu calculez prea bine complexitatea  ) Am luat 28 de puncte la problema asta  desi nu a iesit din timp. Intrebarea este: era posibil sa iasa din int? In total am luat 128 de puncte si pana maine stau ca pe jar sa vad daca ma calific  Daca aveti vreo stire inainte de maine anuntati-ma, va rog, si salvati-ma de 24 de ore in care ma gandesc numai la asta 

[•sima_cotizo]

Da, era. Coordonatele erau pana la 1000, iar 1000*1000 = 1.000.000, care iese din int (maxint = 32.000).

Sima Cotizo...eu am facut aceasi dinamica pe fiecare dreapta si a intrat in 0 ms

Timerele erau cam dubioase, parerea mea Oricum, am zis ca riscai, nu ca era obligatoriu sa iasa.

[•warangel]

mda, sunt dobitoc 

[•andrei.12]

La problema cerc (clasele XI-XII) am folosit x1/y1=x2/y2 (x1*y2=x2*y1) pentru pct a iar pt b si c am folosit programare dinamica. Am luat fiecare dreapta in parte si pentru fiecare am retinut in vector numarul maxim de cercuri exterioare ce se pot forma cu cercul i si cercurile precedente. Complexitatea ar fii cam o(m*n*log(n)) (cred... nu calculez prea bine complexitatea  ) Am luat 28 de puncte la problema asta  desi nu a iesit din timp. Intrebarea este: era posibil sa iasa din int? In total am luat 128 de puncte si pana maine stau ca pe jar sa vad daca ma calific  Daca aveti vreo stire inainte de maine anuntati-ma, va rog, si salvati-ma de 24 de ore in care ma gandesc numai la asta 

Dat fiind ca esti pe 4, parerea mea este ca sigur te califici ( cred ca se iau in jur de 8 )

[•jupanubv92]

La mine s-a rezolvat faza cu \n si m-am calificat la nationala , sper sa se rezolve si la tine xtrem .

[•warangel]

Da, era. Coordonatele erau pana la 1000, iar 1000*1000 = 1.000.000, care iese din int (maxint = 32.000).

dar int*int==int*int, nu? adica 1234*10000==12340*1000 returneaza 1, nu?

[•Palude]

In sfarsit s-au anuntat calificarile pe Bucuresti!!! Si merg pt prima oara la ONI!!!!!!!!!!11111111ONEONEONEONE

[•warangel]

  Felicitari. Si eu merg tot pentru prima data  .

Am o intrebare: Lotul bucurestiului o sa faca pregatire speciala cum e la alte materii?

[•INSiDe123]

m-am calificat si eu :>  ..oni o sa se tina la galati pana la urma?

[•CezarMocan]

Felicitari. Si eu merg tot pentru prima data  .

Am o intrebare: Lotul bucurestiului o sa faca pregatire speciala cum e la alte materii?

Din cate stiu eu nu.

m-am calificat si eu :>  ..oni o sa se tina la galati pana la urma?

Da, la Galati.

[•warangel]

La problema Cerc mergea si greedy si putea fi rezolvata in O(N log N) astfel. Pentru fiecare dreapta, cercul i, aflat la distanta D_i = sqrt(X_i^2 + Y_i^2) de origine, ocupa intervalul (D_i - R_i, D_i + R_i). Pentru a determina numarul de cercuri exterioare 2 cate 2 este corect sa alegi la fiecare pas intervalul cu capatul din dreapta cel mai mic si care nu se intersecteaza cu nici un alt interval deja ales. Poti determina usor numarul, sortand intervalele crescator dupa capatul al doilea.

Adica precum problema "standard" programarea spectacolelor, nu?

[•gabitzish1]

Da. Se gaseste numarul maxim de intervale care nu se intersecteaza.

[•Addy.]

si totusi, are cineva teste, evaluatoare, ceva pentru problemele de la liceu?
caut in continuu si nu dau de nimic. 
merci.

[•gabitzish1]

Eu am pentru clasele 11-12.

[•alexandru92]

Unde se tine ONI  la Galati sau Targoviste ?  Aici scrie ca se tine la  Targoviste, dar cineva mi-a zis ca se tine la  Galati ? Care e adevarul ??

[•gabitzish1]

Se organizeaza in Galati.

[•alexandru92]

Multumesc
ps: De ce scrie acolo ca se organizeaza la Targovistea  daca ii la Galati ??

[•gabitzish1]

Banuiesc ca e gresala.