006 Factorial

[•yonatan]

Am luat 100  . Multumesc.

[•mening12001]

Cod:

#include<iostream.h>
#include<fstream.h>
#include<string.h>
int main()
{long a,b=1,i=2,c=1;
ifstream f("fact.in");
ofstream g("fact.out");
f>>a;
for(i=1;i<=a;i++)
b=b*10;
while(c%b!=0)
{c=c*i;
i++;}
g<<i;
return 0;}

 
daca privim logic..algoritmul trebuie sa mearga perfect...dar desigur..iau 5 pct daor la prima verificare..dupa care la a2a gresit iar de la 3 la 10 afiseaza mesajul "Killed by signal 8(SIGFPE)"...ceea ce inseamna ca undeva se imparte la 0.Asa fiind am observat ca in "for" se intampla ca b=0..ptr valori imense ale lui "a"..respectiv "p" din problema.Sfaturi?

[editat de moderator] foloseste tagul "code"

[•stocarul]

Păi nu e prea bună abordarea.
La rândurile:

Cod:

for(i=1;i<=a;i++)
b=b*10;

b va primi 10^a. Iar cum a este destul de mare, chiar uriaș pentru ce faci tu aici, b va depăși cu mult valoarea tipului de date int/long, sau orice alt tip de date din c/c++.

Citește întreg topic-ul. Sigur vei găsi descrisă o metodă de rezolvare.
Spor.

[•lsorin_94]

folosesc nrcif(n)=n div5 +n div 5 div 5+.... shi asa mai departe ... ceva nu e bn??? iau 15 pcte..

Later Edit: de ce nu scrie tmpul pe care il facemm?

Later Later Edit:
imi merce pe toate ex date in topikurile de mai jos.. dar imi iese din timp.... ce sa fac...

Cod:

program factorial;
var k,n:longint;
    f,t:text;

function fact(n,k:longint):longint;
var x:int64;
    i:longint;
begin
  x:=n;i:=0;
  repeat
    i:=i+x div 5;
    x:=x div 5;
    if i>k then break;
  until x=0;
  fact:=i;
end;

function cif(k:longint) :int64;
var i,x,h,n:longint;
    da:boolean;
begin
  n:=maxlongint;
  for i:=1 to n do
    begin
      x:=fact(i,k);
      if x=k then
        begin
          da:=true;
          h:=i;
          break;
        end;
      if x>k then break;
    end;
  if da then cif:=h
        else cif:=-1;
end;

begin
  assign(f,'fact.in');
  reset(f);
  read(f,k);
  close(f);
  n:=1;
  {------------------}
  if k=0 then k:=1
         else k:=cif(k);
  {------------------}
  assign(t,'fact.out');
  rewrite(t);
  write(t,k);
  close(t);
end.

Editat de admin: Nu mai posta consecutiv. Tagurile "code" se pun intre paranteze drepte.

[•dornescuvlad]

Pai iti iasa din timp pentru ca algoritmul folosit iti iasa din timp, si ... trebuie sa memorezi numarul ca sir de caractere, nu longint  .

foarte adevarat graiesti...buna explicatie =)))

[•SpiderMan]

Am vrut sa spun ca este ineficient, m-am incurcat 

[•gabitzish1]

Cand n'ai nimic de zis.. mai bine nu zici nimic! 
Chiar daca intentia ta e buna, de a ajuta... sfaturile gresite nu sunt bune pentru incepatori. Pe langa explicatia plina de logica cu "iasa din timp", si indicatia de a memora numarul ca sir de caractere e aiurea.

[•SpiderMan]

Sczue m-am incurcat cu un alt post scuze din nou 

[•idomiralin]

Am incercat sa rezolv cu cautare binara. Am facut o functie, in care aflu de cate ori se imparte un numar la 5, iar in programul principal folosesc cautare binara (st=0;dr=1000;mij=(st+dr)/2;).Apelez functia cu acel mij(daca f(mij) = p atunci returnez mij altfel daca f(mij)<p st = mij + 1; altfel dr = mij - 1; si imi da intotdeauna -1.nu gaseste niciodata valoarea. Este gresit rationamentul?
 

[•alexandru92]

Am incercat sa rezolv cu cautare binara. Am facut o functie, in care aflu de cate ori se imparte un numar la 5, iar in programul principal folosesc cautare binara (st=0;dr=1000;mij=(st+dr)/2;).Apelez functia cu acel mij(daca f(mij) = p atunci returnez mij altfel daca f(mij)<p st = mij + 1; altfel dr = mij - 1; si imi da intotdeauna -1.nu gaseste niciodata valoarea. Este gresit rationamentul?

1. Pot fi mai multe valori pentru care f( mij ) == p, tu o vrei doar pe cea mai mica.
2. Ai implementat corect functia f ?

[•idomiralin]

Imi gaseste valoarea, da nu pe cea mai mica. Am pus conditia daca (f(mij) = p && mij<val) atunci {val = mij;dr=mij-1;}(asa ma gandeam sa o gasesc pe cea mai mica),si am initializat val cu 1000 la inceput, dar se blocheaza compilatorul cand fac asa.

Edit:
Am facut direct in main pana la urma.

Cod:

while (st < dr)
     {
            mij = (st + dr)/2;
            a = mij; ct = 0;
            while (a % 5 == 0)
            {
            if (a % 5 == 0) {
                        ct++;
                        a = a / 5;
                        }
            }           
            if (ct == p && mij < val)  {val = mij; dr = mij - 1;}
            else
            if (ct < p && ct > 0)  st = mij + 1; 
                       else dr = mij - 1;
                       }

Editat de moderator: Nu mai posta de mai multe ori consecutiv, editeaza-ti posturile anterioare.
Foloseste tagurile [ code ] [ /code ] cand postezi cod.
             

[•SpiderMan]

Sunt curios st si dr cum le-ai initializat inainte ?
Eu am facut asa : am aflat valoarea cum a fost (adica nu neaparat cea mai mica), si apoi am facut un for : for(;mij % 5;mij--) ; , care verifica daca restul impartiri lui mij la 5 nu este 0, decrementandu-l pe mij pana ajunge la o valoare care se imparte exact la 5 (deoarece ea este cea mai mica). Apoi verific daca ea este solutie, si daca nu afisez -1.

[•deiosx]

Am facut si eu mot-a-mot adica am luat un for de la cinci si am mers din cinci in cinci...
Ideea e ca nu-mi merge si-mi da eroarea asta ciudata ca nu pot sa o descalcesc:

Eroare de compilare:
In file included from /usr/include/c++/4.2/backward/fstream.h:31,
                 from user.cpp:1:
/usr/include/c++/4.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
user.cpp: In function 'int main()':
user.cpp:21: error: name lookup of 'i' changed for new ISO 'for' scoping
user.cpp:11: error:   using obsolete binding at 'i'
   

Acuma sa fiti si voi in materie va dau si codul:

Cod:

f>>o;
int s=0,q=0;
if(o!=0)
{
for(int i=5;s<=o;i=i+5)
{
q=i;
while(q%5==0)
{
s=s+1;
q=q/5;
}
}
if(s!=o)g<<-1;
else g<<i;
}
else g<<1;

Ps in C++ nu are nici o eroare.

[•SpiderMan]

Declara i global, sau in interiorul main-ului si ar trebui sa mearga ( adica sa nu il declari in for ) .

[•deiosx]

Tnx
A mers.
Da' ce-i cautarea binara(cu for la mai toate am TLE)...
 

[•alexandru92]

Tnx
A mers.
Da' ce-i cautarea binara(cu for la mai toate am TLE)...
 

http://infoarena.ro/problema/cautbin

[•Patrunjel]

Salut,eu am folosit un if(N%10==5 || N%10==0) .Pur si simplu nu am gasit alt numar,care inmultit cu oricare alt numar (inafara de 5 si 10) sa dea ultima cifra 0.Mai exista asa ceva?Eu m-am luat dupa ultima cifra,care poate fi 1,2,3,4,5,6,7,8,9,0 ,si i-am scos din calcul pe 5 si pe 0,deoarece 0 nu are nevoie de pereche,si 5 formeaza pereche cu unul dintre numerele pare dinaintea lui.Totusi nu merge.Asta e sursa:

Cod:

#include<fstream.h>
int main(){
	int P,N,i,nr=0;
	ifstream fin("fact.txt");
	ofstream fout("fact1.txt");
	fin>>P;
	for(N=1;;N++){
		if(N%10==0 || N%10==5)
			nr++;
		if(nr==P){
			fout<<N;
			break;}}
	return 0;} 

Un sfat?

[•devilkind]

Hint: 25 * 4 = 100

[•R.A.R]

Citeste ce s-a discutat si iti vei da seama ce gresesti.De exemplu,cand inmultesti cu 25,se adauga 2 de 0 iar cand inmultesti cu 125,3(asta depinde de puterea lui 5 care apare in descompunerea numarului in factori primi).

[•hunter_ionutzzz]

hmm....interesanta o chestie se ia  1*2*3*...*30 de ex are in total 6 zero la sfarsit  se ia de 3 ori  2*5  (2-5,12-15,22-25)  si de 3 ori 10 (10,20,30) si ajung la formula simpla ca n*5= raspuns dar totusi nu nimeresc testele.DC?

[•pauldb]

Pentru ca mai poti scoate un 0, de exemplu din 14 - 25.

[•crisjony]

Cod:

var k,n,i,m:longint;
begin
     n:=0;i:=0;k:=0;
     while k<p do
     begin
          inc(n);m:=n;
          while m mod 5=0 do
          begin
               inc(k);
               m:=m div 5;
          end;
     end;
     determinare:=n;
end;

procedure afisare;
var g:text;
begin
     assign(g,'factorial.out');
     rewrite(g);
     write(g,determinare);
     close(g);
end;

begin
     citire;
     determinare;
     afisare;
end.

si imi da 0  

[editat de moderator] foloseste tag-ul "code" cand postezi cod pe forum!

[•pauldb]

Bine iti face. Daca ai fi citit ce s-a discutat pana acum la aceasta problema ai fi stiut ce gresesti.

[•slilverwolf]

Cel mai eficient algoritm este urmatorul:
Zerouri n! = (n - suma cifrelor in baza 5 a lui n)/4.

[•toni2007]

Nu te cred.