結果

問題 No.362 門松ナンバー
ユーザー ぴろず
提出日時 2016-04-18 00:41:28
言語 Java
(openjdk 23)
結果
AC  
実行時間 296 ms / 3,000 ms
コード長 1,920 bytes
コンパイル時間 1,849 ms
コンパイル使用メモリ 77,324 KB
実行使用メモリ 58,888 KB
最終ジャッジ日時 2024-10-04 12:25:55
合計ジャッジ時間 8,245 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package no362a;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
//      System.out.println(countKadomatsuNumber(102));
        int t = sc.nextInt();
        for(int i=0;i<t;i++) {
            System.out.println(solve(sc.nextLong()));
        }
    }
    
    public static long solve(long x) {
        long left = 101;
        long right = 37294859064823L;
        while(left + 1 < right) {
            long c = (left + right) / 2;
            if (countKadomatsuNumber(c) >= x) {
                right = c;
            }else{
                left = c;
            }
        }
        return right;
    }
    
    //x >= 100
    public static long countKadomatsuNumber(long x) {
        String s = String.valueOf(x);
        int n = s.length();
        int[] a = new int[n];
        for(int i=0;i<n;i++) {
            a[i] = s.charAt(i) - '0';
        }
        long[][][][] dp = new long[n+1][4][2][100];
        dp[0][0][1][0] = 1;
        for(int i=0;i<n;i++) {
            for(int digits=0;digits<=3;digits++) {
                for(int big=0;big<2;big++) {
                    for(int j=0;j<100;j++) {
                        if (dp[i][digits][big][j] == 0) {
                            continue;
                        }
//                      System.out.println(dp[i][digits][big][j]);
                        for(int k=0;k<=9;k++) {
                            if (big == 1 && k > a[i] || (digits >= 2 &&!isKadomatsuSequence(j/10, j%10, k))) {
                                continue;
                            }
                            int ndigits = digits == 0 && k == 0 ? 0 : Math.min(digits+1, 3);
                            int nbig = big == 1 && k == a[i] ? 1 : 0;
                            int nj = j % 10 * 10 + k;
//                          System.out.println(i + "," + digits + "," + big + "," + j + " --" + k + "--> " + (i+1) + "," + ndigits + "," + nbig + "," 
    + nj);
                            dp[i+1][ndigits][nbig][nj] += dp[i][digits][big][j];
                        }
                    }
                }
            }
        }
        long sum = 0;
        for(int i=0;i<2;i++) {
            for(int j=0;j<100;j++) {
                sum += dp[n][3][i][j];
            }
        }
//      System.out.println(sum);
        return sum;
    }
    public static boolean isKadomatsuSequence(long a,long b,long c) {
        if (a == b || b == c || a == c) {
            return false;
        }
        return b < a && b < c || b > a && b > c;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0