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
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <vector>
#include <string>

std::string* Split(std::string input, char delimiter = ' ')
{
    std::vector<std::string> output;
    output.push_back("");
    int index = 0;
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == delimiter)
        {
            index++;
            output.push_back("");
            continue;
        }
        output[index] += input[i];
    }
    std::string* outputArray = new std::string[output.size()];
    std::copy(output.begin(), output.end(), outputArray);
    return outputArray;
}

bool try_a_combination(int n, std::string* toys, int* replica, int index, int iteration, int toys_sum, bool direction)
{
    iteration++;
    (direction) ? index++ : index--;
    if (index < 0) index += 2;
    if (index >= n) index -= 2;
    if (n < 2 || iteration >= toys_sum)
    {
        bool valid_input = true;
        for (int i = 0; i < n; i++)
        {
            if (stoi(toys[i]) != replica[i])
            {
                valid_input = false;
                break;
            }
        }
        return valid_input;
    }
    replica[index]++;

    if (replica[index] > stoi(toys[index])) return false;

    int replica_copy[n];
    for (int i = 0; i < n; i++) replica_copy[i] = replica[i];

    bool left_turn = try_a_combination(n, toys, replica, index, iteration, toys_sum, false);
    bool right_turn = try_a_combination(n, toys, replica_copy, index, iteration, toys_sum, true);

    return left_turn || right_turn;
}

int main()
{
    std::string buf;
    std::getline(std::cin, buf);
    int t = stoi(buf);
    
    for (int i = 0; i < t; i++)
    {
        std::getline(std::cin, buf);
        int n = stoi(buf);
        std::getline(std::cin, buf);
        std::string* toys = Split(buf);
        int replica[n];
        for (int i = 0; i < n; i++) replica[i] = 0;
    
        int max_value = 0;
        int max_value_index = 0;
        int toys_sum = 0;
        for (int j = 0; j < n; j++)
        {
            toys_sum += stoi(toys[j]);
            if (stoi(toys[j]) > max_value)
            {
                max_value = stoi(toys[j]);
                max_value_index = j;
            }
        }
    
        replica[max_value_index]++;
        int iteration = 0;

        int replica_copy[n];
        for (int i = 0; i < n; i++) replica_copy[i] = replica[i];
    
        bool left_turn = try_a_combination(n, toys, replica, max_value_index, iteration, toys_sum, false);
        bool right_turn = try_a_combination(n, toys, replica_copy, max_value_index, iteration, toys_sum, true);
    
        bool valid_input = left_turn || right_turn;
    
        (valid_input) ? std::cout << "TAK" << "\n" : std::cout << "NIE" << "\n";
    }
    return 0;
}