345 Nasa

[•aladin]

o alta idee??

[•cosmin79]

Salut. Am incercat si eu problema asta si nu inteleg de ce iau killed by signal 11 pe multe teste. Eu fac ciurul pt patratele numerelor prime pana in sqrt(b) si pe urma impart intervalul [a,b] in intervale de maxim 10^6 numere care reunite dau intervalul [a,b](cv de genu: [a,b]=[a,a+10^6-1] reunit cu [a+10^6, a+2*10^6-1] reunit cu... [a+k*10^6,b] si pt fiecare ciur pe un interval mic folosesc un vector de char de dimensiune 2^20 (>10^6) Ma lamureste cineva va rog ce gresesc? Mersi anticipat!

Later edit:Tot ce greseam era o singura linie: poz2=(poz/nr[j]+1)*nr[j];  poz2 putea depasi int.Las comentariul in caz ca mai are cineva vreodata problema asta.

[•robigi]

imi puteti spune pls cat spatiu ocupa o variabila de tip bool?    .. pt ca incerc sa folosesc un vector bool v[100 000 000] shi am memory limit exceeded

[•pauldb]

1 byte (octet). E normal sa iti iasa din memorie.

[•robigi]

aha, k ms    mie mi s-a parut ca e un bit 1/8 byte adica

si atunci cam ce ai, ati sugera?

[•toni2007]

Bitset.

[•robigi]

ok ms, imediat ce o sa aflu ce-i aia o sa incerc sa aplic

[•toni2007]

http://www.cplusplus.com/reference/stl/bitset/

[•tzipleatud]

Am scris o sursa in care am respectat indicatiile din comentariile anterioare (pt fiecare nr. prim <sqrt(b) am marcat multipli patratului acestuia din intervalul [a,b]) dar iau 60p cu restul TLE. Am citit despre anumite operatii pe biti dar nu imi dau seama ce operatii si unde sa le folosesc. Daca imi puteti da un mic hint despre aceste operatii,va rog . Multumesc anticipat!

[•danalex97]

Si eu iau 60p , am facut un ciur cu nr prime si unul in care marchez nr de la A la B. Tot tle. Cine a mai rezolvat problema , va rog , putin ajutor...

[•ctlin04]

Nustiu cum ai facut tu ca nu prea am chef sa ma uit pe sursa ta la ora asta, insa niste indicii pentru a lua 100 cred ca ar fi:
1. Mergi si controleaza doar multipli la patrate de numere prime;
2. Gindestete cum pentru un patrat fixat fie el p sa faci (b-a)/p oparatii pentru a-l prelucra;
3. Cind faci ciurul mergi doar pe numere impare cazul x=2 tratindu-l aparte, defapt aceasta optimizare m-a ajutat si pe mine sa iau 100 ca fara ea ultimul set de teste mergea la limita si e clar ca nu se nimerea ca sa mearga tot setul odata.
Cam asta. SPOR  

[•Steve]

Mie mi-a intrat lejer cu o metoda neoptimizata, dar care nu folosea STL...Incearca sa faci bitset-ul de mana, ca nu-i mare chestie sa scrii 2 functii inline / macrouri. N-ai nevoie de long long...baga toate variabilele pe uint. Faci chestiile astea si dublezi viteza.

[•danalex97]

Am incercat ambele , ceva imi scapa  . Daca imi poate da cineva sursa prin PM raman recunoscator. Nu ma prind nicicum. 

[•ctlin04]

Ti-am trimis PM, dar ma uit ca si sursa ta e buna doar ca ultimul for e prea costisitor, trebue sa numeri numerele pe care le excluzi deodata cind prelucrezi patratele nr prime   

[•danalex97]

@Catalin: 10x.   Asta era.
@Steve: Ai dreptate , bitset de mana merge mult mai rapid. 

[•lucian666]

Buna seara.
Am complexitatea ceruta ,dar iau doar 20 pct cu Killed by signal.
Codul care imi nr numerele cerute:

Cod:

 for(int i=2;i<=BB;i++)
        {
            int x=0;
            int number= i*i;
            ciur2[number]=1;
            if( number < A )
                if( A % number )
                    x=A/number+1;
                else
                    x=A/number;
            else
                 x=1;
                 while( 1LL * (number * x) <=B )
                {
                    ciur2[number*x]=1;
                x++;

                }

BB=sqrt(B). vectorul ciur e de tip bitset si are 100 milioane de elemente

Vreo sugestie cum pot scapa de Killed By Signal?
Multumesc Anticipat!!!

[•vendetta]

Ai grija ce bagi in ciur2;in acel while cred ca la un momendat bagi numere mai mari ca si 100 de milioane; m-am uitat si peste ultima sursa trimisa de tine si ai la sfarsit for(int i=A; i<=B; ++i) if ( ciur2[ i ] ) blaala...; acel i depaseste 100 de milioane

[•lucian666]

Ai grija ce bagi in ciur2;in acel while cred ca la un momendat bagi numere mai mari ca si 100 de milioane; m-am uitat si peste ultima sursa trimisa de tine si ai la sfarsit for(int i=A; i<=B; ++i) if ( ciur2[ i ] ) blaala...; acel i depaseste 100 de milioane

Si cum as putea face astfel incat sa nu-mi depaseasca 100 mil?  eu  trebuie sa marchez toti multiplii numarului <=b si oricum trece de 100 milioane la un moment dat
Mersi