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>
#include <map>

using namespace std;

struct node{
    long long  id;
    long long d;
    string state;
    vector<long long> children;
};

vector<struct node> nodes;
map<string, int> states;

string subset;

int n;

void dfs(long long deep, long long ix, long long nd){
    
    nodes[nd].state[ix] = '1';
    
    if(deep<=n){
        for(long long i=0; i<nodes[ix].children.size(); i++){
            if(nodes[nd].state[nodes[ix].children[i]] == '0')
                dfs(deep+1, nodes[ix].children[i], nd);
        }
    }
}

int main()
{
    cin >> n;
    
    string state = "";
    
    for(int i=0; i<n; i++){
        state+="0";
    }
    
    for(int i=0; i<n; i++){
        long long id, d;
        cin >> id >> d;
        
        struct node new_node;
        new_node.id = id;
        new_node.d = d;
        new_node.state = state;

        nodes.push_back(new_node);
    }
    
    //Get children
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i!=j){
                if( nodes[j].id>=(nodes[i].id - nodes[i].d) && nodes[j].id <=(nodes[i].id + nodes[i].d)){
                    nodes[i].children.push_back(j);
                }
            }
        }
    }
    
    //Get all states
    for(int i=0; i<n; i++){
        dfs(0, i, i);
    }
    
    //Iter over all subsets
    for(int i=0; i<(1<<n); i++){
        
        subset = "";
        
        for(int j=0; j<n; j++){
            if(((i>>j)&1) == 1){
                subset += "1";
            }else{
                subset += "0";
            }
        }
        
        for(int j=0; j<n; j++){
            if(subset[j]=='1'){
                for(int k=0; k<n; k++){
                    if(nodes[j].state[k]=='1'){
                        subset[k] = '1';
                    }
                }
            }
        }
        
        states[subset]++;
    }
    
    cout << states.size();
}