UniLecs.137

unilecs137.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;
using std::cout;

// operator< для сравнения двух строк как чисел
bool strless(const string &a, const string &b) {
    return a.size() < b.size() || (a.size() == b.size() && a < b);
}

string solve(int num) {
    if (num == 1) {
        return "1";
    }

    // количество факторов в числе
    uint p[8] = {0};

    // факторизация
    for (const auto &x : {2, 3, 5, 7}) {
        while (num > 0 && num % x == 0) {
            ++p[x];
            num /= x;
        }
    }

    // факторизация содержит факторы отличные от 2, 3, 5, 7
    if (num != 1) {
        return "-1";
    }

    // факторы 5 и 7 можно получить только с помощью соответствующих цифр
    // факторы 2 и 3 можно получить 6 путями:
    const char factor[] = {'2', '3', '4', '6', '8', '9'};
    const uint two[]    = { 1,   0,   2,   1,   3,   0};
    const uint three[]  = { 0,   1,   0,   1,   0,   2};

    // для нахождения оптимальной факторизации для 2 и 3, будем использовать динамику
    // где dp[i][j] это наименьшее число, перемножение цифр которого дает 2^i * 3^j
    vector<vector<string>> dp(p[2] + 1, vector<string> (p[3] + 1));

    for (uint i = 0;i <= p[2]; ++i) {
        for (uint j = 0; j <= p[3]; ++j) {
            // тривиальное решение - i двоек и j троек
            dp[i][j] = string(i, '2') + string(j, '3');
            // перебираем последнию цифру в факторизации
            for (uint k = 0; k < 6; ++k) {
                // если цифра подходит для факторизации
                if (i >= two[k] && j >= three[k]) {
                    // если перебираемая факторизация меньше текущей, то обновляем динамику
                    string x = dp[i - two[k]][j - three[k]] + factor[k];
                    if (strless(x, dp[i][j])) {
                        dp[i][j] = x;
                    }
                }
            }
        }
    }

    // ответ: факторизация двоек и троек + факторизация пятерок + факторизация семерок
    string ans = dp[p[2]][p[3]] + string(p[5], '5') + string(p[7], '7');

    // сортируем
    sort(begin(ans), end(ans));

    return ans;
}

int main() {
    uint T = 19;

    int  tests[] = { 1,   2,   3,   4,   5,   6,   7,   8,   9,   10,   11,   12,
                     13,   14,   15,   20,   512,    3000,   1073741824};
    string res[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "25", "-1", "26",
                    "-1", "27", "35", "45", "888", "35558", "8888888888"};

    for (uint i = 0; i < T; ++i) {
        string ans = solve(tests[i]);
        cout << (ans == res[i] ? "OK---" : "FAIL-");
        cout << i << ": expected " << res[i] << ", found " <<  ans << "\n";
    }

    return 0;
}