Cod sursa(job #2013561)

Utilizator skoda888Alexandru Robert skoda888 Data 21 august 2017 18:53:23
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb

//INFO ARENA - PROBLEMA 6(Fractional)

#include <iostream>
#include <fstream>
#include <climits>

long long P;
long long solutie;

long long numDeZerouri(long long numar)
{
    long long cateZerouri = 0;

    while(numar != 0)
    {
        cateZerouri += numar / 5;
        numar /= 5;
    }

    return cateZerouri;
}

long long nrZerouri(long long nr)
{
  long long nrZ = 0;
  while(nr != 0)
  {
    nrZ += nr / 5;
    nr /= 5;
  }
  return nrZ;
}

void cautareBinara(long long & stanga, long long dreapta)
{

    if(stanga <= dreapta){
    long long mijloc = stanga + (dreapta - stanga) / 2;
    long long zerouri_la_mijloc = numDeZerouri(mijloc);


    if(zerouri_la_mijloc == P)
    {
        solutie = mijloc;
        dreapta = mijloc - 1;
    }
    else if (zerouri_la_mijloc > P)
    {
        dreapta = mijloc - 1;
    }
    else if (zerouri_la_mijloc < P)
    {
        stanga = mijloc + 1;
    }
    cautareBinara(stanga, dreapta);
}

}
int main()
{
    //FRACT.IN
    std::fstream in_fract("fract.in", std::ios::in);
    std::fstream out_fract("fract.out", std::ios::out);

    in_fract >> P;

    if(P < 0)
    {
        out_fract << -1;
    }

    //CAUTAREA BIANARA
    long long stanga = 1;
    long long dreapta = LLONG_MAX;

    cautareBinara(stanga, dreapta);

    out_fract << solutie;
    return 0;
}