483 Maxd

[•Whizzy]

Mie imi ruleaza problema in c++... si functioneaza dar cand o trimit imi zice ca fisierul de iesire lipseste  .. nu pot sa inteleg de ce ...  ma puteti ajuta si pe mine...?

[•c_e_manu]

poate ai gresit numele fisierului de iesire... 

[•Whizzy]

nu e gresit..  maxd.out e numele fisierului.. in c++ imi creeaza fisierul..

[•c_e_manu]

Si fisierul de intrare? Daca nu gasesti bug-ul, trimite-mi PM cu sursa si incerc sa te ajut.

[•Whizzy]

ok.. mersi mult

[•Bit_Master]

Mie-mi da sqrt(4) = 895.
O fi de la MinGW, ca nu-i prea bine facut?
Are un intreg istoric de probleme.

[•wefgef]

Ai grija la afisare, functia sqrt e pe double (atat parametrul cat si valoarea returnata).

[•Bit_Master]

Nu-i vorba de afisare.
Ma refer in calculul din timpul programului.
A trebuit sa scot din cod limita pana la radical.
Programul nu-i asa de optim, dar daca nu merge sqrt... ce sa fac
am pus tot felul de conversii
sqrt (nr)
(int) sqrt ((double) nr)
nu merge
In QuickWatch-ul din MinGW scrie val 800 nush cat.
Am mai patit sa afiseze gresit valorile MinGW dar cand trimiteam pe Infoarena sa mearga ok.

[•Cristian_B]

Nu inteleg de ce imi da TLE pe testul 6, in rest imi da pe toate .

[•mathboy]

Ai putea incerca sa pregenerezi primele 5200 de numere prime intr-un vector ca sa mai economisesti ceva timp 

[•SpiderMan]

Puteti sa-mi spuneti daca e bine cum am facut si daca intra in timp, eventual sa imi spuneti cum pot sa o imbunatatesc.(eu am facut fara fisiere,doar "schita", restul cu divizori si cu cate numere mai au acelasi nr. de divizori o sa fac eu (imi puteti spune cum det. cate nr. mai au acelasi nr. de divizori, eu cred ca la ultima structura repetitiva trebuie sa merg pana la capat).Merci

Cod:

program maxdiv9;
var a,b,i,g,p1,c,j:longint;
    stop:boolean;
    v:array[1..1000000] of longint;
    p:array[-1..1000000] of longint;
 begin
  write('a=');readln(a);
  write('b=');readln(b);
  stop:=false;
  for i:=a to b do
   p[i]:=1;
  for i:=2 to trunc(sqrt(b)) do
   if v[i]=0 then
    for j:=2 to b div i do
     v[i*j]:=1;
  for i:=a to b do
   begin
    for g:=2 to b div 2 do
    begin
     j:=i;
     c:=0;
      if v[g]=0 then
        while j mod g=0 do
         begin
          inc(c);
          j:=j div g;
         end;
       p[i]:=p[i]*(c+1);
    end;
    if p[i]>p[i-1] then
       p1:=p[i];
   end;
  i:=a;
  while not stop do
   if p[i]=p1 then
     stop:=true
    else
     inc(i);
  writeln('Cel mai mic numar care are numarul maxim de divizori din intervalul [',a,',',b,'] este ',i);
  readln;
 end.

[•alexandru92]

Folosesti prea multa memorie, limita este de 640 kbytes. Poti sa imbunatatesti ciurul , mai multe gasesti aici.

[•SpiderMan]

Hey am facut o "optimizare" la acest ciur, nu lucrez in c++ si nu stiu daca e bine , spuneti-mi voi. Merci. Am pus toata problema spuneti-mi ce as mai putea optimiza.Am facut-o fara fisiere si as vrea sa stiu cum as putea vedea cate numere mai au numarul maxim de divizori, trebuie sa parcurg la ultima structura repetitiva toata tructura? Merci

Cod:

program maxdiv9;
var a,b,i,g,p1,c,j:longint;
    stop:boolean;
    v:array[1..1000000] of boolean;
    p:array[-1..1000000] of byte;
 begin
  write('a=');readln(a);
  write('b=');readln(b);
  stop:=false;
  i:=4;
  while i<=b do
  begin
   v[i]:=true;
   i:=i+2;
  end;
  i:=3;
  while i<=trunc(sqrt(b)) do
  begin
   if v[i]=false then
   begin
    j:=i;
     while j<=b div i do
      begin
       v[i*j]:=true;
       j:=j+2;
      end;
   end;
  i:=i+2;
  end;
  for i:=a to b do
   p[i]:=1;
  for i:=a to b do
   begin
    for g:=2 to b div 2 do
    begin
     j:=i;
     c:=0;
      if v[g]=false then
        while j mod g=0 do
         begin
          inc(c);
          j:=j div g;
         end;
       p[i]:=p[i]*(c+1);
    end;
    if p[i]>p[i-1] then
       p1:=p[i];
   end;
  i:=a;
  while not stop do
   if p[i]=p1 then
     stop:=true
    else
     inc(i);
  writeln('Cel mai mic numar care are numarul maxim de divizori din intervalul [',a,',',b,'] este ',i);
  readln;
 end.

[•alexandru92]

Nu prea stiu C++

Defapt e in java. Nu sunt folosite lucruri pe care sa nu le stii plus pe topicul articolului gasesti niste comentarii utile
O alta imbunatatire este sa nu declari v ca  longint. El retine o valoare booleana( adica retine adevarat sau fals ). Poti sa nu mai initializezi vectorul, pui 0 - numar prim, 1 - nu-i numar prim.
ps: ideea era sa injumatatesti memoria folosita. v[ i ] - verifici daca 2*i+1 este sau nu prim

[•SpiderMan]

Cum sa injumatatesti? am facut-o aici ce am mai facut la ea sper ca e bine.

Cod:

program maxdiv9;
var a,b,i,g,p1,c,j:longint;
    stop:boolean;
    v:array[1..1000000] of boolean;
    p:array[-1..1000000] of byte;
 begin
  write('a=');readln(a);
  write('b=');readln(b);
  stop:=false;
  i:=4;
  while i<=b do
  begin
   v[i]:=true;
   i:=i+2;
  end;
  i:=3;
  while i<=trunc(sqrt(b)) do
  begin
   if v[i]=false then
   begin
    j:=i;
     while j<=b div i do
      begin
       v[i*j]:=true;
       j:=j+2;
      end;
   end;
  i:=i+2;
  end;
  for i:=a to b do
   p[i]:=1;
  for i:=a to b do
   begin
    for g:=2 to b div 2 do
    begin
     j:=i;
     c:=0;
      if v[g]=false then
        while j mod g=0 do
         begin
          inc(c);
          j:=j div g;
         end;
       p[i]:=p[i]*(c+1);
    end;
    if p[i]>p[i-1] then
       p1:=p[i];
   end;
  i:=a;
  while not stop do
   if p[i]=p1 then
     stop:=true
    else
     inc(i);
  writeln('Cel mai mic numar care are numarul maxim de divizori din intervalul [',a,',',b,'] este ',i);
  readln;
 end.

[•miculprogramator]

Cod:

var  ciur: array[1..10000];
var i, j, max : word;

Max := 10000;
for i:=2 to Max do
     ciur[i] := 1;
for i:=2 to Max do
    if ciur[i] = 1
       begin
           j := 2;
           while (i * j <= Max)
               begin
                ciur[i*j] := 0;
                j := j + 1;
               end;
      end;

for i:=2 to Max do
    if ciur[i] = 1
       write (' ', ciur[i]);

     

Cam asa ar veni ciurul in Pascal, scuza eventualele greseli, n-a mai scris de mult. Variantele de ciur din articol sunt mai bune si usor transformabile. Spre sa intelegi.

[•RoCky]

Am intr-un vector primele 4700 numere prime si fiecare numar din interval il descompun insa primesc TLE pe testele 1,2 si 6 .

[•SpiderMan]

Buna. Am facut problema iar la evaluator imi da KILLED BY SIGNAL 11. Am facut debug si zice asta:segmentation fault. Despre ce e vorba? Aici e sursa:

Cod:

#include <fstream>
#include <math.h>
using namespace std;


bool v[45000];
int contor=1,nrdiv=2,nrdiv1,j,k,contors;
int main()
{
     long long a,b,min=0,i;
     ifstream f("maxd.in");
     ofstream g("maxd.out"); 
     f>>a>>b;  
     for (i=2;i<=b;i++)
           v[i]=true;
         for (i=2;i<=sqrt(b);i++)
          if (v[i])
              for (j=i;j<=sqrt(b)/i;j++)
               v[i*j]=false; 
                      
     for (i=a;i<=b;i++)
     {
      k=i; 
      nrdiv1=1;  
         for (j=2;j<=sqrt(i);j++)
           if (v[j]==true)
           { 
             contors=0;                           
             while (k%j==0)
             {
               contors++;
               k/=j;
             }
             nrdiv1=nrdiv1*(contors+1);      
           }
     if (k>1)
       nrdiv1*=2; 
     if (nrdiv1==nrdiv)
        contor++;
     else if (nrdiv1>nrdiv)
          {
              contor=1;
              nrdiv=nrdiv1;
              min=i;
          }
     }
     g<<min<<" "<<nrdiv<<" "<<contor;
     f.close();
     g.close();
     return 0;
}         
                              
         
                      

[•mathboy]

Primesti KBS pentru ca depasesti limitele unui vector. Pentru detalii citeste : http://infoarena.ro/documentatie/evaluator .

[•SpiderMan]

STIU ASTA doar ca nu-mi dau seama de ce. Si ti-am zis am facut debug si mi-a dat eroarea:segmentation fault.

[•mathboy]

Uita-te mai bine la limite 1 ≤ a ≤ b ≤ 2000000000 iar tu ai forul asta :

Cod:

for (i=2;i<=b;i++) v[i]=true

E clar ca iti depaseste limitele impuse.
P.S : Data viitoare incearca sa citesti enuntul mai atent si sa iti repari singur greselile. Cu siguranta asa inveti ceva nou.

[•SpiderMan]

Am rezolvat am facut mai optimizat si a mers cu timpi mici

Am intr-un vector primele 4700 numere prime si fiecare numar din interval il descompun insa primesc TLE pe testele 1,2 si 6 .

Cum faci problema? adica ce algoritm folosesti ?

Editat de admin: Nu posta consecutiv pe aceeasi tema. Modifica mesajele anterioare.

[•dornescuvlad]

Mie imi depasea timpul pentru patru test, in cazul in care imi faceam un ciur de 4700 elemente, dupa ce am redus la 550, mi-a intrat in timp..desi ciurul era optimizat.Weird, nu cred ca alg.meu face asa de multi pasi.

[•TheNechiz]

Eu nu înțeleg
Am încercat să rezolv problema cu ciur și cu un tablou unidimensional pentru factori primi,dar obțin asta:
http://infoarena.ro/job_detail/761273

Asta e sursa:

Cod:

# include <iostream>
# include <cstdio>
# define max 45000

using namespace std;

int main(void){

    freopen ("maxd.in","r",stdin);
    freopen ("maxd.out","w",stdout);

    int k,r,j,prim[5500];
    long d,a,b,cif,x,max1,y,cont,i;
    bool ciur[max+1];

    k=2;
    max1=-1;

    for(i=2;i<=max;i++) ciur[i]=true;

    for(i=2;i<=max;i++)
        if(ciur[i]){
            j=2;
            while(i*j<=max){
                ciur[i*j]=false;
                j++;
            }
        if(ciur[i]) prim[k++]=i;
    }

    cin>>a>>b;

    for(i=a;i<=b;i++){
        y=i;
        d=1;
        k=2;
        while(y!=1){
            r=0;
            while(y%prim[k]==0){
                r++;
                y/=prim[k];
                }
            d*=(r+1);
            k++;
        }
        if(max1<d){
            max1=d;
            cif=i;
            cont=0;
            }
        if(max1==d) cont++;
    }

    cout<<cif<<" "<<max1<<" "<<cont;

    fclose(stdin);
    fclose(stdout);

    return 0;
}

După am încercat să găsesc altă metodă pentru aflarea numărului de divizori...am găsit ,dar iau TLE pe 4 teste:

Asta e sursa:

Cod:

# include <iostream>
# include <cstdio>
# include <cmath>

using namespace std;

int main(void){

    freopen ("maxd.in","r",stdin);
    freopen ("maxd.out","w",stdout);

    long a,b,max,cont,nrdiv,cif,i,j;

    cin>>a>>b;

    max=-1;
    for(i=a;i<=b;i++){
        nrdiv=2;
        long stop=sqrt(i);
        for(j=2;j<=stop;++j)
            if(i%j==0) nrdiv+=2;
        if(stop*stop==i) --nrdiv;
        if(max<nrdiv){
            max=nrdiv;
            cif=i;
            cont=0;
            }
        if(max==nrdiv) cont++;
    }

    cout<<cif<<" "<<max<<" "<<cont;

    fclose(stdin);
    fclose(stdout);

    return 0;
}

Mă poate ajuta cineva? 

[•MciprianM]

Gandeste-te ce valori ia k, respectiv prim[k] in primul program. SIGFPE inseamna ca imparti la 0.