006 Factorial

[•fluffy]

Aici puteţi discuta despre problema Factorial.

[•malex]

am gasit formula la problema, insa imi ia doar 2 teste... mi-ati putea da un test mai cu susta sa imi dau seama unde pica?

[•Twister]

Teoderescu Andrei a scris in articolul despre cautare binara:

Cod:

1) Sa se gaseasca (daca exista) cel mai mic n natural astfel incat n! sa se termine in exact p<=10^8 zerori.
....
In prima problema trebuie sa observam prima oara ca numarul de zerouri in care se termina n! creste odata cu n, observatie evidenta datorita definitiei lui n!. Atunci, putem cauta binar valoarea lui n pentru care se verifca relatia din enunt. Recomand problema "Factorial" din arhiva de probleme InfoArena celor interesati de implementarea algoritmului.

Si cum faci generezi pentru toate numerele de la 1 la 10^8, n! pentru care  are exact p cifre de 0 la sfarsit, pentru ca daca e asa tot nu poti sa trimiti o sursa de 1.66 Gb pe net

Nu stiu ce a vrut sa zica in articol...  

[•wickedman]

asa cum zice in enunt, trebuie sa gasesti n pentru care n! are p cifre de 0 la sfarsit.
evident, nu trebuie sa generezi "n!" ca sa afli cate 0-uri are.

[•Twister]

Pai stai un pic, chiar daca nu generez n! si generez descompunerea de 2 si 5 ale lui n! cu un for, tot imi iese din timp la testele 5-20, iar daca vreau sa fac preprocesare nu pot sa trimit sursa din cauza dimensiunilor astronomice

[•filip]

eu am facut un program simplu, am dedus cateva lucruri.
Nu trebuie decat sa cautam 5-urile pentru ca oricum 2-uri vor fi "suficiente" pentru a forma 10.  
Tot imi iese din timp si am luat doar 30 d pcte.

Care este ideea cautarii binare in acest caz.

[•wickedman]

fie
f: N -> N, f(n) = numarul de 0-uri de la sfarsitul lui n!
f este o functie crescatoare (pe masura ca n-ul creste, numarul de 0-uri de la sfarsitul lui n! creste de asemenea)

"smenul" problemei este sa iti dai seama cum se calculeaza f(n). hint: vezi la ce putere apare 5 in descompunerea in factori primi a lui "n!".

cum f este o functie crescatoare, cautarea binara a lui n se aplica in urmatorul fel:
1. a = 0 si b = un numar suficient de mare
2. c = (a + b) / 2
3. daca f(c) < p  => cautarea se restrange in partea dreapta a intervalului [a, b]  (a = c + 1)
altfel cautarea se restrange in partea stanga (b = c - 1)
evident, daca f(c) = p inseamna ca numarul cautat este c
se repeta 2, 3

parcurgeti articolul despre cautare binara
http://info.devnet.ro/articole.php?page=art&art=29

[•malex]

eu am determinat formula, dar totusi nu merge exact.. eu v-am cerut un test sa imi dau seama unde imi apare eroarea...

[•andrei_m]

Si eu am rezolvat-o fara cautare binara si  primesc doar 90 de puncte.
Am retinut intr-un vector puterile lui 5 si intr-un altul nr. de zerouri corespunzator factorialului acestor puteri. Astfel 5! va avea un 0,25!.....6,125!......31 etc
Apoi am parcurs vectorul cu zerouri de la sfarsit spre 1 si  daca p>=zerouri adaugam la rezultat (p/zerouri )*putere si p devenea p%zerouri;
Rationamentul are si demonstratie matematica dar ia doar 90 de puncte!

[•adi_nm]

Nu este necesara cautarea binara in aceasta problema. Se poate porni de la o aproximatie a lui N si se cauta din aproape in aproape. Daca aproximatia este buna atunci la valori mari ale lui lui P esti foarte aproape de rezultat. Iar la valori mici merge o cautare liniara deoarece se face un numar mic de pasi.

[•diac_paul]

Eu am rezolvat problema tot cu cautare binara, ideea e foarte simpla (si explicata foarte bine i n articol si mai sus). Daca tin minte bine, si eu luam 90 de puncte pentru ca nu aveam in vedere ca raspunsul poate fi "-1" (in cazul in care nu exista nici un numar n care sa aiba EXACT p zerouri la sfarsitul factorialului sau).
24! - are 4 zerouri
25! - are 6 zeroiri
Deci pentru p=5 raspunsul este "-1"  
Presupun ca asta e motivul pt care ai luat 90 de puncte.

[•andrei_m]

Asta era problema...pe viitor trebuie sa fiu mai atent la descrierea problemei. Mersi de post.....altfel ma resemnam cu 90 de puncte

[•malex]

pb e usoara invers, daca stii n sa afli cate zerouri p sunt.. invers, apare o pb... unele nr sunt 5^x ... astfel initial consider eu ca am pt p zerouri imi trebuie n=p*5.. insa deoarece in cazul acelor nr 5^x trebuie sa determin pana la N-ul care l-am aflat eu cate nr de forma 5^x au trecut si astfel sa adun pt N-ul determinat pt puterea x la care am ajuns (x-1)*x/2 zerouri la P..
Astfel pot realiza ori ca am gasit n mai mare ori n mai mic, si incerc sa iau valorile n-5 si n+5 sa vad daca imi da p zerouri(dupa cum am spus este formula cu ajutorul careia pot determina f usor pt n dat cate zerouri am: este ceva de genul: n%5+(x-1)*x/2 unde x este ultima putere la care ajunge cel mai mare 5^x care apartine intervalului (1,n)).. daca nu imi dau, inseamna ca  nu este solutie, daca imi dau, afisez variabila...  

Cu toata aceasta regula simpla, nu inteleg unde imi este greseala... imi ies doar 3 teste..

[•Twister]

Spuneti-mi si mie va rog frumos daca sunt corecte rezultatele:
N!         numarul de zerouri de la sfarsit
25                 6
125               31
625               156
3125             781
15625           3906
78125           19531
390625         97656
1953125       488281
9765625       2441406
48828125     12207031
244140625   61035156
1220703125 305175781

Multumesc anticipat pentru tot

[•pirosl]

pb e usoara invers, daca stii n sa afli cate zerouri p sunt.. invers, apare o pb... unele nr sunt 5^x ... astfel initial consider eu ca am pt p zerouri imi trebuie n=p*5.. insa deoarece in cazul acelor nr 5^x trebuie sa determin pana la N-ul care l-am aflat eu cate nr de forma 5^x au trecut si astfel sa adun pt N-ul determinat pt puterea x la care am ajuns (x-1)*x/2 zerouri la P..
Astfel pot realiza ori ca am gasit n mai mare ori n mai mic, si incerc sa iau valorile n-5 si n+5 sa vad daca imi da p zerouri(dupa cum am spus este formula cu ajutorul careia pot determina f usor pt n dat cate zerouri am: este ceva de genul: n%5+(x-1)*x/2 unde x este ultima putere la care ajunge cel mai mare 5^x care apartine intervalului (1,n)).. daca nu imi dau, inseamna ca  nu este solutie, daca imi dau, afisez variabila...  

Cu toata aceasta regula simpla, nu inteleg unde imi este greseala... imi ies doar 3 teste..

Esti aproape de solutie ...mai trebuie sa verifici cate ceva. De exemplu pentru 125, tu obtii 125%5+(3-1)*3/2 = 125+2 = 127 care nu prea este corect. Gandeste-te de exemplu ca 50 o sa genereza 2 zerouri nu 1 cum te astepti tu (de exemplu 50*48=2400 deci mai ai inca 2 zerouri la rezulta.....la fel 75*72=5400...deci si aici ai 2 zerouri in plus la rezultat). Trebuie sa te uiti si cati multipli ai puterilor lui 5 ai pana la n ...... si problema ar trebui sa mearga.

[•bogdan2412]

Spuneti-mi si mie va rog frumos daca sunt corecte rezultatele:
N!         numarul de zerouri de la sfarsit
25                 6
125               31
625               156
3125             781
15625           3906
78125           19531
390625         97656
1953125       488281
9765625       2441406
48828125     12207031
244140625   61035156
1220703125 305175781

Multumesc anticipat pentru tot

Sunt corecte toate...

[•Twister]

Multumesc mult

[•spx2]

P este puterea la care trebuie sa apara 5
intr-un n!.
Asta pentru ca intotdeauna vor fi mai putini
5 decat 2 intr-un n!.Iar ca sa formam
zerouri la final avem nevoie si de 5 si de 2
dar cum de 5 sunt mai putini atunci numarul lor
conteaza mai mult ceilalti 2 care raman,raman
in treaba lor pe dinafara...

deci:
_________________________________________________________
calcularea valorilor ce vor fi precalculate in programul
final:
iau fiecare multiplu de 5 de la 1 la...
si vad daca pm5 adica puterea lui 5 sumata
pana aici este mai mica decat P.
ma opresc daca este mai mare.
cand ies din loop adaug si puterea la care
se afla 5 in urmatorul sau multiplu si daca
am egalitate intre pm5 si P inseamna
ca exista n ai n! sa aiba P zerouri si
bag intr-un vector SEPOATE[P]=1
salvez intr-un vector ultimul multiplu de 5
verificat sa-i zicem M5[P],altfel
inseamna ca bag intr-un vector SEPOATE[P]=0.

asta fac pt primele P<1000 de nr sa zicem.
apoi fac asa:

pt orice P>=1000 primul P' din spate pentru care
SEPOATE[P']=1 pornesc de la ultimul sau multiplu
de 5 adica M5'=M5+5 pornesc de aici si incep iar sa adun
puteri la P' pana cand P' devine P,daca sare de P
iarasi inseamna ca am SEPOATE[P']=0.
si ar trebui sa mearga repede.
La sfarsit afisez P,M5,SEPOATE pe 3 linii diferite
cu toate numerele intre 1 si 99.999.999 cu step
5000 asta inseamna ca afisez intrarile vectorilor
cu indicele 1,5001,10001,...etc .
_________________________________________________________
folosesc valorile astea in felul urmator.
caut cel mai apropiat 5000*i+1<=P
(astfel incat diferenta min[P-(5000*i+1)] ).
de la acel numar pe care il gasesc aici va intreb
pe voi ce sa folosesc ? cautare binara, un while,?
oricum dupa ce am gasit i inseamna ca mai am de calculat
de facut de aici cel mult

O(5000*log   99999999)=O(5000*11,44)=O(57200) operatii
           5
ceea ce e foarte putin
dar vectorii M5,SEPOATE vor trebui stocati in
memorie ceea ce va duce la o incarcare a memoriei
cu O(M5)+O(SEPOATE)=
O([(4*99999999)/(5000*1024)]kb)+O(99999999/(5000*1024))
4 asta vine de la marimea unsigned longului
nouarii reprezinta intervalu mare pe care lucrez
5000 e stepul
1024 e nr de bytes dintr-un kb.
=O(99999999/(1024*10^3)) aprox O(98kb)

dar am mai trimis odata o sursa cu 100kb si nu mi-a mers
incarcata.

Nu consider ca e fair chestia asta cu limita de
marime pe sursa.
ati vazut foarte bine ca nu a fost nici un brute-force
nicaieri si cred ca algoritmul nu triseaza in rezolvarea
problemei,ca atare solicit mai mult spatiu de la voi
adminii de server.
macar la vreo 150k,n-o sa moara nimeni,nici macar hdd-urile
voastre.

[VladS]

Vedeti ca gasiti pe mathworld cum se gaseste numarul de zerouri de la functia factorial. Parca s-a dat si la liis in runda 2.

[•cavendish]

Prima varianta pe care am trimis-o la pb asta a fost precomputare. in loc sa tii exact toate numerele, incearca sa tii din 10.000 in 10.000 si astfel stii cate zerouri sunt pana la un anumit nr si urmeaza doar sa verifici in cel mai rau caz pt urmatoarele 10.000, adica nu prea mult. Sursa avea si inca are 40.984 B si a luat doar 90 fiindca uitasem de '-1' .

Dar daca citesti atent posturile de pe topicu asta iti dai seama ca folosind cautarea binara problema devine 'mai naturala'.

[•spx2]

sursa mea a luat 5 puncte.
nu stiu de ce
lucrez cu unsigned longuri
si afisez si -1 cand e cazul
nu mai memorez numere precomputate
fac doar cautare binara si cu functie rapida
de aflare nr zerouri dintr-un factorial

[•mirceacnu]

1.          Nu stii sa faci cautare binara!
         2.          nr de zerouri a lui n factorial se calculeaza asa:
         nrz (nr de 0-uri)=n div 5+(n div 5 div 5)+......pana cand iti ajunge un termen la 0.

Nota: div iti returneaza catul impartirii.

[•Coty]

fie
f: N -> N, f(n) = numarul de 0-uri de la sfarsitul lui n!
f este o functie crescatoare (pe masura ca n-ul creste, numarul de 0-uri de la sfarsitul lui n! creste de asemenea)

"smenul" problemei este sa iti dai seama cum se calculeaza f(n). hint: vezi la ce putere apare 5 in descompunerea in factori primi a lui "n!".

cum f este o functie crescatoare, cautarea binara a lui n se aplica in urmatorul fel:
1. a = 0 si b = un numar suficient de mare
2. c = (a + b) / 2
3. daca f(c) < p => cautarea se restrange in partea dreapta a intervalului [a, b] (a = c + 1)
altfel cautarea se restrange in partea stanga (b = c - 1)
evident, daca f(c) = p inseamna ca numarul cautat este c
se repeta 2, 3

parcurgeti articolul despre cautare binara

cat de mare sa fie b ala intra in unsigned long long ca asa am gandit si eu, dar cand am vazut dimensiunile m-am oprit...

[later edit]
am incercat cu unsigned long long si b = maximul cat intra si merge... doar ca iau 85 de puncte, gresesc testul 1,3 si 15... au ceva special? am verificat si cazul cand tre sa afisez -1...

[•mist3rfi3ld]

pt TOTI..problema e super simpla....adik ai o cautare binara...pe acolo....doar nu vreti sa va zic rez.........da am o intrebare .....am o rezolvare impecabila....si iau doar 95 de puncte:D....nush de ce.....are ceva compilatoru....?//......solutia e buna is sigur de asta...

[u-92]

pierzi un caz particular