•domino
|
|
« : Decembrie 12, 2005, 00:19:02 » |
|
Aici puteţi discuta despre problema SuperP.
|
|
|
Memorat
|
|
|
|
•points_hunter
Strain
Karma: -7
Deconectat
Mesaje: 26
|
|
« Răspunde #1 : Martie 18, 2006, 12:43:18 » |
|
DAti si voi o idee de optimizare!
|
|
|
Memorat
|
Intr-o lume plina de prostie si noobism Ceva mai increzator, putin mai oportunist Nihil sine DEO(Iubeste si vei fi iubit , Nu uita niciodata ca esti om)
|
|
|
•pauldb
|
|
« Răspunde #2 : Martie 20, 2006, 13:26:30 » |
|
Ai putea sa le precalculezi...
|
|
|
Memorat
|
Am zis
|
|
|
vladut.forum
Vizitator
|
|
« Răspunde #3 : Martie 20, 2006, 17:18:09 » |
|
mai scapa si tu de cifrele inutile
|
|
|
Memorat
|
|
|
|
•points_hunter
Strain
Karma: -7
Deconectat
Mesaje: 26
|
|
« Răspunde #4 : Aprilie 08, 2006, 22:55:44 » |
|
Nu reusesc sa ma prind de o rezolvare in 0.2 s. Elimin cifre inutile, insa poate exista caz in care poti alege toate cele 11-12 cifre, pentru care verificarea daca orice combinatie de cifre e superprima dureaza astronomic. Nu vad nici cum le-as putea precalcula. O idee eficienta ,gen ciurul lui Eratostene nu se incadreaza in memorie. Un mic indiciu poate m-ar ajuta.plss
|
|
« Ultima modificare: Aprilie 08, 2006, 23:00:40 de către points_hunter »
|
Memorat
|
Intr-o lume plina de prostie si noobism Ceva mai increzator, putin mai oportunist Nihil sine DEO(Iubeste si vei fi iubit , Nu uita niciodata ca esti om)
|
|
|
•Marius
|
|
« Răspunde #5 : Aprilie 08, 2006, 23:10:23 » |
|
O idee eficienta ,gen ciurul lui Eratostene nu se incadreaza in memorie. Eu am 0.05 s cu ciurul lui Eratostene! Arunca o privire aici http://info.devnet.ro/articole.php?page=art&art=30 !
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
u-92
Vizitator
|
|
« Răspunde #6 : Aprilie 08, 2006, 23:49:40 » |
|
eu am 0.02 pur si simplu back fara nici o optimizare incearca sa generezi numere super-prime, poate te prinzi
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #7 : Aprilie 09, 2006, 07:16:09 » |
|
Ca sa rezolvati problema in 0.01 trebuie doar sa va folositi de faptu ca un numar superprim este format de la un numar superprim cu o cifra mai putin adaugand o cifra la sfarsit... Evident numarul format trebuie sa fie prim... Daca le generezi cu o coada in care initial bagi numerele prime de o singura cifra poti sa generezi toate numerele superprime foarte rapid in 0.001... Nu e big deal sa gasesti solutia asta... PS: probabil ca am stricat farmecu de a gasi rezolvarea la problema asta da' asta e
|
|
|
Memorat
|
|
|
|
•points_hunter
Strain
Karma: -7
Deconectat
Mesaje: 26
|
|
« Răspunde #8 : Aprilie 09, 2006, 14:36:52 » |
|
Am luat 100. Era chiar usoara daca o faceai cu coada. Multumesc tuturor pt. sfaturi
|
|
|
Memorat
|
Intr-o lume plina de prostie si noobism Ceva mai increzator, putin mai oportunist Nihil sine DEO(Iubeste si vei fi iubit , Nu uita niciodata ca esti om)
|
|
|
dexer_100
Vizitator
|
|
« Răspunde #9 : Mai 29, 2006, 17:55:52 » |
|
...
Vreau si eu programul cu superprim facut cu BTK nu conteaza recursiv nerecursiv pls. [email protected]
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #10 : Iulie 07, 2006, 10:38:24 » |
|
io nu inteleg o chestie, am facut cu ciuru lui erast.. inainte de citire, sa det numerele prime, numa faza ii k nu imi intra in 0.2 secunde ! deci cum trebuie facut sa determin dak un nr este prim?
|
|
|
Memorat
|
vid...
|
|
|
•filipb
|
|
« Răspunde #11 : Iulie 07, 2006, 10:56:53 » |
|
Eu am facut verificarea unui numar prim in O(sqrtN) si am luat 100. Ai grija cum faci backul, poate ai TLE de la asta...
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #12 : Iulie 07, 2006, 12:09:04 » |
|
mai am o intrebare : Cate numere super-prime is de 1,2,3,4...,8? io am calculat si mi-o dat km putine
|
|
|
Memorat
|
vid...
|
|
|
•tm_radu
|
|
« Răspunde #13 : Iulie 07, 2006, 18:27:28 » |
|
de 1,2 ,3 ...8 cifre sau formate din cifrele astea?
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
•cos_min
|
|
« Răspunde #14 : Iulie 08, 2006, 11:13:41 » |
|
no formate din cifre alea , ci numarul de cifre maxim 8 later edit : gata am reusit
|
|
« Ultima modificare: Iulie 08, 2006, 11:43:39 de către cos_min »
|
Memorat
|
vid...
|
|
|
•sarabogdan
Strain
Karma: 4
Deconectat
Mesaje: 40
|
|
« Răspunde #15 : Iulie 11, 2006, 09:22:15 » |
|
M-am saturat de problema asta si cu back si cu preprocesare tot WA iau . Al 156-lea numar superprim ii cumva 1979339339 ?
|
|
|
Memorat
|
|
|
|
|
•svalentin
|
|
« Răspunde #17 : Iulie 11, 2006, 22:11:46 » |
|
nuu, acum s-a dus secretul
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #18 : Aprilie 08, 2007, 12:01:07 » |
|
Am incercat vreo doua rezolvari diferite, dar iau doar WA...oare ce are pb asta?
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #19 : Aprilie 11, 2007, 15:03:45 » |
|
Deci..eu am facut in urmatorul fel.: am ordonat cifrele descrescator...si le-am ales doar pe cele prime..cu exceptia lui 2 si al lui 5. Pe acestea doua le puneam numai dak erau cele mai mari...
Ex: pt 5234: ordonam: 5 4 3 2 - alegeam cifrele prime: 5 3 2..si eliminam numai 2, pastrand 5 -53 pt 2794653: ordonam: 7 6 5 4 3 2: alegeam 7 5 3 2 si eliminam 2 si 5 (pt nu sunt cele mai mari)-obtineam 73.. si mai exista cazul in care exista 2 cifre egale prime..afisam numai una...deci pt 977556 afisez 97.. Ce nu e bine in ratinamentul meu??
|
|
« Ultima modificare: Aprilie 11, 2007, 15:31:29 de către Marcu Florian »
|
Memorat
|
|
|
|
•nash
|
|
« Răspunde #20 : Aprilie 17, 2007, 11:19:35 » |
|
Eu fac ceva in genul urmator : pentru fiecare numar : - bag in coada toate cifrele distincte prime si retin maximul dintre ele in "max" - formez un vector caracteristic in care v[ i ]=numarul de cifre "i" . evident in acest vector nu voi retine decat valorile care adaugate la sfasitul unui numar prim pot sa dea tot un numar prim : 1 , 3 , 7 , 9 - pentru fiecare nod din coada ... : -calculez un vector v1[ i ] in care retin cate cifre au fost folosite de fiecare tip -si pentru fiecare cifra care nu a fost "epuizata" (v[ i ]-v1[ i ]>0) incerc sa vad daca se poate forma din nou un numar prim adaugand-o la sfarsitul numarului curent din coada ... in caz afirmativ noul numar il bag in coada ... Cu toate astea pe 9 din teste imi depaseste timpul de 0,2secunde .. si pe un test imi da raspuns gresit .. ... nu vad ce pot sa imbunatatesc .... si nici ce gresesc ... gata .. acum .. numai iese din timp ( facusem "prost" verificarea primalitatii ) dar acum da "raspuns gresit" poate sa imi spuna si mie cineva .. ce rezultat a avut pentru urmatorul test ? ( pentru 5 numere ) 5 2323 3684 1357792 7251730 11223344826 mie imi da : 233 3 7193 317 313 au incercat si o rezolvare prin back .. ( cei drept .. numai pe primele 4 teste intra in timp .. insa se mai poate imbunatatii destul de mult ) insa tot gresit imi da rezultatul ... ambele programe .. imi dau aceleasi rezultate ... ... pe ori si ce test ...
|
|
« Ultima modificare: Aprilie 17, 2007, 13:52:30 de către nash mit »
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #21 : Ianuarie 14, 2008, 20:10:41 » |
|
Cate numere superprime sunt pana la 10^12? Programul meu, imi spune ca 146. E corect? Iau wa si totusi pe testele mele imi da bine... LE: AM luat in cele din urma 80 cu 4 wa. Ce are special testul 1? [ Dati macat un hint ]. Multumesc. LE2: Am reusit sa iau 100. Insa nu sunt ferm convins care era problema. Cand construiam coada aia, avem while(p<=u && c [ u ] <= Max) (p=primu din coada, u=ultimu, Max=10^12). Am scos a doua conditie (ramanand doar while (p <= u) si am luat 100). Sunt numerele mai mari ca 10^12? Sau am atribuit eu gresit variabilei Max (am facut asa: Max=10.000. Max*=10000; Max*10.000; Max*=10000.), insa nu prea cred, intrucat in watch imi arata valoarea asteptata. Care sa fi fost problema?
|
|
« Ultima modificare: Ianuarie 14, 2008, 20:52:41 de către Marcu Florian »
|
Memorat
|
|
|
|
•marin
Strain
Karma: -1
Deconectat
Mesaje: 22
|
|
« Răspunde #22 : Martie 27, 2008, 17:46:03 » |
|
1 considerat e prim?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #23 : Martie 27, 2008, 20:18:18 » |
|
Nu, 1 nu este considerat prim niciodata.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #24 : Iulie 20, 2008, 18:17:58 » |
|
Editat de moderator: Enuntul problemei e bun asa cum e.
|
|
« Ultima modificare: Iulie 20, 2008, 20:54:27 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
|