結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0