145 Insula

[•fireatmyself]

Aici puteţi discuta despre problema Insula.

[•sims_gl]

Nu ma prind... Unde sunt plantati arborii?

[ditzone]

In fiecare punct de coordonate intregi din interiorul cercului.

[•sims_gl]

Scuze, ma gandeam ca daca arborii ar fi in fiecare punct de coordonate intregi si daca fiecare arbore ar avea 0,5 raza, nu ar mai putea fi vazuta Adriana, deoarece arborii din jurul ei ar fi lipiti... si unul din rezultatele din exemplu era mai mare de 0,5... abia acum am vazut ca era pt. raza insulei 1...

[•Adriana_S]

stiu ca nu are prea mare legatura cu problema ceea ce zic dar...sunt prea fericita ca imi regasesc numele intr-o problema ca sa ma abtin . Oricum, considerand cine e autorul, stiu ca nu se referea la mine cand a propus problema, dar nu conteaza. Tot mi se potriveste partea cu mica de inaltime si fata desteapta . Pot sa continui sa fiu protagonista a multe probleme, nu ma supar

P.S. Scuzati inutilitatea postului

[cristi8]

raza insulei e numar intreg ?

[ditzone]

in testele de la evaluare sunt numere naturale, dar merge la fel de bine si pe numere reale, de aceea nici nu s-a precizat acest lucru in enunt.

[•fireatmyself]

Scuze, ma gandeam ca daca arborii ar fi in fiecare punct de coordonate intregi si daca fiecare arbore ar avea 0,5 raza, nu ar mai putea fi vazuta Adriana, deoarece arborii din jurul ei ar fi lipiti... si unul din rezultatele din exemplu era mai mare de 0,5... abia acum am vazut ca era pt. raza insulei 1...

In mod evident ai mai multe valori ale lui G pentru o valoare R. Eu ti-o cer pe cea minima. Pentru unele cazuri merge si G < 0,5, dar, daca desenai cercul trigonometric (R = 1) iti dadeai seama ca in interiorul lui se afla doar Adriana, iar cei 4 copaci erau plantati pe conturul acestuia. De aceea iti da G > 0.5.

stiu ca nu are prea mare legatura cu problema ceea ce zic dar...sunt prea fericita ca imi regasesc numele intr-o problema ca sa ma abtin :Applause: :Very Happy: . Oricum, considerand cine e autorul, stiu ca nu se referea la mine cand a propus problema, dar nu conteaza. Tot mi se potriveste partea cu mica de inaltime si fata desteapta :Razz:. Pot sa continui sa fiu protagonista a multe probleme, nu ma supar :Very Happy:

P.S. Scuzati inutilitatea postului :Smile:

In mod evident o sa mai fie probleme cu Adriana, dar nu va entuziasmati prea tare... Balaurul o sa fie si el prezent pe'acolo.

[•Adriana_S]

yeeeeeeeeeeeeeeeeey  
Nu-i asa ca numele meu are o rezonanta superba?

Gata asta e ultimu post pe tema asta, ca e complet off topic

[•fireatmyself]

Nu-i asa ca numele meu are o rezonanta superba?

ok... comentarii legate de problema aveti ?
pai, radem, glumim, dar chiar asa ??

Gata asta e ultimu post pe tema asta, ca e complet off topic

     

acum sa te vad luand 100 la probela asta  

[•spatarel]

Se pare ca cineva a descoperit o solutie f. rapida la problema asta (nu eu, pt. ca eu am facut cu pre-calculare   - ce sa-i faci? daca razele nu erau numere reale... dar chiar si atunci ar fi mers cu pre-calculare )

Deci, intrebare: Ce complexitate are solutia oficiala?  

[•fireatmyself]

o(T), dar asta este una din cele trei surse   exista si alte complexitati care pot lua 100 de puncte.

Good luck.

[•spatarel]

Ar fi interesanta o demonstratie pentru formula

Dar, o astfel de demonstratie nu-si are locul aici, pentru ca ar trebui facuta publica formula

Oricum, interesante problema si formula!

[•fireatmyself]

evident ca formula nu va fi postata  
asta ar insemna ca toata lumea sa ia 100 de puncte.
problema are o rezolvare "informatica", rezolvare care vad ca e la moda prin concursuri  

eu am facut cu pre-calculare

tu cum naiba ai precalculat ? (ca din moment ce ai precalculat inseamna ca ai o complexitate super naspa)

[•wefgef]

ptr 1,2,3,4,5 da

Cod:

0.707
0.447
0.316
0.242
0.196

?

[•fireatmyself]

Da.

[•Coty]

:lol: noroc ca am prins ideea voastra de a cauta pe siteuri de mate formulele...  

dar ca idee, daca se primeste o problema asa, care pare de formula, in timpul unui concurs, cum o deduci? adica exista o metoda sau... te rogi sa ai inspiratie de moment?

[ditzone]

Problema asta se poate rezolva si fara formula....
Cat despre formula... normal ca se pot deduce.. ca doar asa au aparut... le-a dedus / demonstrat cineva...

[•wefgef]

eu fac asa: iau toate punctele aflate in coord relativ prime dintr-o optime de cerc si le sortez in functie de panta. apoi ptr toate perechile de puncte consecutive caut binar cat trebuie sa fie raza copacilor astfel incat sa nu se vada adriana. retin maximul si il afisez. mie mi se pare corect...

later edit:  am modificat ceva la afisare si acum iau 80.

[•fireatmyself]

probabil e de la afisare, ca in rest rezolvarea ta pare ok   incearca sa afisezi ca in enunt

[•titusu]

wefget, probabil nu-i destul de mare vectoru cu punctele... si merge frumos fara cautare binara(asta asha, ca fapt divers)

[andreit1]

TEST 1   ...[1.03s]...   Time limit exceeded
TEST 2   ...[0.01s]...   OK!
TEST 3   ...[0.01s]...   OK!
TEST 4   ...[1.11s]...   Time limit exceeded

Este ceva in neregula cu evaluatorul? Este imposibil sa iau TLE pe un program care facem maxim 50 de operatii cu numere reale...

[•fireatmyself]

nu este nimic in neregula cu evaluatorul, vezi sa nu cicleze pe undeva sursa ta

[•wefgef]

am aflat si eu forumla...

daca aveti un link cu demonstratia, dati-mi-l si mie va rog pe private.

[•cesc]

de ce nu este raspunsul pt R=1 chiar 1 ? Cum se poate ca cu o raza de 0,707 Adriana sa nu fie vazuta ?
poate cineva sa explice cum se deduce formula? sau sa primesc un hint asupra cum pot determina formula sau macar un desen pt R=1

Later edit : Stie cineva sa raspunda intrebarii mele?

Editat de moderator: Nu mai posta de doua ori consecutiv, editeaza-ti postul anterior!