找出第k个不含连续'12'、'23'、'31'的123构成的n位数

一个数中如果如果不含连续的'12',连续的'23',连续的'31', 就称作'123'好数. 那么, 在由123构成的n位数中, 第k个'123'好数是什么?

输入

一行, 两个正整数n,k, 用空格分隔

输出

一行, 输出由123构成的n位数中, 第k个'123'好数.

样例输入

6 14

样例输出

113322

提示

【说明提示】 1≤n≤20 k不超过满足条件的'123'好数个数

#include <iostream>
#include <string>
using namespace std;

// 判断一个数是否为'123'好数
bool is123Number(string num) {
    for (int i = 2; i < num.length(); i++) {
        if (num[i] == '3' && num[i - 1] == '2' && num[i - 2] == '1') {
            return false;
        }
    }
    return true;
}

// 获取由'123'构成的n位数中第k个'123'好数
string getKth123Number(int n, int k) {
    string num = '';
    int count = 0;
    while (count < k) {
        num += '1';
        count++;
        if (count == k) {
            break;
        }
        num += '2';
        count++;
        if (count == k) {
            break;
        }
        num += '3';
        count++;
        if (count == k) {
            break;
        }
    }
    while (num.length() < n) {
        if (num[num.length() - 1] == '1') {
            num += '2';
        } else if (num[num.length() - 1] == '2') {
            num += '3';
        } else if (num[num.length() - 1] == '3') {
            num += '1';
        }
    }
    while (!is123Number(num)) {
        num = getKth123Number(n, k + 1);
    }
    return num;
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << getKth123Number(n, k) << endl;
    return 0;
}