Cod sursa(job #595718)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 13 iunie 2011 18:48:53
Problema Factorial Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
/***************************************************
 * Author: Alexandru Palcuie
 * Country: Romania
 * Email: alex [dot] palcuie [at] gmail [dot] com
 * Website: http://palcu.blogspot.com/
 * Year: 2011
****************************************************/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

typedef vector<int> VI;
typedef vector<pair<int,int> > VPI;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;

//Constants
const int rightMax = 100;//500000000;

//Global Vars

//Structs

//Solve Functions
int countZeros(int x){
        int sol = 0;
        while (!(x%5)){
                ++sol;
                x/=5;
        }
        return sol;
}

int countFactorialZeroes(int x){
        int sol = 0, divider = 1;
        int toSum;
        while(toSum = x / (divider *= 5)){
                sol += toSum;
        }
        return sol;
}

inline void get_zeros(){
        unsigned long long i;
        int s=0;
        for (i=1; i<=125; ++i){
                s = countFactorialZeroes(i);
                cout<<i<<" "<<s<<endl;
        }
}

int main()
{
        #ifndef ONLINE_JUDGE
        freopen("fact.in","r",stdin);
        freopen("fact.out","w",stdout);
        #endif

        int nZeros;
        scanf("%d",&nZeros);

        if (nZeros == 0){
                printf("1\n");
                exit(0);
        }

        int left = 0, right = rightMax, mid;
        int currentZeros;

        while(left < right){
                mid = left + (right-left) / 2;
                currentZeros = countFactorialZeroes(mid);
                if (nZeros == currentZeros){
                        while (mid%5) --mid;
                        printf("%d\n",mid);
                        exit(0);
                }
                else{
                        if (nZeros < currentZeros){
                                right = mid - 1;
                        }
                        else{
                                left = mid + 1;
                        }
                }
        }

        printf("-1\n");

        get_zeros();
        return 0;
}