Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: Kgon  (Citit de 10884 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« Răspunde #25 : Februarie 24, 2013, 10:37:53 »

Citeste toate intrebarile si raspunsurile si enuntul.
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #26 : Februarie 24, 2013, 10:40:39 »

Di este intotdeauna mai mic decat 2*Pi*R?
Memorat
costyv87
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #27 : Februarie 24, 2013, 10:57:39 »

Pentru precizie, ce valoare sugerati sa-i dam lui pi ? (Nu stiu daca puteti sa raspundeti la asta, dar cred ca ar ajuta ) .
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #28 : Februarie 24, 2013, 10:58:06 »

2 numere se considera egale daca abs( a-b ) < 10-5?
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« Răspunde #29 : Februarie 24, 2013, 10:59:28 »

@Mihai Ionut Enache DA
@Vlad Costin In biblioteca cmath(sau math.h) se gaseste predefinit pi. Este "M_PI"(ghilimelele sunt doar pentru claritate)
@Alex Velea DA
Memorat
costyv87
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #30 : Februarie 24, 2013, 11:04:35 »

@Mihai Ionut Enache DA
@Vlad Costin In biblioteca cmath(sau math.h) se gaseste predefinit pi. Este "M_PI"(ghilimelele sunt doar pentru claritate)
@Alex Velea DA


Mersi mult. Asta a rezolvat tot.
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #31 : Februarie 24, 2013, 13:06:39 »

Se putea mai bine de N lg N ?  Confused
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #32 : Februarie 24, 2013, 13:07:00 »

Cum ati reusit sa scapati de TLE? Eu am rezolvat-o in O(n) cu hashuri?  Smile
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #33 : Februarie 24, 2013, 13:09:36 »

Cum ati reusit sa scapati de TLE? Eu am rezolvat-o in O(n) cu hashuri?  Smile

Poti sa imi detaliezi putin aici sau pe privat ? Am impresia ca puntele trebuiau sortate. Multumesc anticipat.  Smile
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #34 : Februarie 24, 2013, 13:10:07 »

Eu am luat OK pe testul 7 cu 104 ms, complexitate O(N log N + N). Am sortat si m-am plimbat cu 2 pointeri Smile
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #35 : Februarie 24, 2013, 13:12:21 »

Am gasit L = PI * R * 2 / k, apoi bagam toate punctele intr-un hash. Adaugam L la punctul de start, pana cand gaseam k puncte sau pana gaseam un punct care nu exista. Daca depaseam circumferinta cercului, o scadeam din distanta curenta.
Aveam 132 ms daca faceam doar citirea.  Smile
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #36 : Februarie 24, 2013, 13:13:46 »

Eu am scos o(n log n) cu o sortare si cautare binara a termenilor ce fac parte din progresii aritmetice cu ratia (2*pi*r / k). Pe testul 7 am 148ms. Se poate demonstra corectitudinea solutiei in o(n)?
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #37 : Februarie 24, 2013, 13:16:37 »

Eu am scos o(n log n) cu o sortare si cautare binara a termenilor ce fac parte din progresii aritmetice cu ratia (2*pi*r / k). Pe testul 7 am 148ms. Se poate demonstra corectitudinea solutiei in o(n)?

Idem , doar ca am TLE Smile).

@ SebiSebi : Ce functie de hashing ai folosit ?

LE : Ma refer la faptul ca aveai de retinut double-uri.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #38 : Februarie 24, 2013, 13:18:09 »

@ SebiSebi : Ce functie de hashing ai folosit ?

LE : Ma refer la faptul ca aveai de retinut double-uri.

Puteai inmulti numerele double cu 10^7, astfel ti le tineai long long-uri
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #39 : Februarie 24, 2013, 13:19:06 »

Am incercat 3 modalitati , insa fara succes. Am pastrat hashing-ul pentru numere reale (cel cu partea fractionala), folsind constanta propusa de Knuth si modulo 10007.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #40 : Februarie 24, 2013, 13:21:04 »

Am incercat 3 modalitati , insa fara succes. Am pastrat hashing-ul pentru numere reale( cel cu partea fractionala) , folsind constanta propusa de Knuth si modulo 10007.

Eu tot nu prea vad cum cu hash.. tot trebuiau sortate numerele pana la urma Neutral
Daca ai ceva de genul:

Cod:
3
1
2

(astea sunt distantele, "sa presupunem" ca se poate),
atunci ce faci?
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #41 : Februarie 24, 2013, 13:25:34 »

@ Vlad: Poi de la un punct se poate ajunge adugand la unul din set sau se poate iesi din set. Marchezi punctele cand mergi , si nu mai ai de la parcurs din nou. Cred ca ar merge.  Huh
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #42 : Februarie 24, 2013, 13:27:03 »

Cum ati facut sa intre precizia? Am incercat mai multe modalitati (toate cu cautare binara) pe int si pe reale, cu precizia -5, -6, dar nu mi-a intrat...
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #43 : Februarie 24, 2013, 13:28:02 »

Sper ca am inteles ce vrei sa spui. Daca aveam exemplul din enunt , dar in alta ordine :
Cod:
5 3 10.000000
41.887902
0.000000
12.978671
38.111412
20.943951
l = 20.943951
L = 62.83185
Plecam din primul punct, deoarece pe el nu l-am mai "vizitat" pana acum.
Caut punctul 41.887902 + l=62.83185 , care este egal cu circumferinta cercului, deci scad L - > punctul devine 0.
Caut punctul 0 + l = 20.943951, il gasesc -> am gasit trei puncte care formeaza un triunghi echilateral.
Eu am considerat ca nu conteaza ordinea punctelor.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #44 : Februarie 24, 2013, 13:28:32 »

Steve: Eu am facut cu eps 0.000001 si mi-a mers....
Dan Alex: Stai putin, tu la ce te referi cu set? Ala din "#include <set>" ? Daca da, ala e logn (mai mult de fapt).. si nu mai iese o(n) solutia Confused
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #45 : Februarie 24, 2013, 13:40:04 »

@ Vlad: Nu set din STL. La puntele din hash. Graba...

LE: Sebi , cred ca e bun rationamentul.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #46 : Februarie 24, 2013, 13:44:20 »

@ Vlad: Nu set din STL. La puntele din hash. Graba...

LE: Sebi , cred ca e bun rationamentul.

Da, este bun, am luat 40 de puncte cu complexitatea O(n). O sa inlociuesc hash-ul cu o sortare + cautare binara, sa vad cat iau.  Smile 
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #47 : Februarie 24, 2013, 13:45:47 »

Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N)  Smile
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #48 : Februarie 24, 2013, 13:46:45 »

Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N)  Smile
OK. Nu ma asteptam sa mearga asa de prost hash-ul, dar se mai intampla.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #49 : Februarie 24, 2013, 14:22:22 »

E buna ideea intr-adevar ... bravo Smile
Oricum, cred ca modulo-urile alea mananca o droaie de-a timp (cred ca de la asta ai atatea TLE-uri) Confused
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines