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 <vector>
#include <iostream>

struct fight
{
    bool visited;
    int a;
    int d;
    
    fight(int a_i, int d_i, bool v)
    {
        a = a_i;
        d = d_i;
        visited = 0;
    }
};

bool search_path(std::vector<fight> fights, int z, std::vector<int> & path)
{
    std::vector<fight> new_fihgts;
    std::vector<int> new_path;
    int zdrowie;
    for(int i=0; i<fights.size(); ++i)
    {
        if(not fights.at(i).visited and z > fights.at(i).d)
        {
            new_fihgts = fights;
            new_fihgts.at(i).visited = true;
            zdrowie = z - fights.at(i).d + fights.at(i).a;
            new_path = std::vector<int>(path);
            new_path.push_back(i+1);
            
            if (search_path(new_fihgts, zdrowie, new_path))
            {
                path = new_path;
                return true;
            }
        }
    }

    if( new_path.size() == fights.size())
    {
            path = new_path;
        return true;
    }
    else return false;
 
}

void print_path(std::vector<int> p){
    for(int i = 0; i<p.size(); i++)
        printf("%d ", p.at(i));
}

int main()
{
    int z, c, a, d, n;
    std::vector<fight> f;
    std::vector<int> p;
    scanf("%d %d", &n, &z);
    
    
    for ( c = 0 ; c < n ; c++ )
    {
        scanf("%d %d", &d, &a);
        f.push_back(fight(a, d, false));
    }
    
    if (search_path(f, z, p))
    {
        printf("TAK\n");
        print_path(p);
    }
    else
        printf("NIE\n");
    
}