Submission #42236364

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import std;
void main () {
    int N = readln.chomp.to!int;
    solve(N).writeln;
    //solve2(N);
    //solve3(N);
}
unittest {
    assert(solve(127) == solve2(127) && solve(127) == solve3(127));
    assert(solve(3) == solve2(3) && solve(3) == solve3(3));
    assert(solve(44852) == solve2(44852) && solve(44852) == solve3(44852));
}
int solve (int N) {
    // 解法1: ループによる動的計画法 (Nlog(N))
    // dp[i] := i円を引き出す最小回数
    int[] dp = new int[](N+1);
    dp[] = int.max;
    dp[0] = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import std;

void main () {
    int N = readln.chomp.to!int;
    solve(N).writeln;
    //solve2(N);
    //solve3(N);
}

unittest {
    assert(solve(127) == solve2(127) && solve(127) == solve3(127));
    assert(solve(3) == solve2(3) && solve(3) == solve3(3));
    assert(solve(44852) == solve2(44852) && solve(44852) == solve3(44852));
}

int solve (int N) {
    // 解法1: ループによる動的計画法 (Nlog(N))
    // dp[i] := i円を引き出す最小回数
    int[] dp = new int[](N+1);
    dp[] = int.max;
    dp[0] = 0;

    // インデックスの遷移テーブル作成
    int[] table;
    {
        table ~= 1;
        int six = 6;
        while (six <= N) {
            table ~= six;
            six *= 6;
        }
        int nine = 9;
        while (nine <= N) {
            table ~= nine;
            nine *= 9;
        }
    }

    // 動的計画法
    for (int i = 0; i < N+1; i++) {
        foreach (ref diff; table) {
            if (i - diff < 0) {
                continue;
            }
            dp[i] = min(dp[i], dp[i-diff]+1);
        }
    }

    return dp[N];
}

int solve2 (int N) {
    // 解法2: 状態のDAGのトポロジカル順序を気にしないメモ化再帰
    int[] dp = new int[](N+1);
    dp[] = int.max;
    dp[0] = 0;

    // インデックスの遷移テーブル作成
    int[] table;
    {
        table ~= 1;
        int six = 6;
        while (six <= N) {
            table ~= six;
            six *= 6;
        }
        int nine = 9;
        while (nine <= N) {
            table ~= nine;
            nine *= 9;
        }
    }

    // 再帰関数(遷移は解法1と同じ)
    int rec (int[] dp, int x) {
        if (dp[x] != int.max) {
            return dp[x];
        }

        foreach (diff; table) {
            if (0 <= x - diff) {
                dp[x] = min(dp[x], rec(dp, x-diff)+1);
            }
        }
        return dp[x];
    }

    return rec(dp, N);
}

int solve3 (int N) {
    // 解法3: 全探索
    // 任意の引き出し方は「6の冪を使った総和」と「9の冪を使った総和」に分けることができる。
    // つまり、Nを2つに分ける方法を全探索して、分けた2つを6進数/9進数で表し、ビットの総和を取れば良い

    int ans = int.max;
    foreach (_x; 1..N+1) {
        int x = _x;
        int y = N-_x;
        // x := 6進数で表現 / y := 9進数で表現

        // 候補値
        int res = 0;

        int six = 1;
        while (6*six <= x) {
            six *= 6;
        }
        while (x != 0) {
            res += x/six;
            x -= six*(x/six);
            six /= 6;
        }

        int nine = 1;
        while (9*nine <= y) {
            nine *= 9;
        }
        while (y != 0) {
            res += y/nine;
            y -= nine*(y/nine);
            nine /= 9;
        }

        ans = min(ans, res);
    }

    return ans;
}

Submission Info

Judge Result