Cod sursa(job #2923021)

Utilizator miramaria27Stroie Mira miramaria27 Data 11 septembrie 2022 11:04:25
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
using namespace std;

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

// first step: binary search

int computeNoZero(int nr){
  int div = 5, sol = 0;
  // div <= nr and nr < 10^8 => doesn't overflow
  while(div <= nr){
    sol += nr/div;
    div *= 5;
  }
  return sol;
}

void binarySearch(int left, int right, int noZero, int &sol){
    if(left <= right) {
      int mid = left + (right - left)/2;
      if(computeNoZero(mid) < noZero) {
        binarySearch(mid + 1, right, noZero, sol);
      }
      else {
        sol = mid;
        binarySearch(left, mid - 1, noZero, sol);
      }
    }
}

int main() {
  int P;
  fin >> P;
  int sol = -1;
  if(P == 0){
    sol = 1;
  }
  else {
    binarySearch(1, 5*P, P, sol);
  }
  if(computeNoZero(sol) != P){
    sol = -1;
  }
  fout<<sol;
}