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
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct vertex{
    int type;
    bool visited;
    vector<int> neighbors;
};

vector<vertex> graph;
int sum;


int dfs(int root){
    int sub_graph;
    if(graph[root].visited) return 0;
    graph[root].visited = true;
    int longestPath = 1;
    for(int i = 0; i < graph[root].neighbors.size(); i++){
        sub_graph = dfs(graph[root].neighbors[i]);
        longestPath = max(sub_graph+1, longestPath);
    }
    return longestPath;
}

int main(void){
    int t, n, k, result;
    bool can_be_achieved;
    vector<int> toy_n;
    scanf("%d", &t);
    for(int day = 0; day < t; day++){
        scanf("%d", &n);
        toy_n.resize(n);
        sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &k);
            toy_n[i] = k;
            sum += k;
        }
        graph.resize(sum);
        for(int i = 0; i < sum; i++) graph[i].neighbors.clear();
        k = 0;
        // wierzchołki mają swój typ
        for(int i = 0; i < n; i++){
            for(int j = 0; j < toy_n[i]; j++, k++){
                graph[k].type = i;
            }
        }
        //stwórz graf, tż dwa wierzchołki są połączone, gdy róznią się typem o 1
        for(int i = 0; i < sum; i++){
            for(int j = 0; j < sum; j++){
                if(graph[i].type -1 == graph[j].type){
                    graph[i].neighbors.push_back(j);
                    graph[j].neighbors.push_back(i);
                }
            }
        }
        can_be_achieved = false;
        //wypisz wyniki przeszukiwania grafu wszerz - wybierz jeden z wierzchołków danego typu i od niego zaczynaj
        for(int i = 0, j = 0; i < sum; i+=toy_n[j], j++){
            for(k = 0; k < sum; k++) graph[k].visited = false;
            result = dfs(i);
            //printf("%d dla wierzchołka typu %d\n", result, j);
            if(result == sum) {
                can_be_achieved = true;
                break;
            }
        }
        if(can_be_achieved) printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}