Cod sursa(job #2759851)

Utilizator Andrei_23Andrei Iatagan Andrei_23 Data 20 iunie 2021 22:26:44
Problema Factorial Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>

using namespace std;

///se cauta binar numarul N, in spatiul de solutii.
///pe N nu il generam, dar aflam puterea lui 5 din descompunerea lui, a.i. sa nu depasim limita memoriei.
///pentru fiecare N cautat : pcinci = puterea lui 5, din N!.
///daca pcinci == P, am terminat. pcinci < P, mergem pe stanga / analog dreapta. daca s > d, afisam -1.

///OPTIMIZARE :
/*
long long d = 33554432 : ~1.4sec;
cb :

    if(s > d) return -1;
    if(pcinci((s + d) / 2) == p) return ((s + d) / 2);
    if(pcinci((s + d) / 2) < p) return cb(p, ((s + d) / 2) + 1, d);
    if(pcinci((s + d) / 2) > p) return cb(p, s, ((s + d) / 2) - 1);

long long d = 33554432 : ~0.5sec;
cb :
    if(s > d) return -1;
    int pc = pcinci((s + d) / 2);
    if(pc == p) return ((s + d) / 2);
    if(pc < p) return cb(p, ((s + d) / 2) + 1, d);
    if(pc > p) return cb(p, s, ((s + d) / 2) - 1);

long long d = 33554432 : ~0.5sec;
cb :
    if(s > d) return -1;
    int pc = pcinci((s + d) >> 1);
    if(pc == p) return ((s + d) >> 1);
    if(pc < p) return cb(p, ((s + d) >> 1) + 1, d);
    if(pc > p) return cb(p, s, ((s + d) >> 1) - 1);
pc :
    long long pcinci = 0;
    for(int i = 1; i <= n; i++)
    {
        long long cop = i;
        while(cop % 5 == 0)
        {
            pcinci++;
            cop /= 5;
        }
    }

long long d = 33554432 : ~0.25sec;
cb identic,
pc :     for(int i = 5; i <= n; i+=5)


*/

ifstream cin("fact.in");
ofstream cout("fact.out");

long long pcinci(long long n);
long long cb(long long p, long long s, long long d);
long long celmaimic(long long n);

int main()
{
    long long p; cin >> p;
    if(p == 0)
    {
        cout << 1;
        return 0;
    }
    long long s = 1;
    long long d = 16777216; /// nu e calculat, doar vreau sa vad punctaj
    cout << celmaimic(cb(p, s, d));
    return 0;
}

long long celmaimic(long long n)
{
    while(n % 5 != 0)n--;
    return n;
}

long long cb(long long p, long long s, long long d)
{
    if(s > d) return -1;
    int pc = pcinci((s + d) >> 1);
    if(pc == p) return ((s + d) >> 1);
    if(pc < p) return cb(p, ((s + d) >> 1) + 1, d);
    if(pc > p) return cb(p, s, ((s + d) >> 1) - 1);
}

/*
long long cb(long long p, long long s, long long d)
{
    long long rez = -1;
    while(s <= d)
    {
        long long pc = pcinci((s + d) / 2);
        if(pc == p) return ((s + d) / 2);
        if(pc < p) s = ((s + d) / 2) + 1;
        if(pc > p) d = ((s + d) / 2) - 1;
    }
    return rez;
}
*/
long long pcinci(long long n)
{
    long long pcinci = 0;
    for(int i = 5; i <= n; i+=5)
    {
        long long cop = i;
        while(cop % 5 == 0)
        {
            pcinci++;
            cop /= 5;
        }
    }
    return pcinci;
}