Cod sursa(job #1010513)

Utilizator iulia_infoIulia Cosmin iulia_info Data 15 octombrie 2013 01:01:42
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;
 
long int fives(int x) {
  long int count = 0;
  while ((x > 0) && (x % 5 == 0)) {
    count++;
    x /= 5;
  }
  return count;
}

int prev_multiple(int x) {
  while (x % 5 != 0) { x--; }
  return x;
}
 
int main()
{
  ifstream input("fact.in");
  int p;
  input >> p;
  ofstream output("fact.out");

  int left = 1;
  int right = 100000000;
  int found = false;

  while ((left < right) && (!found)) {
    // This is normally prone to overflows, but not in this case.
    int mid = (left + right) / 2;
    long int mid_fives = 0;
    for (int i = 5; i <= mid; i += 5) {
      mid_fives += fives(i);
    }
    if (mid_fives == p) {
      found = true;
      int result = prev_multiple(mid);
      if (result == 0) { result = 1; }
      output << result;
    } else {
      if (mid_fives < p) { left = mid + 1; }
      else { right = mid - 1; }
    }
  }
  
  if (!found) { output << -1; }
}