結果

問題 No.220 世界のなんとか2
コンテスト
ユーザー norioc
提出日時 2017-09-18 00:20:23
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1 ms / 1,000 ms
コード長 1,386 bytes
コンパイル時間 813 ms
コンパイル使用メモリ 103,984 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 21:57:51
合計ジャッジ時間 1,571 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

long calc(int p) {
    ulong x = 10uL ^^ p;
    string s = x.to!string;
    int n = cast(int) s.length;

    auto dp = new long[][][][](n + 1, 2, 2, 3);
    // dp[i][j][k][m]
    // i: i 桁目までみた
    // j: x 未満か
    // k: 3 を含めた
    // m: mod 3

    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int m = 0; m < 3; m++) {
                    int lim = j ? 9 : s[i] - '0';
                    for (int d = 0; d <= lim; d++) {
                        dp[i + 1][j || d < lim][k || d == 3][(m + d) % 3] += dp[i][j][k][m];
                    }
                }
            }
        }
    }

    long ans = 0;
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            for (int m = 0; m < 3; m++) {
                if (k == 1 || m == 0) { // 3 を含めた or 3 の倍数
                    ans += dp[n][j][k][m];
                }
            }
        }
    }
    return ans - 1; // -1 は 0 の分
}

void main() {
    int p = readint;
    writeln(calc(p));
}
0