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
#include <stdint.h>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

#define INF 1000000000000000001

vector<vector<int64_t> > P;
vector<int64_t> row_length;

int64_t get(int64_t n, int64_t c) {
    int64_t row_len = row_length[n];
    int64_t mirrored_c = row_len - c - 1;
    if (c<0 || c>row_len-1) return 0;
    if (c<P[n].size()) return P[n][c];
    if (mirrored_c<P[n].size()) return P[n][mirrored_c];
    return INF;
}

void populate(int64_t n) {
    row_length.clear(); row_length.resize(n+1);
    row_length[0] = 1;

    P.clear(); P.resize(n+1);
    P[0].push_back(1);

    for(int64_t i=1; i<=n; ++i) {
        row_length[i] = row_length[i-1] + i - 1;
        P[i].push_back(1);
        for (int64_t j=1; j<row_length[i]; ++j) {
            int64_t x = get(i, j-1) + get(i-1, j) - get(i-1, j-i);
            if (x >= INF) break;
            P[i].push_back(x);
        }
    }
}

int64_t N;
int64_t K, C;

int main(){
    scanf("%lld %lld", &N, &K);
    if (N%4>1){ printf("NIE"); return 0; }
    populate(N);
    C = N*(N-1)/4;
    if (get(N, C) <= K-1){ printf("NIE"); return 0; }

    K -= 1;
    printf("TAK\n");
    set<int32_t> D; for(int32_t i=1; i<=N; ++i) D.insert(i);
    for(int32_t i=0; i<N; ++i) {
        int64_t init_d = C-row_length[N-i-1]+1;
        if (init_d < 0) init_d = 0;

        for(int64_t d=init_d; d<N-i; ++d) {
            int64_t sub_factor = get(N-i-1, C-d);
            if (sub_factor <= K) {
                K = K - sub_factor;
                continue;
            } else {
                C = C - d;
                set<int32_t>::iterator it;
                if (d < D.size()-d-1) {
                    it = D.begin();
                    for(int32_t j=0; j!=d; ++j) ++it;
                } else {
                    it = D.end();
                    for(int32_t j=D.size(); j!=d; --j) --it;
                }
                printf("%d ", *it);
                D.erase(it);
                break;
            }
        }
    }
}