結果

問題 No.319 happy b1rthday 2 me
ユーザー takeya_okinotakeya_okino
提出日時 2019-06-21 18:59:39
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,668 bytes
コンパイル時間 2,875 ms
コンパイル使用メモリ 78,508 KB
実行使用メモリ 54,580 KB
最終ジャッジ日時 2024-06-07 16:08:34
合計ジャッジ時間 7,513 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 116 ms
54,044 KB
testcase_01 AC 115 ms
53,880 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 111 ms
54,116 KB
testcase_05 AC 119 ms
53,920 KB
testcase_06 AC 117 ms
53,724 KB
testcase_07 AC 117 ms
53,952 KB
testcase_08 AC 113 ms
54,108 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 103 ms
52,904 KB
testcase_13 AC 118 ms
54,004 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 117 ms
54,008 KB
testcase_19 AC 114 ms
53,996 KB
testcase_20 WA -
testcase_21 AC 122 ms
54,028 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 120 ms
54,496 KB
testcase_25 AC 118 ms
54,096 KB
testcase_26 WA -
testcase_27 AC 106 ms
53,020 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 119 ms
54,232 KB
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String A = sc.next();
    String B = sc.next();
    long ans = 0;
    if(A.equals("1")) {
      if(!(B.equals("1"))) {
        ans = func(B) + 1 + f(B);
      }
    } else {
      long t1 = 0;
      for(int i = 0; i < A.length() - 1; i++) {
        if((A.charAt(i) == '1') && (A.charAt(i) == '2')) t1++;
      }
      long t2 = 0;
      if((A.length() > 1) && (A.charAt(0) == '2') && (A.charAt(A.length() - 1) == '1')) t2 = 1;
      ans = func(B) - func(A) + t1 + f(B) - f(A) + t2;
    }
    System.out.println(ans);
  }

  public static long f(String X) {
    int len = X.length();
    long ret = 0;
    if(len > 1) {
      for(int i = 0; i < len - 1; i++) {
        int s = len - 2 - i;
        if(i == 0) {
          if(X.charAt(0) == '1') {
            
          } else if(X.charAt(0) == '2') {
            long t = 0;
            if((X.charAt(len - 1) == '0') || (X.charAt(len - 1) == '1') || (X.charAt(len - 1) == '2')) {
              if(len > 2) {
                String sub = X.substring(1, len - 1);
                long subt = Long.parseLong(sub);
                if(!(X.charAt(len - 1) == '2')) {
                  ret += (subt);
                } else {
                  ret += (subt + 1);
                }
              }
            } else {
              ret += ((long)Math.pow(10, s));
            }
          } else {
            ret += ((long)Math.pow(10, s));
          }
        } else {
          ret += ((long)Math.pow(10, s));
        }
      }
    }
    return ret;
  }

  public static long func(String X) {
    int len = X.length();
    long[][][][] dp = new long[len][10][10][2];
    int first = Integer.parseInt(String.valueOf(X.charAt(0)));
    if(len == 1) {
      for(int j = 0; j < first; j++) {
        dp[0][j][0][1] = 1;
      }
      dp[0][first][0][0] = 1;
    } else {
      for(int j = 0; j < first; j++) {
        dp[0][j][0][1] = 1;
      }
      dp[0][first][0][0] = 1;
      for(int i = 1; i < len; i++) {
        int d = Integer.parseInt(String.valueOf(X.charAt(i)));
        for(int j = 0; j < 10; j++) {
          for(int k = 0; k < 9; k++) {
            if(j != 1) {
              for(int t = 0; t <= d; t++) {
                if(t == d) {
                  dp[i][t][k][0] += dp[i - 1][j][k][0];
                } else {
                  dp[i][t][k][1] += dp[i - 1][j][k][0];
                }
              }
              for(int t = 0; t < 10; t++) {
                dp[i][t][k][1] += dp[i - 1][j][k][1];
              }
            } else {
              for(int t = 0; t <= d; t++) {
                if(t == d) {
                  if(t == 2) {
                    dp[i][t][k + 1][0] += dp[i - 1][j][k][0];
                  } else {
                    dp[i][t][k][0] += dp[i - 1][j][k][0];
                  }
                } else {
                  if(t == 2) {
                    dp[i][t][k + 1][1] += dp[i - 1][j][k][0];
                  } else {
                    dp[i][t][k][1] += dp[i - 1][j][k][0];
                  }
                }
              }
              for(int t = 0; t < 10; t++) {
                if(t == 2) {
                  dp[i][t][k + 1][1] += dp[i - 1][j][k][1];
                } else {
                  dp[i][t][k][1] += dp[i - 1][j][k][1];
                }
              }
            }
          }
        }
      }
    }
    long ret = 0;
    for(int j = 0; j < 10; j++) {
      for(int k = 1; k < 10; k++) {
        for(int l = 0; l < 2; l++) {
          ret += (k * dp[len - 1][j][k][l]);
        }
      }
    }
    return ret;
  }
}
0