•fluffy
|
|
« : Martie 08, 2004, 19:56:27 » |
|
Aici puteţi discuta despre problema Factorial.
|
|
|
Memorat
|
|
|
|
•malex
Client obisnuit
Karma: 6
Deconectat
Mesaje: 53
|
|
« Răspunde #1 : Ianuarie 24, 2005, 15:30:41 » |
|
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?
|
|
|
Memorat
|
Programarea e frumoasa daca o inveti logic..
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #2 : Ianuarie 28, 2005, 11:45:35 » |
|
Teoderescu Andrei a scris in articolul despre cautare binara: 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...
|
|
|
Memorat
|
|
|
|
•wickedman
|
|
« Răspunde #3 : Ianuarie 28, 2005, 15:29:54 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #4 : Ianuarie 28, 2005, 16:12:51 » |
|
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
|
|
|
Memorat
|
|
|
|
•filip
Strain
Karma: -1
Deconectat
Mesaje: 1
|
|
« Răspunde #5 : Ianuarie 28, 2005, 16:26:42 » |
|
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.
|
|
|
Memorat
|
|
|
|
•wickedman
|
|
« Răspunde #6 : Ianuarie 28, 2005, 20:25:38 » |
|
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
|
|
|
Memorat
|
|
|
|
•malex
Client obisnuit
Karma: 6
Deconectat
Mesaje: 53
|
|
« Răspunde #7 : Februarie 16, 2005, 08:32:02 » |
|
eu am determinat formula, dar totusi nu merge exact.. eu v-am cerut un test sa imi dau seama unde imi apare eroarea...
|
|
|
Memorat
|
Programarea e frumoasa daca o inveti logic..
|
|
|
•andrei_m
Strain
Karma: -1
Deconectat
Mesaje: 2
|
|
« Răspunde #8 : Februarie 16, 2005, 10:43:16 » |
|
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!
|
|
|
Memorat
|
|
|
|
•adi_nm
Strain
Karma: 0
Deconectat
Mesaje: 3
|
|
« Răspunde #9 : Februarie 17, 2005, 08:19:59 » |
|
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.
|
|
|
Memorat
|
|
|
|
•diac_paul
|
|
« Răspunde #10 : Februarie 17, 2005, 13:15:22 » |
|
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.
|
|
|
Memorat
|
|
|
|
•andrei_m
Strain
Karma: -1
Deconectat
Mesaje: 2
|
|
« Răspunde #11 : Februarie 18, 2005, 10:35:59 » |
|
Asta era problema...pe viitor trebuie sa fiu mai atent la descrierea problemei. Mersi de post.....altfel ma resemnam cu 90 de puncte
|
|
|
Memorat
|
|
|
|
•malex
Client obisnuit
Karma: 6
Deconectat
Mesaje: 53
|
|
« Răspunde #12 : Februarie 23, 2005, 22:39:08 » |
|
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..
|
|
|
Memorat
|
Programarea e frumoasa daca o inveti logic..
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #13 : Martie 18, 2005, 00:30:22 » |
|
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
|
|
|
Memorat
|
|
|
|
•pirosl
Strain
Karma: -2
Deconectat
Mesaje: 34
|
|
« Răspunde #14 : Martie 18, 2005, 11:08:51 » |
|
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.
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #15 : Martie 18, 2005, 11:21:47 » |
|
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...
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #16 : Martie 18, 2005, 18:05:49 » |
|
Multumesc mult
|
|
|
Memorat
|
|
|
|
•spx2
Strain
Karma: -1
Deconectat
Mesaje: 7
|
|
« Răspunde #17 : Martie 22, 2005, 20:01:13 » |
|
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.
|
|
|
Memorat
|
crack everything
|
|
|
VladS
Vizitator
|
|
« Răspunde #18 : Martie 22, 2005, 21:28:19 » |
|
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.
|
|
|
Memorat
|
|
|
|
•cavendish
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #19 : Martie 24, 2005, 00:49:11 » |
|
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'.
|
|
|
Memorat
|
|
|
|
•spx2
Strain
Karma: -1
Deconectat
Mesaje: 7
|
|
« Răspunde #20 : Martie 24, 2005, 13:27:25 » |
|
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
|
|
|
Memorat
|
crack everything
|
|
|
•mirceacnu
Strain
Karma: -16
Deconectat
Mesaje: 19
|
|
« Răspunde #21 : Martie 25, 2005, 08:51:34 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Coty
|
|
« Răspunde #22 : Martie 03, 2006, 09:49:25 » |
|
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...
|
|
|
Memorat
|
|
|
|
•mist3rfi3ld
Strain
Karma: -3
Deconectat
Mesaje: 4
|
|
« Răspunde #23 : Martie 07, 2006, 17:17:47 » |
|
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...
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #24 : Martie 07, 2006, 18:22:09 » |
|
pierzi un caz particular
|
|
|
Memorat
|
|
|
|
|