Submission #2472743

---

Source Code Expand

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

void main() {
    auto N = readln.chomp.to!long;
    assert(N <= 10^^5);

    long[] nico = [1];
    for (long a = 2; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a;
    for (long a = 5; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a;
    auto M = nico.length.to!int;

    auto dp = new long[long][](N+1);

    auto q = new BinaryHeap!(Array!(Tuple!(long, long, long)), "a[2] > b[2]");
    q.insert(tuple(0L, 1L, 0L));

    while (!q.empty) {
        auto n = q.front[0];
        auto m = q.front[1];
        auto d = q.front[2];
        q.removeFront;
        if (m in dp[n] && dp[n][m] <= d) continue;
        dp[n][m] = d;

        if (n+m <= N) q.insert(tuple(n+m, m, d+1));

        foreach (x; nico) {
            auto mm = m * x;
            if (mm > N) continue;
            q.insert(tuple(n, mm, d));
        }
    }

    dp[N].values.reduce!min.writeln;
}

Submission Info

Judge Result