1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <climits>
#include <string>

#define LL unsigned long long
#define MAX_LENGTH 1000010
#define INF ULLONG_MAX

char solution[MAX_LENGTH];

#define DBG(X)

LL total_x(int n) {
  // return 2^n - 1
  if (n <= 62) return ((1LLU << n) - 1);
  else return INF;  
}

char smallestL[3] = {1, 0, 0};
char nextL[3] = {2, 2, 1};

int kth_x(int n, LL k, char first_litera, int idx) {
    solution[idx] = first_litera + 'a';
    while (k) {
        LL med = total_x(n-1);
        if (k <= med) {
            first_litera = smallestL[first_litera];
            k--;
        } else {
            first_litera = nextL[first_litera];
            k = k - med - 1;
        }
        n -= 1;
        idx++;
        solution[idx] = first_litera + 'a';
    }
    solution[idx+1] = 0;
    return 0;
}

int kth(int n, LL k, int idx) {
    DBG(printf("%d %llu = \n", n, k));
    for (int litera=0; litera < 3; litera++) {
        if (k < total_x(n)) {
            // zacznij od litery
            DBG(printf("First letter: %c\n", 'a' + litera));
            return kth_x(n, k, litera, idx);
        }
        k -= total_x(n);
    }
    sprintf(solution, "NIE");
    return 0;
}

void selftest() {
    int n = 100;
    std::string last_string = "";
    LL start_k = 100000000000000000LLU;    
    for (LL k=start_k; k < start_k+100; k++) {
        kth(n, k, 0);
        std::string s = std::string(solution);
        if (s <= last_string) {
            printf("error because %s is lower lexicographically than %s\n", s.c_str(), last_string.c_str());
        }
        printf("%d %llu %s\n", n, k, solution);
        last_string = s;
    }
}

int main() {
    // selftest();
    int n;
    LL k;
    while (scanf("%d%llu", &n, &k) > 1) {   
        kth(n, k-1, 0); 
        printf("%s\n", solution);
    }
    return 0;
}