#87591 (C++11（廃止可能性あり）) No.362 門松ナンバー

• 問題: No.362 門松ナンバー
• ユーザー: Hachimori
• 提出日時: 2016-04-18 00:32:36
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 2 ms / 3,000 ms
• コード長: 3,169 bytes
• コンパイル時間: 402 ms
• コンパイル使用メモリ: 57,980 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-04 12:19:55
• 合計ジャッジ時間: 1,020 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_DIGIT = 15;
const int NOT_EXIST = 10;
bool isKadomatsu(int a, int b, int c) {
    return a != b && a != c && b != c && (b > max(a, c) || b < min(a, c));
}
// dp[nTh][prepre][pre]:
// nTh 番目の桁, 二つ前の数字が prepre, 一つ前の数字が pre で,
// これ以降、門松ナンバーが作られるように数字を決めたとき、何通りの門松ナンバーが作られるか
long long dp[MAX_DIGIT][11][11];
long long calcRec(int nTh, int prepre, int pre) {
    if (nTh == -1) {
        return 1;
    }
    
    long long &ret = dp[nTh][prepre][pre];
    
    if (ret != -1) return ret;
    
    ret = 0;
    
    if (nTh >= 3 && pre == NOT_EXIST) {
        ret += calcRec(nTh - 1, NOT_EXIST, NOT_EXIST);
    }
    for (int digit = 0; digit <= 9; ++digit) {
        if (digit == 0) {
            if (pre != NOT_EXIST && (prepre == NOT_EXIST || isKadomatsu(prepre, pre, 0))) {
                ret += calcRec(nTh - 1, pre, digit);
            }
            continue;
        }
        if (prepre == NOT_EXIST || pre == NOT_EXIST || isKadomatsu(prepre, pre, digit)) {
            ret += calcRec(nTh - 1, pre, digit);
        }
    }
    return ret;
}
long long K;
void read() {
    cin >> K;
    --K;
}
void work() {
    long long curK = 0;
    
    int nTh = MAX_DIGIT - 1;
    int prepre = NOT_EXIST;
    int pre = NOT_EXIST;
    
    while (nTh >= 0) {
        
        #define get(a, b, c) (a == -1 ? 1 : dp[a][b][c])
        
        int toPrint = -1;
        
        if (nTh >= 3 && pre == NOT_EXIST) {
            if (curK + get(nTh - 1, NOT_EXIST, NOT_EXIST) <= K) {
                curK += get(nTh - 1, NOT_EXIST, NOT_EXIST);
            }
            else {
                toPrint = NOT_EXIST;
                goto _finish;
            }
        }
        for (int digit = 0; digit <= 9; ++digit) {
            if (digit == 0) {
                if (pre != NOT_EXIST && (prepre == NOT_EXIST || isKadomatsu(prepre, pre, 0))) {
                    if (curK + get(nTh - 1, pre, digit) <= K) {
                        curK += get(nTh - 1, pre, digit);
                    }
                    else {
                        toPrint = 0;
                        goto _finish;
                    }
                }
                continue;
            }
            
            if (prepre == NOT_EXIST || pre == NOT_EXIST || isKadomatsu(prepre, pre, digit)) {
                if (curK + get(nTh - 1, pre, digit) <= K) {
                    curK += get(nTh - 1, pre, digit);
                }
                else {
                    toPrint = digit;
                    goto _finish;
                }
            }
        }
        
    _finish:
        if (toPrint != NOT_EXIST) {
            cout << toPrint;
        }
        
        --nTh;
        prepre = pre;
        pre = toPrint;
    }
    
    cout << endl;
}
int main() {
    memset(dp, -1, sizeof(dp));
    calcRec(MAX_DIGIT - 1, NOT_EXIST, NOT_EXIST);
    
    int cases;
    cin >> cases;
    for (int i = 0; i < cases; ++i) {
        read();
        work();
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX