結果

問題 No.362 門松ナンバー
ユーザー btk
提出日時 2016-05-24 22:32:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 3,000 ms
コード長 1,953 bytes
コンパイル時間 1,875 ms
コンパイル使用メモリ 183,676 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 05:08:41
合計ジャッジ時間 2,837 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

/*
* Problem link
* 
*/
#include<bits/stdc++.h>
using namespace std;
struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;
typedef long long LL;
#define rep(i,n) for(auto i= 0*(n);i<n;i++)
#define range(it,v) for(auto &it:v)
#define mp make_pair
bool checkKadomatsu(int a, int b, int c) {
    return (a != c && ((a > b && (b < c) || (a<b&&b>c))));
}
int main() {
#ifdef INPUT_FROM_FILE
    ifstream cin("sample.in");
    ofstream cout("sample.out");
#endif
    int T;
    while (cin >> T) {
        while (T--) {
            LL K;
            cin >> K;
            vector<map<pair<int,int>,LL>> dp(1);
            rep(i, 10)rep(j,10)if(i!=j) dp[0][mp(i, j)] = 1;
            LL lb = 1;
            LL ub = 1;
            auto cnt = [&]() {
                rep(i, 9) {
                    range(it, dp.back()) {
                        if (checkKadomatsu(i + 1, it.first.first, it.first.second))
                            ub+=it.second;
                    }
                }
            };
            cnt();
            while (!(lb <= K&&K<ub)) {
                lb = ub;
                map<pair<int, int>, LL> nxt;
                rep(i, 10) {
                    range(it, dp.back()) {
                        if (checkKadomatsu(i, it.first.first, it.first.second)) 
                            nxt[mp(i, it.first.first)] += it.second;
                        
                    }
                }
                dp.push_back(nxt);
                cnt();
            }
            vector<int> res;
            [&]() {
                rep(i, 9) {
                    range(it, dp.back()) {
                        if (checkKadomatsu(i + 1, it.first.first, it.first.second)) {
                            if (lb + it.second > K) {
                                res.push_back(i + 1);
                                res.push_back(it.first.first);
                                res.push_back(it.first.second);
                                return;
                            }
                            lb += it.second;
                        }
                    }
                }
            }();
            dp.pop_back();
            while (dp.size() > 0) {
                range(it, dp.back()) {
                    int p = res[res.size() - 1];
                    int pp = res[res.size() - 2];
                    if(p==it.first.first)
                        if (checkKadomatsu(pp, it.first.first, it.first.second)) {
                            if (lb + it.second > K) {
                                res.push_back(it.first.second);
                                break;
                            }
                            lb += it.second;
                        }
                }
                dp.pop_back();
            }
            for (auto& i : res)cout << i;
            cout << endl;
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0