43092023-03-23 11:09:271478Kígyózó szavakcpp17Elfogadva 100/1008ms4764 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{

    int h, n;
    cin>>h>>n;
    vector<vector<long long>> dp(h+1, vector<long long>(27));
    //vector<int> tas

    for(int i=1; i<=26; i++){
        dp[1][i] = 1;
    }

    for(int i=2; i<=h; i++){
        for(int j = 1; j<=26; j++){
            if(j>1) dp[i][j] += dp[i-1][j-1];
            if(j<26) dp[i][j] += dp[i-1][j+1];
            dp[i][j]=min(dp[i][j],1000000000LL);
        }
    }

    for(int i=2; i<=h; i++){
        for(int j=1; j<=26; j++){
            dp[i][j] += dp[i-1][j];
        }
    }

    for(int i=1; i<=n; i++){
        string sol;
        int k, g = h;
        cin>>k;
        int ind = 1;
        while(k-dp[g][ind] > 0){
            k -= dp[g][ind];
            ++ind;
        }
        sol +='a' + ind - 1;
        //cout<<sol<<" ";
        //cout<<k<<": ";
        bool ok = 0;
        while(1){
            k--;
            g--;
            if(k <= 0) {
                break;
            }
            if(ind > 1 && ind < 26){
                if(k-dp[g][ind-1] > 0) {
                    sol+='a'+ind;
                    //cout<<sol<<" ";

                    k -= dp[g][ind-1];
                    //cout<<k<<endl;
                    ind++;
                }
                else{
                    sol+='a'+ind-2;
                    //cout<<sol<<" "<<k<<endl;
                    ind--;
                }
            }
            else if(ind == 1){
                sol+='b';
                ind++;
            }
            else if(ind == 26){
                sol+='y';
                ind--;
            }
        }
        cout<<sol<<endl;
    }
    return 0;
}