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
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstdlib>

typedef unsigned long long ull;

static const ull MAX_N = 1000 * 1000;
static const ull MAX_M = MAX_N * MAX_N * MAX_N;
static const ull LENGTH_OVER_LIMIT_FROM = 59;

static char outbuffer[MAX_N + 1];

inline ull countWordsBeginningWithA(ull upToLength)
{
    return (1ULL << upToLength) - 1ULL;
}

inline char chooseNextLetter(char prevLetter, int choice) {
    static const char choices[6] = {
        'b', 'c',
        'a', 'c',
        'a', 'b'
    };

    return choices[2 * (prevLetter - 'a') + choice];
}

int main(int argc, char ** argv)
{
    int n;
    ull k;
    scanf("%d %llu", &n, &k);

    k--; // Convert to 0-based number

    // Choose the first letter
    char currLetter = 'a';
    if (n < LENGTH_OVER_LIMIT_FROM) {
        const ull tailCount = countWordsBeginningWithA(n);
        // printf("TC1 %llu\n", tailCount);
        if (k >= 3 * tailCount) {
            puts("NIE");
            return 0;
        }
        else if (k >= 2 * tailCount) {
            currLetter = 'c';
            k -= 2 * tailCount;
        }
        else if (k >= tailCount) {
            currLetter = 'b';
            k -= tailCount;
        }
    }

    int written = 0;
    for (int i = 0; i < n; i++) {
        const int lengthRemaining = n - (i + 1);

        outbuffer[written++] = currLetter;

        if (k == 0) {
            // puts("END");
            break;
        }

        k--;

        if (lengthRemaining >= LENGTH_OVER_LIMIT_FROM) {
            currLetter = chooseNextLetter(currLetter, 0);
            continue;
        }
        else {
            const ull tailCount = countWordsBeginningWithA(lengthRemaining);
            // printf("LR: %d, TC: %llu, k: %llu\n", lengthRemaining, tailCount, k);
            if (k >= tailCount) {
                k -= tailCount;
                currLetter = chooseNextLetter(currLetter, 1);
            }
            else {
                currLetter = chooseNextLetter(currLetter, 0);
            }
        }
    }

    outbuffer[written] = '\0';
    puts(outbuffer);

    return 0;
}