006 Factorial

[•sima_cotizo]

10!=3628800. De atunci are 2 cifre de 0 la sfarsit...

[•wefgef]

@Davide: Ti-as sugera sa iti revizuiesti tonul din comentarii. In primul rand pentru ca vorbesti prostii, si in al doilea rand pentru ca ar fi spre binele tau daca iti doresti sa fii ajutat.

[•b_ady20]

Cod:

var a,b,stop,c,e,n,p:int64;
function f(c:int64):int64;
var fact:int64;
begin
fact:=1;
e:=0;
while c div fact<>0 do
begin
fact:=fact*5;
if c div fact=0 then
break;
e:=e+c div fact;
end;
f:=e;
end;
begin
assign (input,'fact.in');
reset (input);
read (input,p);
close (input);
if p=0 then
begin
assign (output,'fact.out');
rewrite (output);
write (output,1);
close (output);
halt;
end
else
if p<=4 then
begin
assign (output,'fact.out');
rewrite (output);
write (output,p*5);
close (output);
halt;
end;
a:=0; b:=p*5; stop:=0;
while a<=b do
begin
c:=(a+b-5) div 2;
if f(c)<p then
a:=c+1
else
if f(c)>p then
b:=c-1
else
begin
stop:=p; a:=b+1;
end;
end;
assign (output,'fact.out');
rewrite (output);
if stop<>0 then
if c mod 10=5 then
write (output,c)
else write (output,c-(c mod 10 - 5))
else
write (output,-1);
close (output);
end.

...Ma poate ajuta cineva cu vreun caz special, indicatie, orice pliz Chiar nu pot sa-mi dau seama de ce iau doar 55 de puncte  raman dator...

[•mihaionly]

Stie cineva ce-i cu testul 2?Nu iau mai mult de 95 de puncte din cauza lui.Am tratat caz particular pentru cand p este 0 sa afiseze 1 iar cautarea mi se opreste fie cand ok ia valoarea true(cand a gasit rezultatul) fie cand nu mai e valabila relatia a<c<b (a,b-capetele c-mijlocul)
http://infoarena.ro/job_detail/287713

[•Florian]

Cand gasesti C-ul, probabil tu il afisezi direct, insa trebuie afisat cel mai mare multiplu al lui 5, mai mic decat C.

[•mihaionly]

c-ul nu ia valori decât pe multiplii lui 5.Eu când calculez C-ul folosesc formulele:
C=(A+B)/2;
C-=C%5;

[•Florian]

Relatia asta nu e buna: a<c<b. Ar trebui sa fie a<=c<=b.

[•mihaionly]

Bine-ar fi fost să fie aia problema..Tot 95  .SecvenÈ›a pentru căutarea binară e asta:
 

Cod:

a=1;  
 b=5*p;  
 c=(a+b)/2;  
 c=c-c%5;  
 while(a<=c&&c<=b&&a<=b&&!ok)  
  {  
  fn=get(c); //get(c) returneaza zerourile pe care le are la sfarsit c!  
  if(fn==p)  
   {  
   ok=true;  
   i=c;  
   }  
  else if(fn<p)  
   a=c+1;  
  else  
   b=c-1;  
  c=(a+b)/2;  
  c=c-c%5;  
  }  

[•Florian]

Fa cautarea in intervalul [0, MAXINT]. Banuiesc ca afisezi -1, daca la sfarsit ok ramane false... Si la conditia din while, e suficient sa pui while(a<=b && !ok).

[•mihaionly]

În sfârșit .Nu trebuia să folosesc numai divizorii lui 5.La final numai trebuia să afișez i-i%5 ca să mă asigur.Thx

[•valentinrosca]

Pai fa-ti tu un test corect si incearca-l

[•valentinrosca]

folositi __int64

[•valentinrosca]

puteti sa-mi dati un test va rog

[•DraStiK]

puteti sa-mi dati un test va rog

testele oficiale nu se fac publice, dar incearca sa faci un program brut cu care sati generezi propriile teste si sigur vei gasi greseala (daca exista una)

[•valentinrosca]

Pai nici nu-mi trebuie.
Am gasit formula: n/5^1+n/5^2+.....+n/5^i
unde 5^i<=n
5^i=5 la puterea i
dar timpul de executie e prost.

[•klamathix]

Timpul de executie e ok . Nu cred ca ai fost prea atent la cerinta . Tu ai gasit acolo o functie pe care o poti folosi pentru a afla numarul de zerouri al lui N ! , insa ti se cere N minim pentru care N! are exact P zerouri, deci pe undeva exact invers . Poti totusi folosi functia asta la ceva Daca nu iese , citeste tot topic-ul .

[•valentinrosca]

Citat din mesajul lui klamathix:

Timpul de executie e ok . Very Happy Nu cred ca ai fost prea atent la cerinta . Tu ai gasit acolo o functie pe care o poti folosi pentru a afla numarul de zerouri al lui N ! , insa ti se cere N minim pentru care N! are exact P zerouri, deci pe undeva exact invers Smile. Poti totusi folosi functia asta la ceva Tongue Daca nu iese , citeste tot topic-ul .

Pai nu am folosit nici o functie
ci am folosit formula asta pentru a afla nr de 0 a lui n! n=n+1
dar eu am pus n=n+5 si nu-mi iese
dar stiu ca asta este formula
P.S. eu am facut asta pana cand nr de zerouri = p.  
Ai inteles!!!!!

[•DraStiK]

Citat din mesajul lui klamathix:

Timpul de executie e ok . Very Happy Nu cred ca ai fost prea atent la cerinta . Tu ai gasit acolo o functie pe care o poti folosi pentru a afla numarul de zerouri al lui N ! , insa ti se cere N minim pentru care N! are exact P zerouri, deci pe undeva exact invers Smile. Poti totusi folosi functia asta la ceva Tongue Daca nu iese , citeste tot topic-ul .

Pai nu am folosit nici o functie
ci am folosit formula asta pentru a afla nr de 0 a lui n! n=n+1
dar eu am pus n=n+5 si nu-mi iese
dar stiu ca asta este formula
P.S. eu am facut asta pana cand nr de zerouri = p.  
Ai inteles!!!!!

Ideea de baza este ca rezolvarea ta este ineficienta in raport cu timpul de executie

Iti sugerez sa citesti tot topicul pentru ca vei gasi informatii valoroase despre rezolvare.

[•valentinrosca]

Si unde gasesc topicul?
[editat de moderator]exces de emoticoane

[•gabitzish1]

Tocmai postezi in el...

[•sima_cotizo]

                   
 

In plus, nu mai face exces de smilies. Nu te ajuta nici in rezolvare, nici sa gasesti un utilizator care sa iti explice calm.

[•valentinrosca]

Pai am gasit alta solutie

Cod:

#include<math.h>
#include<fstream.h>
ifstream fin("fact.in");
ofstream fout("fact.out");
long p,n,i,j,x;
int main()
{
	fin>>p;
	if(p)
	{
		n=9;
		do
		{
			n++;
			x=0;
			for(i=5;i<=n;i=i+5)
			{
				ci=i;
				while(ci%5==0)
				{
					x=x+ci/5;
					ci=ci/5;
				}
			}	
		}
		while(x<p);
		if(x>p)
			fout<<"-1";
		else
			fout<<n;
	}
	else
		fout<<"1";
	return 0;
}

dar imi iese doar 10 pt

[editat] mai lasa smilieurile.

Acum, imi explica si mie cineva cum sa gasesc solutia,va rog.
Adresa mea de mail este [email protected]

[editat] nu mai posta consecutiv, foloseste butonul "modifica"

[•razyelx]

pe pagina 4, respectiv 5 vei afla ca trebuie sa folosesti cautare binara in intervalul [1 .. MAX]. In cautarea binara vei introduce formula de calculat zero-uri.

[•andrici_cezar]

am facut problema de 40 ... restu TLE  puteti sa imi ziceti si mie o metoda usoara de a afla cate numere de 0 are la sfarsit? ( 

Cod:

int nrz(long x)//x numarul caruia ii fac x!
    {
    nr0=0;//numarul de 0 de la sfarsit
    tmp=x;//auxiliar lui x
    while (tmp>0)
          {
          nr0+=tmp/5;
          tmp/=5;
          }
    return nr0;
    }

Deci aveti idei? Va rog sa imi ziceti  am incercat sa optimizez dar nu pot
P.s am citit tot forumu si nu am inteles ideea cu cautarea binara:((

[•andrici_cezar]

am reusit sa fac cu cautare binara dar pentru 10 mie imi zice 47 :d de ce?