#94223 (Java) No.362 門松ナンバー

• 問題: No.362 門松ナンバー
• ユーザー: 37zigen
• 提出日時: 2016-05-26 21:57:13
• 言語: Java (openjdk 23)
• 結果: WA
• 実行時間: -
• コード長: 2,060 bytes
• コンパイル時間: 2,470 ms
• コンパイル使用メモリ: 80,120 KB
• 実行使用メモリ: 55,356 KB
• 最終ジャッジ日時: 2024-10-07 16:18:21
• 合計ジャッジ時間: 7,469 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 1 WA * 2
other	WA * 19

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package yukicoder;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        new Main().solve();
    }
    void solve(){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        /*
         *dp[一番左の桁の数][左から一つ右にずれた桁の数][桁数]=門松数の数
         *leading 0を許す。
         */
        long[][][] dp=new long[10][10][101];
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                if(i==j)continue;
                dp[i][j][2]++;
            }
        }
        for(int digit=3;digit<20;digit++){
            for(int i=0;i<10;i++){
                for(int j=0;j<10;j++){
                    for(int k=0;k<10;k++){
                        if(isKadomatsu(i,j,k)){
                            dp[i][j][digit]+=dp[j][k][digit-1];
                        }
                    }
                }
            }
        }
        //sum[i]:i桁以下の数の数
        //leading 0を許さない
        long[] sum=new long[30];
        for(int digit=3;digit<30;digit++){
            for(int i=1;i<10;i++){
                for(int j=0;j<10;j++){
                    sum[digit]+=dp[i][j][digit];
                }
            }
        }
        for(int rep=0;rep<t;rep++){
            long k=sc.nextLong();
            int d=3;
            //k番目の門松数はd桁の数
            for(;;d++){
                if(sum[d]>=k){
                    break;
                }
            }
            String ans="";
            long now=k;
            int pre1=-1;
            int pre2=-1;
            //leading 0を許さない。
            out:for(int i=1;i<10;i++){
                for(int j=0;j<10;j++){
                    now-=dp[i][j][d];
                    //                  System.out.println(now+" "+i+" "+j);
                    if(now<=0){
                        now+=dp[i][j][d];
                        ans+=String.valueOf(i)+String.valueOf(j);
                        pre1=i;
                        pre2=j;
                        d-=2;
                        break out;
                    }
                }
            }
            out2:for(;d>=1;d--){
                if(d==1){
                    for(int i=1;i<10;i++){
                        if(isKadomatsu(pre1,pre2,i)){
                            now--;
                            if(now==0){
                                ans+=String.valueOf(i);
                                break out2;
                            }
                        }
                    }
                }
                for(int i=0;i<9;i++){
                    now-=dp[pre2][i][d];
                    if(now<=0){
                        now+=dp[pre2][i][d];
                        ans+=String.valueOf(i);
                        pre1=pre2;
                        pre2=i;
                    }
                }
            }
            System.out.println(ans);
        }
    }
    boolean isKadomatsu(int x,int y,int z){
        if(x==y||y==z||z==x)return false;
        if(x<y&&y>z)return true;
        if(x>y&&y<z)return true;
        return false;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX