006 Factorial

[•repp4radu]

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.

[•daviddaogaru]

[editat de moderator] Inteleg ca iti plac bananele, dar pe viitor te rog sa le tii doar pt tine.

[•Mihnea22]

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ă.

[•romyk]

Imi spune si mie cineva de ce nu imi merge codul asta

Cod:

#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

[•Andru_]

Cred că nu merge ceva aici:

Cod:

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.

[•NicuCJ]

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.

[•theodor.nicolae]

Aveti probleme de incepator?

[•Andrei1998]

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.

[•reking]

http://www.infoarena.ro/job_detail/967027?action=view-source
Ce as mai putea sa fac sa-mi intre in timp sursa?
Primesc TML pe 10 teste 

[•PlayLikeNeverB4]

Sa nu apelezi de doua ori functia. Ii stochezi valoarea returnata si apoi o folosesti de cate ori vrei

[•klamathix]

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.

[•reking]

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.

[•darkseeker]

Nu m-am uitat foarte atent dar cred ca daca nu ai solutie si se ajunge la min = max in while iti cicleaza.

[•PlayLikeNeverB4]

Cod:

if (fct(mid)<p) min=mid;
else if (fct(mid)>p) max=mid;

Aici ma refer. O apelezi de doua ori cu acelasi mid.

[•klamathix]

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.

[•reking]

http://www.infoarena.ro/job_detail/967457?action=view-source

Bun...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?

[•klamathix]

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.

[•reking]

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???

Cod:

#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

[•dragangabriel]

Inlocuieste Nmax cu 1 miliard, si pune in while min<=max

[•reking]

Multam!
 

[•Eladiv]

#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?

[•stefy9815]

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;
}

[•stefy9815]

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??

[•BaTDucK]

Eu am rezolvat astfel problema..... cu toate ca rezultatele imi dau primesc decat 25 de puncte

Cod:

#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.

[•NarTooN]

Am trimis problema gresita !