結果

問題 No.319 happy b1rthday 2 me
ユーザー takeya_okinotakeya_okino
提出日時 2019-06-21 18:59:39
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 3,668 bytes
コンパイル時間 3,437 ms
コンパイル使用メモリ 78,004 KB
実行使用メモリ 41,652 KB
最終ジャッジ日時 2024-12-25 22:47:52
合計ジャッジ時間 7,309 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 14 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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