Cod sursa(job #3240445)

Utilizator andreitricaAndrei Trica andreitrica Data 15 august 2024 15:41:34
Problema Factorial Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("fact1.in");
ofstream fout("fact1.out");

struct int5{
    int val;
    int pre;
};

bool comp (int5 a, int5 b){
    return a.val<b.val;
}

const int NMAX=100000000;
vector<int5>m5;

int findm5 (int q){
    int s=0, j;
    int5 aux;
    for(int i=25, j=1; i<NMAX; i*=5, ++j){
        s+=(j);
        aux.pre=s;
        aux.val=i;
        m5.push_back(aux);
    }

    int5 tof;
    tof.val=q;
    auto findval = equal_range(m5.begin(), m5.end(), tof, comp);

    /*for (auto i : m5)
        cout<<i.pre<<" "<<i.val<<"\n";*/

    int index;

    if ( m5[findval.first-m5.begin()].val != tof.val)
        index=findval.first-m5.begin()-1;
    else
        index=findval.first-m5.begin();

    if (index<0 && m5[index].val>q)
        return -1;

    //cout<<index<<" "<<m5[index].pre*5;

    return m5[index].pre*5;
}

int main()
{
    int n;
    fin>>n;

    if (n==0){
        fout<<1<<"\n";
        return 0;
    }

    int aux=findm5(n*5);
    if (aux==-1){
        fout<<(n*5)<<"\n";
        return 0;
    }
    fout<<(n*5)-aux<<"\n";
    return 0;
}