•freak93
|
 |
« Răspunde #25 : Februarie 24, 2013, 10:37:53 » |
|
Citeste toate intrebarile si raspunsurile si enuntul.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit

Karma: 20
Deconectat
Mesaje: 74
|
 |
« Răspunde #26 : Februarie 24, 2013, 10:40:39 » |
|
Di este intotdeauna mai mic decat 2*Pi*R?
|
|
|
Memorat
|
|
|
|
•costyv87
Strain
Karma: 8
Deconectat
Mesaje: 37
|
 |
« 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
|
 |
« Răspunde #28 : Februarie 24, 2013, 10:58:06 » |
|
2 numere se considera egale daca abs( a-b ) < 10-5?
|
|
|
Memorat
|
|
|
|
•freak93
|
 |
« 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
Mesaje: 37
|
 |
« 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
|
 |
« Răspunde #31 : Februarie 24, 2013, 13:06:39 » |
|
Se putea mai bine de N lg N ? 
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
 |
« 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? 
|
|
|
Memorat
|
|
|
|
•danalex97
|
 |
« 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?  Poti sa imi detaliezi putin aici sau pe privat ? Am impresia ca puntele trebuiau sortate. Multumesc anticipat. 
|
|
|
Memorat
|
|
|
|
•visanr
|
 |
« 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
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
 |
« 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. 
|
|
|
Memorat
|
|
|
|
•harababurel
Client obisnuit

Karma: 23
Deconectat
Mesaje: 62
|
 |
« 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
|
 |
« 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  ). @ SebiSebi : Ce functie de hashing ai folosit ? LE : Ma refer la faptul ca aveai de retinut double-uri.
|
|
|
Memorat
|
|
|
|
•vladtarniceru
|
 |
« 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
|
 |
« 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
|
 |
« 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  Daca ai ceva de genul: (astea sunt distantele, "sa presupunem" ca se poate), atunci ce faci?
|
|
|
Memorat
|
|
|
|
•danalex97
|
 |
« 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. 
|
|
|
Memorat
|
|
|
|
•Steve
Client obisnuit

Karma: 36
Deconectat
Mesaje: 72
|
 |
« 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
|
 |
« 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 : 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
|
 |
« 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 
|
|
|
Memorat
|
|
|
|
•danalex97
|
 |
« 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
|
 |
« 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.
|
|
|
Memorat
|
|
|
|
•visanr
|
 |
« Răspunde #47 : Februarie 24, 2013, 13:45:47 » |
|
Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N) 
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
 |
« Răspunde #48 : Februarie 24, 2013, 13:46:45 » |
|
Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N)  OK. Nu ma asteptam sa mearga asa de prost hash-ul, dar se mai intampla.
|
|
|
Memorat
|
|
|
|
•vladtarniceru
|
 |
« Răspunde #49 : Februarie 24, 2013, 14:22:22 » |
|
E buna ideea intr-adevar ... bravo  Oricum, cred ca modulo-urile alea mananca o droaie de-a timp (cred ca de la asta ai atatea TLE-uri) 
|
|
|
Memorat
|
|
|
|
|