006 Factorial

[•andreicanta]

Imi puteti spune ce gresesc depaseste timpul de executie

Cod:

var nr,z,p,i:longint;
    f:text;
begin
  assign(f,'fact.in');reset(f);
  read(f,p);
  assign(f,'fact.out');rewrite(f);
  z:=0;i:=0;
  while z < p do
    begin
      inc(i,5);
      nr := i;
      while nr mod 5 = 0 do
        begin
          inc(z);
          nr := nr div 5;
        end;
    end;
  if z>p then
    writeln(f,-1)
  else if p = 0 then
    writeln(f,1)
  else
    writeln(f,i);
  close(f);
end.

Am incercat si cautare binara dar acolo la fiecare c (centru, mijloc) face descompunerea. Iar la mine face doar odata.
Ce am gresit ?

[•razyelx]

as dori sa imi comfirmati daca sunt bune urmatoarele deduceri

!n       cifre de zero

125     31
150     38
175     44
200     51

[•gabitzish1]

Nu prea sunt corecte. Uite rezultatele:
125 - 31
155 - 38
180 - 44
210 - 51

[•razyelx]

numa sa imi spuneti si mie preprocesare sau nu?

[•Mishu91]

Intra lejer si fara preprocesare

[•cata00]

1/5 + 1/25 + 1/125 + 1/625 + ... converge la 1/4 

[•neagu1000123]

deci.... am o problema... am facut binary search si am optimizat tot ce puteam, dar la 2 teste imi da tle (time limit execeded) ... am incercat sa schimb dr cu alata valoare decat 2000000000, dar in rest IMI DA MAI PUTIN    ... ajutor cineva ?


Multumesc anticipat

[•05_Yohn]

uita-te in pag 3 a topic-ului la primele 3 mesaje.. la fel ca si tine pierdea testele 3 si 15 .. succes

[•Bogdan_tmm]

Deci am si eu o problema.Am facut problema cu un soi de cautare binara,merge pentru testele din exemplu si totusi iau 0 puncte.Any idea?Crek fac ceva ce nu e permis in gnu dar totusi nu da eroare...

[•Mishu91]

Incearca si alte teste, nu numai pentru cele din exemplu. Uite cateva

Nu prea sunt corecte. Uite rezultatele:
125 - 31
155 - 38
180 - 44
210 - 51

[•Bogdan_tmm]

si pentru astea merge

[•criscer]

cum de creat o lista a numerelor prime in turbo pascal?

mersi anticipat

[•venom4u31]

Parerea mea este ca x trebuie neaparat sa fie divizibil cu 5... Programul meu imi iese, dar nu merge compilatorul , sau ce este pe site de da note la programe ... Problema ia destul de putin ... sper sa vad si eu cat am gresit ...

[•chibicitiberiu]

Salutare
Imi merge programul, dar nu si atunci cand nu gaseste nici un numar care sa indeplineasca conditiile: timp depasit. De asemenea compilatorul imi zice ca raspunsul e gresit dintr-un motiv necunoscut. Unde am gresit?

Cod:

#include<iostream.h>
#include<fstream.h>

ifstream in("fact.in");
ofstream out("fact.out");

int main()
{
	int p,ok=0,n,twos=0,fives=0,pp;
	in>>p;

	for(n=1;ok==0 && n>0;n++)
	{
		pp=n;
		while(pp%5==0 || pp%2==0){
			if (pp%2==0) { twos++; pp=pp/2;}
			if (pp%5==0) { fives++; pp=pp/5;}
			}

		if(twos>=p && fives>=p) ok=n;
	}

	if(ok==0) out<<-1;
	else out<<ok;

	out.close();
	in.close();

	return 0;
}

[•toni2007]

@Tiberiu

Sursa ta este ineficienta. Citeste cele 6 pagini ale topicului si vei vedea ca se rezolva cu cautare binara. Si acel test cu raspuns gresit il iei pentru ca nu afisezi -1 cand nu exista N cu proprietatea ceruta, tu afisezi -1 cand ok e 0, nefiind niciodata 0.

Uite codul aici:

Cod:

#include<iostream.h>
#include<fstream.h>

ifstream in("fact.in");
ofstream out("fact.out");

int main()
{
	int p,ok=0,n,twos=0,fives=0,pp;
	in>>p;

	for(n=1;ok==0 && n>0;n++)
	{
		pp=n;
		while(pp%5==0){
			if (pp%5==0) { fives++; pp=pp/5;}
			}

		if(fives>=p)
			ok=n;
	}

	if(fives != p) out<<-1;
	else out<<ok;

	out.close();
	in.close();

	return 0;
}

http://infoarena.ro/job_detail/240954



Vezi ca nu trebuie sa tii cont si de 2-uri, ele vor fi intotdeauna mai multe decat cinciuri. Astfel, timpul se reduce destul de mult, si prinzi inca 2 teste. Gandeste-te la solutia cu cautare binara.

Spor

[•madflame]

Propun o abordare fara cautare binara
Pentru P zerouri ne trebuiesc in N! sa apara 5 de P ori.
Intalnim un 5 la fiecare 5 numere, apoi intalnim un 5 in plus la fiecare 25 de numere, inca unu in plus la fiecare 125 de numere... si asa mai departe pana la 5^13 = 1220703125.
Plecand de la aceasta idee putem spune ca
P zerouri se gasesc in primele (P - (P div 5) - (P div 25) - (P div 125) - ... - (P div 5^13))*5 numere.
Rationamentul, zic eu, este corect, dar pe alocuri nu returneaza ce ar trebui.
Mi-a placut mai mult ideea aceasta deoarece algoritmul este minim...

EX: pentru P = 2 avem P * 5 = 10
               P = 7         (P - 1) * 5 = 30

Ma poate corecta cineva?

[•shnako]

Nu stiu de unde ai scos 5^13, dar am presupus ca ai dreptate. Mi-ar placea totusi sa stiu de unde l-ai scos.

Ideea ta in mare e buna, dar faci greseala fatala sa confunzi p cu n.
Exemplu:
Pentru p=5, algoritmul tau va da 20, dar raspunsul corect este 25.
Pentru p=31, algoritmul tau va da 115, dar raspunsul corect este 125.
Ideea e ca tu numeri cate numere sunt divizile cu n^k pana la numarul respectiv, cand tu defapt ar trebui sa numeri de cate ori apare numarul 5 pana la numarul respectiv.
5 in ecuatia ta va trebui inlocuit cu 6, 25 cu 31 si asa mai departe, conform urmatorului algoritm:

Cod:

#include <stdio.h>
#include <conio.h>
unsigned long t, s, i, n;
int main(void)
{
s=0;
scanf("%uld", &n);
for (i=1;i<=n/5;i++)
	{
   s++;
   if (i%5==0)
   	{
      t=i;
      while (t%5==0)
      	{
         s++;
         t/=5;
         }
      }
   }
printf("%ld", s);
getch();
return 0;
}

Inlocuind toate acestea iti va da urmatoarea formula:
p=p-p/6-p/31-p/156-p/781-p/3906-p/19531-p/97656-p/488281-p/2441406-p/12207031-p/61035156-p/305175781;
n=5*p;
Problema e ca am reusit sa iau doar 20 puncte cu ea, restul Wrong Answer.
Asta e forma la care am ajuns. Sper ca observa cineva ce am gresit ca la ora asta nu se prea mai invart rotitele.

Cod:

#include <stdio.h>
long long p, t;
int main(void)
{
freopen("fact.in", "r", stdin);
freopen("fact.out", "w", stdout);
scanf("%lld", &p);
if (p==0)
	printf("1");
else
{
t=p+1;
p=p-p/6-p/31-p/156-p/781-p/3906-p/19531-p/97656-p/488281-p/2441406-p/12207031-p/61035156-p/305175781;
t=t-t/6-t/31-t/156-t/781-t/3906-t/19531-t/97656-t/488281-t/2441406-t/12207031-t/61035156-t/305175781;
if (t==p)
	printf("-1");    

else
	printf("%lld", p*5);
}
fcloseall();
return 0;
}

Iar pentru varianta cu cautarea binara ... Poate spune cineva in detaliu ce caut cu el ? Ca pe forum am gasit numa bucati care nu se prea leaga. (P.S.: Nu imi explicati algoritmul ca il stiu, ci cum se implementeaza pentru problema asta ca nu reusesc sa-mi dau seama. Mersi.)

[•b_ady20]

Nu stiu de unde ai scos 5^13, dar am presupus ca ai dreptate. Mi-ar placea totusi sa stiu de unde l-ai scos.

Ideea ta in mare e buna, dar faci greseala fatala sa confunzi p cu n.
Exemplu:
Pentru p=5, algoritmul tau va da 20, dar raspunsul corect este 25.
Pentru p=31, algoritmul tau va da 115, dar raspunsul corect este 125.
Ideea e ca tu numeri cate numere sunt divizile cu n^k pana la numarul respectiv, cand tu defapt ar trebui sa numeri de cate ori apare numarul 5 pana la numarul respectiv.
5 in ecuatia ta va trebui inlocuit cu 6, 25 cu 31 si asa mai departe, conform urmatorului algoritm:

mdea... exista calculator si in windows ce are pana la 12 cifre sau depinde.. chiar mai multe.. cat despre idee este foarte buna, atat doar ca are nevoie doar de puteri ale lui 5 pana la 5^10 si probabil conditiile in caz ca p=5^x, unde x ia valori de la 1 la 10, nu le-a pus bine (prezinta cazuri particulare fata de formula lui) In rest cred ca este bine si chiar in acest moment ma chinuiam sa-l fac sa mearga 

[•madflame]

Ideea parea foarte ok... daca intreaga problema putea fi restransa la o formula era exceptional... dar nu este, mi-am dat seama dupa mult trial and error ce si cum.
5^13 este ultima putere a lui 5 care incape intr-un integer (4 byte int)
MACAR ca aproximatie bunicica ar putea fi folosita formula... am facut teste si greseste pentru numere mari undeva cam cu 8-9%, deci de la aproximatie spre numar se poate apela la un algoritm simplu de adunari repetate (sau fie... si cautare binara)

[•b_ady20]

Ideea parea foarte ok... daca intreaga problema putea fi restransa la o formula era exceptional... dar nu este, mi-am dat seama dupa mult trial and error ce si cum.
5^13 este ultima putere a lui 5 care incape intr-un integer (4 byte int)
MACAR ca aproximatie bunicica ar putea fi folosita formula... am facut teste si greseste pentru numere mari undeva cam cu 8-9%, deci de la aproximatie spre numar se poate apela la un algoritm simplu de adunari repetate (sau fie... si cautare binara)

Pai imbunatatind metoda ta intr-un fel am reusit sa iau 10 puncte, iar cu alogrimul meu intial (ce foloseste o alta metoda) am obtinut 25 de puncte... sincer nu imi dau seama din ce cauza, deoarece cel care foloseste formula e mult mai eficient, insa la unele teste imi da Raspuns Incorect. 
 

Cod:

var i,p:longint;    a:array[1..100000000] of longint;
    f:text;
begin
assign (f,'fact.in');
reset (f);
readln (f,p);
close (f);
if p=0 then
begin
assign (f,'fact.out');
rewrite (f);
writeln (f,1);
close(f);
end
else
begin
if p<=5 then
begin
assign (f,'fact.out');
rewrite (f);
writeln (f,p*5);
close (f);
end
else
begin
a[1]:=5;
for i:=2 to (p div 5) do
begin
a[i]:=a[i-1]+6;
end;
dec(i);
if p=a[i] then
begin
assign (f,'fact.out');
rewrite (f);
writeln (f,(p-(i-2)-((p*5) div (25*i)))*5);
close (f);
end
else
if p<a[i] then
begin
assign (f,'fact.out');
rewrite (f);
writeln (f,(p+(i-1)-((p*5) div (25*(i-1))))*5);
close (f);
end
else
begin
assign (f,'fact.out');
rewrite (f);
writeln (f,(p-(i-1)-((p*5) div (25*i)))*5);
close (f);
end;
end;
end;
end.

e in stare cam bruta, stiu.. dar am incercat atatea variante, sa obtin un algoritm mai optim decat cel de 25 de puncte, incat mi`a pierit orice chef sa imi mai scurtcircuitez creierii 

Editat de moderator: Era mai simplu si mai elegant sa folosesti tag-ul [ code ], in loc de:

[ color=green ][ b ][ b ][ b ][ shadow=red,left ]

[•pauldb]

Nu m-am uitat pe codul tau, desi presupun ca nu este pe ideea corecta. In schimb, mi-a sarit in ochi faptul ca declari 400 Mb (4 * 100 000 000, vectorul a). Iata una din greselile tale.

In plus, ar fi o idee buna sa va dezvatati sa mai postati codul tuturor problemelor care nu va ies. Nu e treaba comunitatii sa va depaneze sursele. O alternativa mai buna ar fi sa va ganditi de mai multe ori inainte sa incepeti sa codati si apoi sa incercati sa va gasiti greselile singuri.

[•shnako]

Nu m-am uitat pe codul tau, desi presupun ca nu este pe ideea corecta. In schimb, mi-a sarit in ochi faptul ca declari 400 Mb (4 * 100 000 000, vectorul a). Iata una din greselile tale.

In plus, ar fi o idee buna sa va dezvatati sa mai postati codul tuturor problemelor care nu va ies. Nu e treaba comunitatii sa va depaneze sursele. O alternativa mai buna ar fi sa va ganditi de mai multe ori inainte sa incepeti sa codati si apoi sa incercati sa va gasiti greselile singuri.

Am stat 4 ore si tot am cautat de ce nu merge. Dupa 4 ore am ajuns la concluzia ca ori o las balta ori va intreb si pe voi. Am preferat a doua solutie. E ceva rau in asta?

[•StefanFai]

Aflam 0-urile prin impartirea la 5.(deoarece numarul de 0-uri=numarul de perechi 2*5)
Normal,am putea sa ii spunem sa imparta si la 2,si la 5,dar doar am complica,deoarece tot timpul 5 va fi la putere mai mica.

Sunt sigur ca rezultatul a fost trimis de foarte mult timp,dar poate trece cineva pe aici sa-mi spune daca am gandit bine.(si da,mi-e lene sa citesc 100+ comentarii).

[•devilkind]

(si da,mi-e lene sa citesc 100+ comentarii).

Si mie imi e lene sa iti raspund. Baga o sursa si vezi daca merge sau nu.

[•Davide]

De cand 10! are mai putin de 2 cifre? Exemplul e gresit. 10! = 24320. Nu trebuie sa aiba mai mult de 2 cifre.

Ce sa zic... am uitat sa includ fisierele text...

[editat de moderator] foloseste butonul "modifica", nu mai posta consecutiv (e a doua oara in seara asta cand iti zic, nu?)