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

• 問題: No.362 門松ナンバー
• ユーザー: koyumeishi
• 提出日時: 2016-03-16 02:08:31
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 70 ms / 3,000 ms
• コード長: 1,720 bytes
• コンパイル時間: 1,221 ms
• コンパイル使用メモリ: 76,276 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-10-01 20:11:04
• 合計ジャッジ時間: 2,586 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
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
#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
//resize(vector, v1,v2,...,vn); v[v1][v2]...[vn]
template<typename V, typename H> void resize(vector<V>& vec, const H head){vec.resize(head);}
template<typename V, typename H, typename ... T> void resize(vector<V>& vec, const H& head, const T ... tail){
    vec.resize(head);
    for(auto& v: vec) resize(v, tail...);
}
string ltos(long long x){
    stringstream ss;
    ss << x;
    return ss.str();
}
long long cnt_kadomatsu_digit(string s){
    vector<vector<vector<long long>>> dp;
    resize(dp, 11,11, 2);
    dp[10][10][0] = 1;
    for(int i=0; i<s.size(); i++){
        vector<vector<vector<long long>>> dp_;
        resize(dp_, 11,11, 2);
        int k = s[i] - '0';
        for(int a=0; a<=10; a++)
        for(int b=0; b<=10; b++)
        for(int s=0; s< 2 ; s++){
            if(!dp[a][b][s]) continue;
            for(int c=0; c<10; c++){
                if(s==0 && c>k) break;
                int next_s = s || c<k;
                bool ok = (a<b && b>c && a!=c) || (a>b && b<c && a!=c) || (a==10 || b==10);
                if(ok){
                    dp_[b][(b==10&&c==0) ? 10 : c][next_s] += dp[a][b][s];
                }
            }
        }
        swap(dp, dp_);
    }
    long long ret = 0;
    for(int a=0; a<10; a++)
    for(int b=0; b<10; b++)
    for(int s=0; s<2 ; s++){
        ret += dp[a][b][s];
    }
    return ret;
}
int main_(){
    long long n = 0;
    cin >> n;
    n += cnt_kadomatsu_digit("99");
    long long lb = 1;
    long long ub = 500000000000000LL;
    while(ub-lb>1){
        long long mid = (lb+ub)/2;
        bool ok = cnt_kadomatsu_digit(ltos(mid)) >= n;
        (ok? ub : lb) = mid;
    }
    cout << ub << endl;
    return 0;
}
#include <ctime>
int main(){
    //auto s = clock();
    int t;
    cin >> t;
    while(t--){
        main_();
    }
    //cerr << clock()-s << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX