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
#include <stdio.h>

void solveRest(long long n, long long k, char last) {
/*
1: 1 2 => 2 = 0 + 2
2: 1 12 13 2 21 23 => 6 = 2 + 4
3: 1 12 121 123 13 131 132 2 21 212 213 23 231 232 => 14 = 6 + 8
4: 1 12 121 1212 1213 123 1231 1232 13 131 1312 1313 132 1321 1323 2 21 212 2121 2123 213 2131 2132 23 231 2312 2313 232 2321 2323 => 30 = 14 + 16
*/
        long long i=0, j=2, ni=1;
        while (ni < n) {
                i = i+j;
                j = 2*j;
                ni++;
        }
        long long s = i+j; // ni=3, s=14
        while (k > 0) { // k=0..14
                long long mid = s/2; // 7
                if (k <= mid) { // in 1..7
                        last = last == 'a' ? 'b' : 'a';
                } else {
                        last = last == 'c' ? 'b' : 'c';
                }
                printf("%c", last);
                k = (k-1) % mid; // k: 1..7 -> 0..6, 8..14 -> 0..6
                s = s / 2 - 1; // 30 -> 14 -> 6 -> 2
        }
        printf("\n");
}

int main() {
        long long n, k;
        scanf("%lld %lld", &n, &k);
        if (k <= n) {
                long long i;
                for(i=0; i<k; i++) {
                        printf("%c", (i%2) == 0 ? 'a' : 'b');
                }
                printf("\n");
                return 0;
        } else if (n > 60) {
                char last;
                long long i;
                for(i=0; n > 60; i++, n--, k--) {
                        last = (i%2) == 0 ? 'a' : 'b';
                        printf("%c", last);
                }
                solveRest(n, k, last);
        } else {
                long long i=0, j=3, ni=1; // i - number of total words so far (for up to ni-1 chars in each word), j - number of words of exactly ni chars length
/*
1: a b c => 3 = 0 + 3; i=0, j=3, ni=1
2: a ab ac b ba bc c ca cb 9 = 3 + 6, i=3, j=6, ni=2
3: a ab aba abc ac aca acb b ba bab bac bc bca bcb c ca cab cac cb cba cbc 21 = 9 + 12, i=9, j=12, ni=3
*/
                while (ni < n) {
                        i = i+j;
                        j = 2*j;
                        ni++;
                }
                if (k > i+j) {
                        printf("NIE\n");
                        return 0;
                }
                long long lastA = (i+j)/3;
                long long lastB = lastA * 2;
                char last = k <= lastA ? 'a' : k <= lastB ? 'b' : 'c';
                printf("%c", last);
                solveRest(n-1, (k-1) % lastA, last);
        }
        return 0;
}