483 Maxd

[•DITzoneC]

Aici puteţi discuta despre problema Maxd.

[•Dastas]

Vad ca sunt multe solutii care intra lejer in timp... cum aflati cati divizori are un numar? Eu fac fara ciur in O(sqrt(nr)) si nu intra in timp...

Sa calculez cu ciurul atatea numere prime iarasi nu cred ca ar intra in timp... deci ce mai ramane?

[•cos_min]

Intra in timp daca iti calculezi cu erast. numerele prime, dupa care sa faci descompunerea in factori primi in sqrtN. De aici te descurci  . In total iti vine undeva la O(N*sqrtN + N*sqrtN).

[•Dastas]

Da... a intrat

Multumesc!

[•ciprianf]

Pf....nu am inteles cum se face din e ziceti voi acolo...eu sunt clasa a 9a asa ca nu inteleg ce e O(log(...)) .. eu am pus intr-un vector toate numerele prime mai mici ca 2 milioane....si apoi am luat fiecare numar din intervalul [a,b] si l-am descompus in factori primi, am retinut puterile si am aplicat nrdiv=(1+p1)(1+p2)...(1+pr) unde p1..pr sunt puterile factorilor primi......si de aici ati inteles......dar iau KBS 11........care e varianta optima de rezolvare?

[•pandaemon]

Pf....nu am inteles cum se face din e ziceti voi acolo...eu sunt clasa a 9a asa ca nu inteleg ce e O(log(...)) .. eu am pus intr-un vector toate numerele prime mai mici ca 2 milioane....si apoi am luat fiecare numar din intervalul [a,b] si l-am descompus in factori primi, am retinut puterile si am aplicat nrdiv=(1+p1)(1+p2)...(1+pr) unde p1..pr sunt puterile factorilor primi......si de aici ati inteles......dar iau KBS 11........care e varianta optima de rezolvare?

Declarand un vector atat de mare, tu depasesti cu mult memoria alocata acestei probleme.

Pentru a genera solutia este nevoie doar de valorile dintr-un anumit interval. Incearca sa tii cont de chestia asta in rezolvare.

Bafta!

[•skyel]

in teste e inclus si cell mai prost caz(adica de la 1.999.980.000 la 2 miliarde)?? ca la mine pe calc la testu ala ia peste 0.5, iar pe site vad ca nu depasesc 52ms

[•Florian]

in teste e inclus si cell mai prost caz(adica de la 1.999.980.000 la 2 miliarde)?? ca la mine pe calc la testu ala ia peste 0.5, iar pe site vad ca nu depasesc 52ms

Nu. Nu e inclus.

[•recviem]

Pf....nu am inteles cum se face din e ziceti voi acolo...eu sunt clasa a 9a asa ca nu inteleg ce e O(log(...)) .. eu am pus intr-un vector toate numerele prime mai mici ca 2 milioane....si apoi am luat fiecare numar din intervalul [a,b] si l-am descompus in factori primi, am retinut puterile si am aplicat nrdiv=(1+p1)(1+p2)...(1+pr) unde p1..pr sunt puterile factorilor primi......si de aici ati inteles......dar iau KBS 11........care e varianta optima de rezolvare?

1. hehe, in primul rand logaritmii se fac in a 10-a ..
2. http://infoarena.ro/ciurul-lui-erathostene

[•shnako]

Daca gaseste careva de ce imi da Declaration Syntax Error pe linia cu void delete ii dau o bere. Stiu ca s-ar putea sa fie si alte erori da important e sa trec de asta. Mersi.

Cod:

#include <stdio.h>
long x[20001], i, s=1, t=1, p=0, d, z;
bool v[100000];

void delete (long k)
	{
   d=k;
   while (d<=z/k)
   	{
      v[k*d]=0;
      d++;
      }
   }

void ciur(z)
{
for (i=2;i<=z;i++)
  	v[i]=1;
delete(2);
for (i=3;i<=z;i=i+2)
 	if (v[i])
     	{
      s++;
     	delete(i);
      }
for (i=1;t=<s;i++)
   if (v[i])
   	v[t++]=v[i];
}


int main()
{
freopen("maxd.in", "r", stdin);
freopen("maxd.out", "w", stdout);
scanf("%ld%ld", &a, &b);
ciur(b);
for (i=1;i<=b-a;i++)
	x[i]=0;
for (i=1;i<=b-a;i++)
	for (j=1;j<=s;j++)
   	if ((i+a)%j==0)
      	a[i]++;
max=0;
for(i=1;i<=b-a;i++)
	if (v[i]>max)
   	max=v[i];
for (i=1;<=b-a;i++)
   {
   p++;
	if (v[i]==max)
		printf("%ld", i+a);
	}
printf("\n", "%ld", max, "\n");
printf("%ld", p);
fcloseall();
return 0;
}

[•gabitzish1]

"delete" e cuvant rezervat. Schimba numele functiei si ar trebui sa mearga.
Imi vreau berea!

[•shnako]

Aia era 
Daca esti din Arad sau ne intalnim la vreun ONI iti fac 3 beri nu una 

[•Pepelea_Flaviu]

stii sa faci bere ?

[•shnako]

Deci se pare ca problema asta nu vrea sa fie facuta ... Killed by signal 11(SIGSEGV) in toate testele. Am scos vectorul si tot aia imi da. Anyone know why?

Cod:

#include <fstream.h>
ifstream f("maxd.in");
ofstream g("maxd.out");
int x[20001];
long i, s=1, t=1, p=0, d, z, a, b, j, max, k, y;
bool sw;

void marcheaza(long k)
	{
   for (j=a/k;j<=b/k;j++)
   	x[k*j-a]++;
   }

void divizori()
	{
   for (i=2;i<=b;i++)
   	marcheaza(i);
   }

int main()
{
f>>a>>b;
for (i=0;i<=(b-a);i++)
	x[i]=1;
divizori();
max=0;
for(i=1;i<=b-a;i++)
	if (x[i]>max)
   	max=x[i];
for (i=0;i<=(b-a);i++)
   {
   if (x[i]==max)
   	p++;
	if (x[i]==max&&sw==0)
		{
		g<<i+a<<"\n";
      sw=1;
      }
	}
g<<max<<"\n"<<p;
f.close();
g.close();
return 0;
}

[•Florian]

Nu m-am uitat foarte atent, dar cred ca de la " x[k*j-a]++; " se trage. Ai grija ce valori ai in k*j-a. Vezi sa nu fie niciodata negative, sau sa nu depaseasca 20000.

[•c_e_manu]

da...cum zice florian...incearca pentru b=2 000 000 000 si a=1 999 980 000...am facut de mana si parca incerci sa marchezi x[-a]...deci de acolo ti se trage KBS11

[•shnako]

Deci pana la varianta asta am ajuns.

Cod:

#include <fstream.h>
ifstream f("maxd.in");
ofstream g("maxd.out");
int x[20001];
long i, s=1, t=1, p=0, d, z, a, b, j, max, k, y;
bool sw;

void marcheaza(long k)
	{
   for (j=a/k;j<=b/k;j++)
   	if (k*j!=k)
   		x[k*j-a]++;
   }

void divizori()
	{
   for (i=2;i<=b/2;i++)
   	marcheaza(i);
   }

int main()
{
f>>a>>b;
for (i=0;i<=(b-a);i++)
	x[i]=2;
divizori();
max=0;
for(i=1;i<=b-a;i++)
	if (x[i]>max)
   	max=x[i];
for (i=0;i<=(b-a);i++)
   {
   if (x[i]==max)
   	p++;
	if (x[i]==max&&sw==0)
		{
		g<<i+a<<"\n";
      sw=1;
      }
	}
g<<max<<"\n"<<p;
f.close();
g.close();
return 0;
}

Totusi hai sa o luam matematic.
Exact cand intra in for j=a/k. Daca inlocuim k*j-a=k*a/k-a=a-a=0. Sub zero nu ar avea cum sa scada.
Ultima oara cand intra in for are valoarea j=b/k. Daca inlocuim k*j-a=k*b/k-a=b-a care se garanteaza in problema ca nu depaseste 20000.
Deci matematic ar trebui sa mearga. Treaba ii ca si pe testul 200 200 mi se blocheaza in watch fix dupa acolada care inchide int mainu. Eu chiar nu reusesc sa-mi dau seama ce are ... Ma pricep si eu la erorile din C++ da deja cand ma umple de ferestre (am Borland 5 ca 3 nu merge  ) ma pierd. 

[•c_e_manu]

acum ai schimbat putin functia divizori...dar iti explic de unde iti iesea x[-a]....
luam b=2 000 000 000 si a=1 999 980 000
in functia ta cu divizori i ajungea la b si il dadea ca parametru...
a<b deci in c++ a/b=0 desi in matematica =0.(9) fiindca tu retii partea intreaga in int... int nu rotunjeste... eventual fa-ti o functie pentru a rotunji un numar...
si atunci cum j=0, k*j-a=0-a=-a... sper ca ai inteles acum ce am vrut sa zic...


acum un contraexemplu chiar si cu modificarea ta de i<=b/2...
luam cazul a=1 si b= 20 001...
acuma a<b/2... si mai departe se repeta...


daca am gresit in exemple va rog sa spuneti ca totusi e o ora destul de tarzie, cea la care am postat


LE: pe scurt uiti cazul in care j incepe de la 0 si de acolo ti se buseste tot codul... scuze pentru tot romanul de dinainte... am zis sa-l las ca e si explicat cate ceva pe acolo

[•anna_bozianu]

Chiar daca e putin probabil sa aiba legatura cu problema ta as vrea sa iti fac si eu doua recomandari. Prima ar fi sa nu folosesti aceeasi litera pentru o variabila (cazul lui k la tine) declarata global si un parametru de functie ( uneori poate sa iti induca anumite confuzii) iar a doua este sa nu abuzezi de functii asa cum faci tu in sursa ta cu functia marcheaza() Chiar daca nu e sursa KBS-ului tau, datorita consumului de timp cu apelurile, e posibil in unele cazuri sa iesi din timp si sa te trezesti cu TLE.

[•xtreme]

Cine ma poate ajuta iau TLE pe 3 teste...De ce?.... ...fak ciur pana la 45000 si dupa aia fac descompunerea in factori primi in sqrt nr...

Cod:

#include<iostream.h>
#include<stdio.h>
#include<math.h>

unsigned char ciur[45001];

int main()
    {
    unsigned long int a,b,i,j,nrmax=0,max=0,min=200000000,nr,e,panala,v[20001];long int dif;
    freopen("maxd.in","r",stdin);freopen("maxd.out","w",stdout);
    scanf("%ld %ld",&a,&b);
    for(i=2;i<=45000;i++)
              if(!ciur[i])
                  for(j=i+i;j<=45000;j+=i)
                        ciur[j]=1;
    dif=-1;     
    for(i=a;i<=b;i++)
             {nr=i;dif++;v[dif]=1;panala=sqrt(nr);
             for(j=2;j<=panala && nr>1;j++)
                      if(!ciur[j])
                            {e=0;
                             while(nr%j==0)
                                 {nr=nr/j;e++;}
                             v[dif]*=(e+1);}   
             if(nr!=i)
                     if(nr>1)
                         v[dif]*=2;}
    dif=b-a;
    for(i=0;i<=dif;i++)
             {if(v[i]>max)
                    {nrmax=0;min=i;
                    max=v[i];}
              else
                 if(v[i]==max) nrmax++;}                            
    printf("%ld %ld %ld",min+a,max,nrmax+1);
    fclose(stdin);fclose(stdout);                           
    return 0;
    }

[editat de moderator] Nu mai posta consecutiv. Daca are cineva o idee, te va ajuta. Nu insista.

[•shnako]

Deci din nou iau "Killed by Signal 11" pe 9 teste ... Am rescris tot programu pe alta idee si culmea tot acolo ajung
Raman recunoscator daca imi zice cineva de ce imi da Signal 11, avand in vedere ca am incercat vectorii de toate dimensiunile.
 

[•Florian]

Tu mergi cu i pana la w inclusiv, dar pozitia w nu exista in vectorul v[], pentru ca declari v[w], ceea ce inseamna ca aloca memorie pt elementele 0,1,2 ... w-1. Deci declara vectorul v[w+3], ca sa fii sigur ca nu iesi din el. Si mai e si chestia asta:

Cod:

	for (j=i;j*i<=b;j++)
         	v[j*i]=0;

Dupa cum probabil stii, b-ul este de 2 miliarde. Deci daca mergi cu i*j pana la 2 miliarde, e destul de logic ca nu ai vectorul v[] atat de mare. Mai baga acolo un " && i*j<=w ". Doar astea doua lucruri le-am observat. Fa modificarile, si probabil nu o sa mai iei KBS11.

[•shnako]

Tu mergi cu i pana la w inclusiv, dar pozitia w nu exista in vectorul v[], pentru ca declari v[w], ceea ce inseamna ca aloca memorie pt elementele 0,1,2 ... w-1. Deci declara vectorul v[w+3], ca sa fii sigur ca nu iesi din el. Si mai e si chestia asta:

Cod:

	for (j=i;j*i<=b;j++)
         	v[j*i]=0;

Dupa cum probabil stii, b-ul este de 2 miliarde. Deci daca mergi cu i*j pana la 2 miliarde, e destul de logic ca nu ai vectorul v[] atat de mare. Mai baga acolo un " && i*j<=w ". Doar astea doua lucruri le-am observat. Fa modificarile, si probabil nu o sa mai iei KBS11.

Asa era, mersi 

[•chibicitiberiu]

Sunt intr-a 9-a si n-am auzit de 'ciur'(??).

Dar am facut cum am stiut:
Mi-a dat la 3 teste timp depasit, iar la restul a mers, cum pot sa optimizez?

Cod:

#include <fstream>
#include <math.h>

using namespace std;

int calcdiv(int nr)
{
    int a=0,s;
    s=sqrt(nr);
    for (int i=1;i<=s;i++)
        if (nr%i==0) a+=2;
    return a;
}

int main()
{
    int max=0, maxi, a, b, no, c;
    ifstream in ("maxd.in");
    in>>a>>b;
    in.close();

    no=1;
    for (int i=a;i<=b;i++)
    {   c=calcdiv(i);
        if (c>max) { max=c; no=1; maxi=i; }
        else if (c==max) no++;
    }

    ofstream out("maxd.out");
    out<<maxi<<" "<<max<<" "<<no;
    out.close();
}

[•sima_cotizo]

Daca nu ai invatat despre ciur, invata despre ciur . Te vor ajuta problema din arhiva educationala si articolul despre ciur.