•repp4radu
|
|
« Răspunde #275 : Decembrie 20, 2012, 11:30:20 » |
|
Nu e chiar asa usor. Chiar si 20! iti iasa din orice tip de date. Trebuie sa gasesti o solutie mai buna la problema.
Hint: Incearca sa il scrii pe 10 (un 0 la final e echivalent cu numarul inmultit cu 10) ca fiind 2 * 5.
|
|
|
Memorat
|
|
|
|
•daviddaogaru
Strain
Karma: -1
Deconectat
Mesaje: 1
|
|
« Răspunde #276 : Ianuarie 11, 2013, 18:09:07 » |
|
[editat de moderator] Inteleg ca iti plac bananele, dar pe viitor te rog sa le tii doar pt tine.
|
|
« Ultima modificare: Ianuarie 11, 2013, 18:20:46 de către Dragos-Alin Rotaru »
|
Memorat
|
|
|
|
•Mihnea22
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #277 : Februarie 16, 2013, 18:45:06 » |
|
problema e simplă, și totuși foarte frumoasă dacă te apuci s-o „optimizezi”. nu știu dacă am voie sau nu să zic în comentarii rezolvări, așa că doar dau indicii. în primul rând după câteva încercări se vede că N și P sunt în dependență liniară (de gradul 1), așa că trebuie să existe o formulă între ei. acea formulă se află relativ ușor, sunt formule de liceu de la matematică, poate că de-aia mi-a venit ideea. acea formulă aproximează FOARTE aproape și mereu mai mic sau egal, deci căutarea e simplă. nu e nevoie de nicio căutare binară.
|
|
|
Memorat
|
|
|
|
•romyk
Strain
Karma: 5
Deconectat
Mesaje: 40
|
|
« Răspunde #278 : Februarie 17, 2013, 14:27:34 » |
|
Imi spune si mie cineva de ce nu imi merge codul asta #include<stdio.h>
long long int i,p,k;
int main(void) { scanf("%lld",&p); i=5*p; p=i; if(p>=25&&p%25!=0) { k=p/25; i-=k*5; } else if(p>=25) { k=(p-1)/25; i-=k*5; }
printf("%lld",i);
return 0; }
Am incercat exemplele astea si mi-a mers pentru toate: 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 Dar pentru astea nu: 10 000 000=40 000 010 99 999 999=400 000 010 24 165 865=96 663 485 23 750 754=95 003 040
|
|
|
Memorat
|
|
|
|
•Andru_
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #279 : Aprilie 04, 2013, 23:13:15 » |
|
Cred că nu merge ceva aici: program fact; var vector:array[0..12] of longint= (1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 1000000001); p,k,zerouri:longint; marime,i:byte; fin,fout:text; begin assign(fin,'fact.in'); reset(fin); read(fin,p); close(fin); marime:=0; while p>vector[marime] do marime:=marime+1; zerouri:=p; for i:=marime downto 1 do begin zerouri:=zerouri-p div vector[i]; if p mod vector[i]>=vector[i]-i then p:=-1; end; assign(fout,'fact.out'); rewrite(fout); if p=0 then write(fout,1) else if p=-1 then write(fout,-1) else write(fout,zerouri*5); close(fout); end.
|
|
|
Memorat
|
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
|
« Răspunde #280 : Aprilie 05, 2013, 23:53:42 » |
|
Problema are legatura cu puterile lui 5, nu cu raspunsurile pentru anumite puteri ale lui 5 din fisierul de intrare. Ca sa ai un 0 la final la rezultatul factorialului, trebuie sa observi din ce se formeaza.
|
|
|
Memorat
|
|
|
|
•theodor.nicolae
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #281 : Mai 25, 2013, 19:09:22 » |
|
Aveti probleme de incepator?
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #282 : Mai 25, 2013, 21:44:32 » |
|
In general, pe infoarena se pun probleme care pot contribui in mod semnificativ la pregatirea individuala (cu alte cuvinte, e greu de gasit o problema intr-adevar usoara pe infoarena). Iti recomand sa incerci de pe campion.edu.ro/arhiva problemele cadouri, psp, alo, case1, bancomat si barca (daca inca nu ai rezolvat problema capete). Iti urez succes si sa nu uiti niciodata ca toti am fost odata incepatori si ca vei depasi, daca inveti din placere, imediat momentul.
|
|
|
Memorat
|
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #284 : Iunie 26, 2013, 21:49:58 » |
|
Sa nu apelezi de doua ori functia. Ii stochezi valoarea returnata si apoi o folosesti de cate ori vrei
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #285 : Iunie 27, 2013, 03:02:11 » |
|
Complexitatea e log ^ 2 la problema asta, poti sa faci ce vrei cu constanta, trebuie sa-ti intre in timp. Daca iei TLE inseamna ca cicleaza. De exemplu, cred ca-ti cicleaza cand raspunsul e -1.
|
|
|
Memorat
|
|
|
|
•reking
Strain
Karma: 3
Deconectat
Mesaje: 39
|
|
« Răspunde #286 : Iunie 27, 2013, 09:07:46 » |
|
George Marcus:In while trebuie sa o apelez mereu pentru ca variabila mid se schimba. Mihai Calancea:Poti sa fii mai explic, te rog? Chiar nu inteleg de ce cicleaza cand raspunsul e -1.
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #287 : Iunie 27, 2013, 11:14:26 » |
|
Nu m-am uitat foarte atent dar cred ca daca nu ai solutie si se ajunge la min = max in while iti cicleaza.
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #288 : Iunie 27, 2013, 11:47:49 » |
|
if (fct(mid)<p) min=mid; else if (fct(mid)>p) max=mid; Aici ma refer. O apelezi de doua ori cu acelasi mid.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #289 : Iunie 27, 2013, 11:55:06 » |
|
Iti cicleaza fiindca ajunge la min = max cum spune Cosmin mai sus. Nu trebuie sa mai incluzi mid-ul in intervalul de cautare, stii deja ca nu e solutie.
|
|
|
Memorat
|
|
|
|
•reking
Strain
Karma: 3
Deconectat
Mesaje: 39
|
|
« Răspunde #290 : Iunie 27, 2013, 18:05:28 » |
|
http://www.infoarena.ro/job_detail/967457?action=view-sourceBun...am ajuns cu sursa pana in stadiul acesta. Am modificat din min<=max in min<max si am folosit o variabila 'val' care retine fct(mid) - ca sa n-o mai apelez de 2 ori. Diferenta nu s-a simtit...tot 50 de puncte iau Alte idei?
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #291 : Iunie 27, 2013, 18:18:10 » |
|
Pai iti cicleaza si cu min < max, nu asta era partea pe care trebuia sa o repari. Ti-am mai spus si in alt thread, invata sa-ti faci debug, sa vezi ce se intampla de fapt in cod. Pentru 5, daca nu gresesc, o sa-ti ruleze la infinit.
|
|
|
Memorat
|
|
|
|
•reking
Strain
Karma: 3
Deconectat
Mesaje: 39
|
|
« Răspunde #292 : Iunie 27, 2013, 19:38:54 » |
|
Stiu sa folosesc debug-ul dar...nu stiam ca asta era problema (ca cicla). Am rezolvat problema cu mersul in gol, iar acum a aparut alta: primesc WA pe cateva teste Sa fie de la cautare??? #include <iostream> #include <fstream> #define NMax 100000001 using namespace std; ifstream f("fact.in"); ofstream g("fact.out"); int fct (int x) { int a=5,rez=0; while (x/a) { rez=rez+x/a; a=a*5; } return rez; } int main () { int p,val; f>>p; if (p==0) g<<1; else { int min=1,max=NMax,mid; bool ok=false; while (min<max && !ok) { mid=(min+max)/2; val=fct(mid); if (val<p) min=mid+1; else if (val>p) max=mid-1; else ok=true; } if (ok) { while (mid%5) mid--; g<<mid; } else g<<-1; } }
PS:ms de pontul cu ciclarea
|
|
|
Memorat
|
|
|
|
•dragangabriel
Strain
Karma: 3
Deconectat
Mesaje: 9
|
|
« Răspunde #293 : Iunie 27, 2013, 21:09:26 » |
|
Inlocuieste Nmax cu 1 miliard, si pune in while min<=max
|
|
|
Memorat
|
|
|
|
•reking
Strain
Karma: 3
Deconectat
Mesaje: 39
|
|
« Răspunde #294 : Iunie 27, 2013, 21:17:13 » |
|
|
|
|
Memorat
|
|
|
|
•Eladiv
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #295 : Noiembrie 22, 2013, 10:33:53 » |
|
#include<iostream> #include<fstream> using namespace std; int main() { int p,t; ifstream f("fact.in"); ofstream g("fact.out"); f>>p; t=p/5; if(p%6==5) g<<-1; else { if(p==0) g<<1; else { if(p%5!=0) g<<(p-t)*5; else g<<(p-t+1)*5; } } return 0; }
Imi poate spunce cineva de ce iau doar 15 puncte?
|
|
|
Memorat
|
|
|
|
•stefy9815
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #296 : Februarie 12, 2014, 15:00:53 » |
|
Eu am rezolvat astfel problema..... cu toate ca rezultatele imi dau primesc decat 25 de puncte
#include<iostream> #include<fstream> using namespace std; ifstream f("fact.in"); ofstream g("fact.out"); int main() { int p,nr2,nr5,nr,x,k,minim; f>>p; nr2=0; nr5=0; nr=0; k=2; while(nr<p) { x=k; while(x%2==0) { nr2++; x=x/2; } while(x%5==0) { nr5++; x=x/5; } if(nr2<nr5) minim=nr2; else minim=nr5; nr=nr+minim; nr2=nr2-minim; nr5=nr5-minim; k++; } k--; if(nr==p) g<<k; else g<<"-1"; return 0; }
|
|
|
Memorat
|
|
|
|
•stefy9815
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #297 : Februarie 17, 2014, 14:50:01 » |
|
Eu am rezolvat astfel problema..... cu toate ca rezultatele imi dau primesc decat 25 de puncte
#include<iostream> #include<fstream> using namespace std; ifstream f("fact.in"); ofstream g("fact.out"); int main() { int p,nr2,nr5,nr,x,k,minim; f>>p; nr2=0; nr5=0; nr=0; k=2; while(nr<p) { x=k; while(x%2==0) { nr2++; x=x/2; } while(x%5==0) { nr5++; x=x/5; } if(nr2<nr5) minim=nr2; else minim=nr5; nr=nr+minim; nr2=nr2-minim; nr5=nr5-minim; k++; } k--; if(nr==p) g<<k; else g<<"-1"; return 0; }
Am probleme cu timpul. Ma poate ajuta cineva??
|
|
|
Memorat
|
|
|
|
•BaTDucK
Strain
Karma: 10
Deconectat
Mesaje: 19
|
|
« Răspunde #298 : Februarie 17, 2014, 22:21:33 » |
|
Eu am rezolvat astfel problema..... cu toate ca rezultatele imi dau primesc decat 25 de puncte #include<iostream> #include<fstream> using namespace std; ifstream f("fact.in"); ofstream g("fact.out"); int main() { int p,nr2,nr5,nr,x,k,minim; f>>p; nr2=0; nr5=0; nr=0; k=2; while(nr<p) { x=k; while(x%2==0) { nr2++; x=x/2; } while(x%5==0) { nr5++; x=x/5; } if(nr2<nr5) minim=nr2; else minim=nr5; nr=nr+minim; nr2=nr2-minim; nr5=nr5-minim; k++; } k--; if(nr==p) g<<k; else g<<"-1"; return 0; } Iti da "decat" 25 de puncte fiindca iti iese din timp(Time limit exceeded.). Din cate vad tu aflii si puterea lui 2, ceea ce este inutil fiindca puterea lui 2 va fi mai mare ca puterea lui 5. Poate te va ajuta si urmatorul post: Eu nu inteleg de ce trebuie cautare binara si nici nu prea inteleg implementarea in problema asta. Putem sa ne bazam doar pe cateva observatii matematice : 5*2 = 10, deci numarul de zerouri are legatura cu puterile lui 5. Deci p se poate calcula ca mai jos si mai gasim o observatie (4p<=n) : Asa ca putem calcula numarul de zerouri impartindu-l pe n la 5 pentru fiecare numar incepand cu n=4*p pana cand gasim numarul p cautat si se obtine o complexitate mai buna decat log2(P) cu doar 33 iteratii pentru p=10^8.
|
|
|
Memorat
|
|
|
|
•NarTooN
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #299 : Februarie 24, 2014, 19:40:40 » |
|
Am trimis problema gresita !
|
|
|
Memorat
|
|
|
|
|