Cod sursa(job #1595523)

Utilizator ArceyGeorge Cioroiu Arcey Data 10 februarie 2016 12:55:08
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <cstdio>
#include <iostream>
#include <set>
#include <climits>
#include <map>
#include <algorithm>
#include <list>
#include <vector>
#include <utility>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <string>

using namespace std;

//  BINARY SEARCH
//
//  PARAMETERS:
//      left, right:       MEANING THE NATURAL INTERVAL [left, right]
//      target:             THE VALUE WE'RE SEARCHING FOR
//      Function:        THE FUCTION WE USE
//      equality:          IF WE NEED TO FIND THE EXACT VALUE
//
//  RETURN:
//      MINIMUM / MAXIMUM x FOR WHICH f(x) >= OR <= target
//      NOTE THAT IF equality IS TRUE THE CONDITION BECOME f(x) = target
//
//  USE Predicate FOR LOWER / GREATER
//
//  USE Function TO WRITE THE FUNCTION YOUR PROBLEM NEEDS
//
int binaryFunction(int number) {
    int ans = 0;

    while (number > 0) {
        number /= 5;
        ans += number;
    }

    return ans;
}

bool binaryPredicate(int value, int target) {
    return (binaryFunction(value) >= target);
}

int binarySearch(int left, int right, int target, bool equality) {
    while (left < right) {
        int mid = (left + right) / 2;

        if (binaryPredicate(mid, target))
            right = mid;
        else
            left = mid + 1;
    }

    if (equality && binaryFunction(left) != target)
        return -1;

    return left;
}


//  SIEVE FOR PRIME NUMBERS
//
//  PARAMETERS:
//      primality:       A BOOLEAN VECTOR WHERE primality[i] = TRUE IF i IS A PRIME
//      maxValue:      THE MAX VALUE SIEVE WILL GO TO. NOTE THAT i < maxValue
//
//  RETURN:
//      COMPLETED VECTOR primality WITH THE FUNCTIONALITY DESCRIPTED ABOVE
//
//  IF TAKES TOO LONG, USE IT IN MAIN
//
void sieve(bool primality[], int maxValue) {
    for (int i = 2; i < maxValue; i++) {
        primality[i] = true;
    }
    for (int i = 2; i * i < maxValue; i++) {
        if (primality[i]) {
            for (int j = i * i; j < maxValue; j += i) {
                primality[j] = false;
            }
        }
    }
}


//  GCD AND LCM
//
//  PARAMETERS:
//      a, b:   THE NUMBERS WE WANT TO FIND  THEIR GCD / LCM
//
// RESULT:
//      THE GCD / LCM OF THE NUMBERS
//
// IF WRONG ANSWER, CHANGE TO LONG / LONG LONG
//
int gcd(int a, int b) {
    if (a == 0)
        return b;

    return gcd(b % a, a);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}


//  MODULAR EXPONENTIATION
//
//  PARAMETERS:
//      base:       THE BASE FOR EXPONENTIATION
//      exp:         THE EXPONENT FOR EXPONENTIATION
//      mod;        THE MODOLUS
//
//  RETURN:
//      THE RESULT OF (base ^ mod) % mod
//
//  IF WRONG ANSWER, CHANGE TO LONG / LONG LONG
//
int modExp(int base, int exp, int mod) {
    if (mod == 1)
        return 0;

    int ans = 1;
    base %= mod;

    while (exp > 0) {
        if (exp % 2 == 1)
            ans = (ans * base) % mod;

        exp >>= 1;
        base = (base * base) % mod;
    }

    return ans;
}

int main() {
   // freopen("tt.txt", "r", stdin);
    freopen("fact.in", "r", stdin);
    freopen("fact.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);

    int p;
    cin >> p;
    int ans = binarySearch(1, 5 * p, p, true);
    cout << ans;

    return 0;
}