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
#include <cstdio>
#include <cstdlib>

#include <algorithm>
#include <set>
#include <vector>

struct mine {
    long long int pos, radius;
    int id;

    inline bool operator<(const mine& other) const {
        if (pos != other.pos) {
            return pos < other.pos;
        }
        return radius < other.radius;
    }
};

int main() {
    int n;
    scanf("%d", &n);
    if (n > 30) {
        puts("NOPE");
        return 0;
    }

    std::vector<mine> m;
    for (int i = 0; i < n; i++) {
        mine mi;
        scanf("%lld %lld", &mi.pos, &mi.radius);
        mi.id = i;
        m.push_back(mi);
    }

    // Brute-force it...
    std::vector<bool> results;
    results.resize(1 << n, false);

    std::vector<mine> remaining_vec;
    std::vector<mine> boom_vec;

    unsigned long long int result = 0;

    for (int i = 0; i < (1 << n); i++) {
        int detonated = 0;

        remaining_vec.clear();
        boom_vec.clear();

        for (int j = 0; j < n; j++) {
            const bool has_mine = i & (1 << j);
            if (has_mine) {
                boom_vec.push_back(m[j]);
            } else {
                remaining_vec.push_back(m[j]);
            }
        }

        while (!boom_vec.empty()) {
            mine mi = boom_vec.back();
            boom_vec.pop_back();

            auto it = std::remove_if(remaining_vec.begin(), remaining_vec.end(), [mi] (const mine& m) {
                return mi.pos - mi.radius <= m.pos && m.pos <= mi.pos + mi.radius;
            });
            auto old_it = it;
            for (; it < remaining_vec.end(); ++it) {
                boom_vec.push_back(*it);
            }
            remaining_vec.resize(std::distance(remaining_vec.begin(), old_it));
        }

        for (const auto& mi : remaining_vec) {
            detonated |= 1 << mi.id;
        }

        if (!results[detonated]) {
            results[detonated] = true;
            result++;
        }
    }

    printf("%llu\n", result);
    return 0;
}