NO IMAGE

題目:

Consider all the sequences with length (0 <  N < 44), containing only the elements 0 and 1, and no two ones are adjacent (110 is not a valid sequence of length 3, 0101 is a valid sequence of length 4). Write a program which finds the sequence, which is on K-th place (0 <  K < 10 9) in the lexicographically sorted in ascending order collection of the described sequences.

Input

The first line of input contains two positive integers N and K.

Output

Write the found sequence or −1 if the number K is larger then the number of valid sequences.

Sample Input

3    1

Sample Output

000

題目大意:

    給出01字串的長度,字串要滿足不能有相鄰兩個1,給出序號k,求出按字典序排列的第k個滿足要求的字串。

解題思路:

    先求出每個長度下滿足條件的字串的個數,用動態規劃,設f[i][1]和f[i][0]是長度為i且以1和0開頭的滿足條件的字串的數量,如果第一位是1,則第二位一定是0,如果第一位是0,則第二位可以是0和1,所以有轉換方程:f[i][1]=f[i-1][0],f[i][0]=f[i-1][1] f[i-1][0]。初始狀態f[1][1]=1,f[1][0]=0。

    知道了各種長度字串的數量如何求出第k個字串呢?我們需要求的長度為n的字串按字典序排列的話一定是首位為“0”的排在前面,後面是首位為“1“的字串,所以如果k小於等於首位為“0”的字串的數量(f[n][0]),則可以知道目標字串的首位一定是“0”,在這種情況下,我們知道當首位都是相同的“0”時,剩下的n-1位字串按字典序仍然是首位(即長度為n的字串的第二位)為“0”的排在前面,所以繼續用這種方式判斷首位是否是“0”;那如果判斷的結果是k大於首位為“0”的字串的數量怎麼辦呢?這時候該位的字串是“1”,與上面的情況不同的時,這時候要將k的值減去f[n][0],這是因為進行n-1長度的字串比較時,在首位都為“1”的情況下,這些字串在整體所有字串的位置已經位於所有首位為“1”的字串後面。

程式碼:

#include <iostream>

using namespace std;

int main(){
    int n;
    long long int k;
    int f[46][2];
    f[1][0]=1;
    f[1][1]=1;
    for(int i=2;i<44;i ){
        f[i][1]=f[i-1][0];
        f[i][0]=f[i-1][1] f[i-1][0];
    }
    while(cin>>n>>k){
        if(k>f[n][1] f[n][0]){
            cout<<-1<<endl;
            continue;
        }
        while(n){
            if(f[n][0]>=k)cout<<‘0’;
            else{
                k=k-f[n][0];
                cout<<‘1’;
            }
            n–;
        }
        cout<<endl;
    }
    return 0;
}