Cerinta completa

Given an integer, , find the smallest integer such that is divisible by (i.e., is a factor of ) and satisfies the following properties:

  • must not contain zeroes in its decimal representation.
  • The sum of ‘s digits must be greater than or equal to the product of ‘s digits.

Given , find and print the number of digits in ‘s decimal representation.

Input Format

A single integer denoting .

Constraints

  • is not divisible by .

Time Limits

  • The time limits for this challenge are available here.

Output Format

Print the number of digits in the decimal representation of the smallest possible .

Sample Input 0

1

Sample Output 0

1

Explanation 0

is evenly divided by , doesn’t contain any zeroes in its decimal representation, and the sum of its digits is not less than the product of its digits. Thus, we print the number of digits in (which also happens to be ) as our answer.

Sample Input 1

9

Sample Output 1

1

Explanation 1

is evenly divided by , doesn’t contain any zeroes in its decimal representation, and the sum of its digits is not less than the product of its digits. Thus, we print the number of digits in , which is , as our answer.

Limbajul de programare folosit: cpp14

Cod:

#include <iostream>
#include <cstdio>
#include <vector>
    
using namespace std;
    
bool add(int value, vector < int >* digits) {
    digits->at(0) += value;
    for (int i = 0; i + 1 < digits->size(); ++i) {
        if (digits->at(i) >= 10) {
            digits->at(i + 1) += digits->at(i) / 10;
            digits->at(i) %= 10;
        } 
        else {
            break;
        }
    }
    return digits->back() < 10;
}
    
int getSum(const vector < int >& digits) {
    int res = 0;
    const int significant_digits = min((int)digits.size(), 30);
    for (int i = 0; i < significant_digits; ++i) {
        res += digits[i];
    }
    res += digits.size() - significant_digits;
    return res;
}
    
int getProduct(const vector < int >& digits) {
    int res = 1;
    const int significant_digits = min((int)digits.size(), 30);
    const int inf = 1000000;
    for (int i = 0; i < significant_digits; ++i) {
        res *= digits[i];
        if (res > inf) {
            res = inf;
            break;
        }
    }
    return res;
}
    
int largest = 0;
    
bool build(int n, int length, vector < int >* digits) {
    int rem = 0;
    for (int i = length - 1; i >= 0; --i) {
        rem = rem * 10 + digits->at(i);
        rem %= n;
    }
    if (!add((n - rem) % n, digits)) {
        return false;
    }
    int iterations = 0;
    const int max_iterations = n;

    while (iterations < max_iterations) {
        ++iterations;
        int sum = getSum(*digits);
        int product = getProduct(*digits);
        if (product == 0 || sum < product) {
            if (!add(n, digits)) {
                return false;
            }
            continue;
        }
        return true;
    }
    
    return false;
}

bool try_to_build(int n, int length) {
    vector < int > digits(length, 1);
    if (build(n, length, &digits)) {
        return true;
    }
    return false;
}

int solve(int n) {
    if (n % 10 == 0) {
        return -1;
    }
    int starting_length = 60;
    
    for (int length = starting_length; ; ++length) {
        if (try_to_build(n, length)) {
            return length;
        }
    }
}

const int maxS = 75;
const int maxN = 30000;
unsigned char d[maxS][maxS][maxN];

int clever(int n) {
    if (n % 10 == 0) {
        return -1;
    }
    const int inf = 250;
    for (int i = 0; i < maxS; ++i) {
        for (int j = 0; j < maxS; ++j) {
            for (int k = 0; k < maxN; ++k) {
                d[i][j][k] = inf;
            }
        }
    }
    d[0][1][0] = 0;
    for (int i = 0; i < maxS; ++i) {
        for (int j = 0; j < maxS; ++j) {
            for (int k = 0; k < n; ++k) {
                if (d[i][j][k] == inf) {
                    continue;
                }
    
                for (int digit = 1; digit < 10; ++digit) {
                    if (i + digit < maxS && j * digit < maxS) {
                        int l = (k * 10 + digit) % n;
                        d[i + digit][j * digit][l] = min(
                            d[i + digit][j * digit][l], 
                            (unsigned char)(d[i][j][k] + 1)
                        );
                    }
                }
            }
        }
    }
    
    int res = 1000000;
    for (int i = 1; i < maxS; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (d[i][j][0] != inf) {
                res = min(res, (int)(d[i][j][0]));
            }
        }
    }
    return res;
}
    
int main() {
    int n;
    scanf("%d", &n);
    int res = clever(n);
    if (res == 1000000) {
        res = solve(n);
    }
    printf("%d\n", res);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647765

Link challenge: https://www.hackerrank.com/challenges/divisible-numbers/problem

Divisible Numbers