結果

問題 No.260 世界のなんとか3
ユーザー ukakukak
提出日時 2017-01-05 08:02:26
言語 Java21
(openjdk 21)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,116 bytes
コンパイル時間 2,376 ms
コンパイル使用メモリ 77,964 KB
実行使用メモリ 67,676 KB
最終ジャッジ日時 2024-12-20 09:44:29
合計ジャッジ時間 13,734 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 127 ms
54,280 KB
testcase_01 AC 130 ms
54,228 KB
testcase_02 AC 128 ms
53,832 KB
testcase_03 MLE -
testcase_04 MLE -
testcase_05 AC 275 ms
57,788 KB
testcase_06 AC 234 ms
56,972 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 AC 279 ms
60,008 KB
testcase_10 MLE -
testcase_11 MLE -
testcase_12 AC 347 ms
62,412 KB
testcase_13 AC 231 ms
57,132 KB
testcase_14 AC 414 ms
63,880 KB
testcase_15 AC 246 ms
58,340 KB
testcase_16 AC 369 ms
63,944 KB
testcase_17 MLE -
testcase_18 MLE -
testcase_19 AC 329 ms
62,480 KB
testcase_20 AC 346 ms
59,268 KB
testcase_21 AC 334 ms
60,948 KB
testcase_22 AC 415 ms
63,528 KB
testcase_23 AC 194 ms
54,732 KB
testcase_24 AC 395 ms
63,620 KB
testcase_25 AC 335 ms
63,384 KB
testcase_26 MLE -
testcase_27 AC 131 ms
53,880 KB
testcase_28 MLE -
testcase_29 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class Main {

    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            String A = in.next();
            String B = in.next();
            int sekaiA = sekai(A.toCharArray(), true);
            int sekaiB = sekai(B.toCharArray(), false);
            int ans = sekaiA > sekaiB ? (sekaiB + MOD - sekaiA) : sekaiB - sekaiA;
            System.out.println(ans);
        }
    }

    private static int sekai(char[] N, boolean ignoreAllTight) {
        final int n = N.length;
        // position, tight, mod3, has3, mod8
        final int[][][][][] dp = new int[n + 1][2][3][2][8];

        dp[0][1][0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 2; l++) {
                        for (int m = 0; m < 8; m++) {
                            int lim = j == 1 ? N[i] - '0' : 9;
                            for (int d = 0; d < lim + 1; d++) {
                                int nj = j == 1 && d == lim ? 1 : 0;
                                int nk = (10 * k + d) % 3;
                                int nl = l == 1 || d == 3 ? 1 : 0;
                                int nm = (10 * m + d) % 8;
                                dp[i + 1][nj][nk][nl][nm] += dp[i][j][k][l][m];
                                dp[i + 1][nj][nk][nl][nm] %= MOD;
                            }
                        }
                    }
                }
            }
        }

        int sum = 0;
        for (int j = 0; j < (ignoreAllTight ? 1 : 2); j++) {
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 2; l++) {
                    for (int m = 0; m < 8; m++) {
                        if ((k == 0 || l == 1) && m != 0) {
                            sum += dp[n][j][k][l][m];
                            sum %= MOD;
                        }
                    }
                }
            }
        }
        return sum;
    }
}
0