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
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int N = ((int)(3e5))+50;

int n;
vector <int> graph[N];
pair<int,int> tab[N];
long long returns[N];
bool met[N];
map <long long, bool> mapka;

long long detonate( int pos ){
	met[pos] = 1;
	long long ret = 0; 
	ret |= (1<<pos);
	for (int i = 0; i < (int)graph[pos].size(); i++){
		if(!met[graph[pos][i]]){
			ret |= detonate(graph[pos][i]);
		}
	}
	met[pos] = 0;
	return ret;
}

int main(){
	ios_base::sync_with_stdio( 0 ); cout.tie( 0 ); cin.tie( 0 );
	cin>>n;
	int t1,t2;
	for (int i = 0; i < n; i++){
		cin>>t1>>t2;
		tab[i] = {t1 , t2};
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if(abs(tab[j].f-tab[i].f) <= tab[i].s){
				graph[i].push_back(j);
			}
		}
	}
	for (int i = 0; i < n; i++){
		returns[i] = detonate(i);
	}
	long long wynik = 0;
	for (int i = 1; i < (1<<n); i++){
		long long dets = 0;
		for (int j = 0; j < n; j++){
			if( (i & (1<<j)) > 0 ){
				dets |= returns[j];
			}
		}
		if(mapka[dets] == 0){
			mapka[dets] = 1;
			wynik++;
		}
	}
	cout<<wynik+1;
	return 0;
}