151 SuperP

[•domino]

Aici puteţi discuta despre problema SuperP.

[•points_hunter]

DAti si voi o idee de optimizare!

[•pauldb]

Ai putea sa le precalculezi...

[vladut.forum]

mai scapa si tu de cifrele inutile  

[•points_hunter]

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

[•Marius]

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 !

[u-92]

eu am 0.02 pur si simplu back fara nici o optimizare
incearca sa generezi numere super-prime, poate te prinzi

[•bogdan2412]

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

[•points_hunter]

Am luat 100. Era chiar usoara daca o faceai cu coada.
Multumesc tuturor pt. sfaturi

[dexer_100]

...

Vreau si eu programul cu superprim facut cu BTK nu conteaza recursiv nerecursiv pls. [email protected]

[•cos_min]

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?

[•filipb]

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...

[•cos_min]

mai am o intrebare : Cate numere super-prime is de 1,2,3,4...,8? io am calculat si mi-o dat km putine

[•tm_radu]

de 1,2 ,3 ...8 cifre sau formate din cifrele astea?

[•cos_min]

no formate din cifre alea , ci numarul de cifre maxim 8

later edit : gata am reusit 

[•sarabogdan]

M-am saturat de problema asta si cu back si cu preprocesare tot WA iau .  Al 156-lea numar superprim ii cumva 1979339339 ?

[•pauldb]

  Fie...sa mai ramana putin secretul

[•svalentin]

nuu, acum s-a dus secretul

[•Florian]

Am incercat vreo doua rezolvari diferite, dar iau doar WA...oare ce are pb asta?

[•Florian]

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??

[•nash]

  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 ...

[•Florian]

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?

[•marin]

1 considerat e prim?

[•wefgef]

Nu, 1 nu este considerat prim niciodata.

[•andrei-alpha]

Editat de moderator: Enuntul problemei e bun asa cum e.