Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1936
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1936
Factorial
By Vinícius Fernandes dos Santos 
Brazil
Timelimit: 1
The factor of a positive integer N, denoted by N!, is defined as the product of the positive integers smaller than or equal to N. For example 4! = 4 × 3 × 2 × 1 = 24.
Given a positive integer N, you should write a program to determine the smallest number k such that N = a1! + A2! + ... + Ak!, where each ai, for 1 ≤ i ≤ k is a positive integer.
For example, for N = 10 the answer is 3, it is possible to write N as the sum of three numbers factor: 10 = 3! + 2! + 2!. For N = 25 the answer is 2, it is possible to write N as the sum of two factorial numbers: 25 = 4! + 1!.
Input
The input consists of a single line containing an integer N (1 ≤ N ≤ 105).
Output
Its program should produce a single line with an integer representing the smallest amount of factor numbers whose sum is equal to the value of N.
| Input Samples | Output Samples |
|
10 |
3 |
|
25 |
2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int fat(int n) {
if (n < = 1) return 1;
else return n * fat(n-1);
}
int main(void) {
int n, i, c, t, f;
scanf("%d", &n);
c = 0;
for (i = 8; i >= 0; --i) {
f = fat(i);
t = (int)(n / f);
n -= t * f;
c += t;
}
printf("%d\n", c);
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
using namespace std;
int fat(int n) {
if (n < = 1) return 1;
else return n * fat(n-1);
}
int main(void) {
int n, i, c, t, f;
cin >> n;
c = 0;
for (i = 8; i >= 0; --i) {
f = fat(i);
t = int(n / f);
n -= t * f;
c += t;
}
cout << c << endl;
return 0;
}
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
static Reader in = new Reader(System.in);
static Writer out = new Writer(System.out);
static final int[] F = {40320, 5040, 720, 120, 24, 6, 2, 1};
public static void main(String[] args) throws IOException {
int N = in.nextInt();
int pos = 0;
int sol = 0;
int div;
while (N != 0) {
if (N >= F[pos]) {
div = N / F[pos];
sol += div;
N -= div * F[pos];
}
pos++;
}
out.println(sol);
in.close();
out.flush();
out.close();
}
////// INPUT / OUTPUT ///////
static class Reader implements Closeable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public Reader(InputStream input) {
reader = new BufferedReader(
new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
private StringTokenizer getTokenizer() throws IOException {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer;
}
public boolean hasNext() throws IOException {
return getTokenizer() != null;
}
public String next() throws IOException {
return hasNext() ? tokenizer.nextToken() : null;
}
public String nextLine() throws IOException {
tokenizer = null;
return reader.readLine();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public String[] nextStringArray(int size) throws IOException {
String[] array = new String[size];
for (int i = 0; i < size; i++) {
array[i] = next();
}
return array;
}
public int[] nextIntArray(int size) throws IOException {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = nextInt();
}
return array;
}
public long[] nextLongArray(int size) throws IOException {
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = nextLong();
}
return array;
}
public double[] nextDoubleArray(int size) throws IOException {
double[] array = new double[size];
for (int i = 0; i < size; i++) {
array[i] = nextDouble();
}
return array;
}
@Override
public void close() throws IOException {
tokenizer = null;
reader.close();
}
}
static class Writer implements Closeable, Flushable {
private final PrintWriter writer;
public Writer(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
@Override
public void close() {
writer.close();
}
@Override
public void flush() {
writer.flush();
}
}
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
def fat(n):
if n <= 1: return 1
else: return n * fat(n-1)
f = [fat(x) for x in range(8, 0, -1)]
n = int(input())
c = 0
for i in range(8):
t = n // f[i]
n -= t * f[i]
c += t
print(c)
Input
Output