class Solution {
    using ll = long long;
public:
    int numberofprize(int a, int b, int c) {
        ll x = a;
        ll y = b;
        ll z = c;
        ll cnt = 0;
        if(x < y) swap(x, y);
        if(x < z) swap(x, z);
        if(y < z) swap(y, z);
        
        cnt += z;
        x -= z;
        y -= z;

        if(y == 0) {
            return cnt + x / 5;
        }
        return cnt + (x + y) / 4;
    }
};

class Solution {
    const double eps = 1e-6;
    using pdd = pair<double, double>;
public:
    int getHouses(int t, int* xa, int xaLen) {
        vector<pdd> arr(xaLen / 2);
        int n = arr.size();
        if(n == 0) return 0;
        if(n == 1) return 2;
        for(int i = 0, t = 0; i < xaLen; i += 2) {
            arr[t].first = xa[i] - (xa[i+1] / 2.0);
            arr[t++].second = xa[i] + (xa[i+1] / 2.0);
        }
        set<double> pos;
        pos.insert(arr[0].first);
        for(int i = 1; i < n; ++i) {
            double dx = arr[i].first - arr[i-1].second;
            if(dx < t) continue;
            if(dx - t <= eps) {
                pos.insert(arr[i].first);
            } else {
                pos.insert(arr[i-1].second);
                pos.insert(arr[i].first);
            }
        }
        pos.insert(arr[n-1].second);
        return pos.size();
    }
};

class Solution {
    using ll = long long;
public:
    long long getPasswordCount(string password) {
        set<string> ans;
        if(password.size() <= 1) return 9;
        for(int i = 0; i < 10; ++i) {
            string path = to_string('0' + i);
            dfs(password, 1, path, ans);
        }
        if(ans.count(password)) return ans.size()-1;
        return ans.size();
    }
    void dfs(string& s, int left, string p, set<string>& ans) {
        if(left >= s.size()) {
            ans.insert(p);
            return;
        }

        int val = (p.back() - '0') + (s[left] - '0');
        char ch = ('0' + val/2);

        if(val&0x1) {
            p.push_back(ch);
            dfs(s, left+1, p, ans);
            p.pop_back();

            ch++;
            p.push_back(ch);
            dfs(s, left+1, p, ans);
            p.pop_back();
        } else {
            p.push_back(ch);
            dfs(s, left+1, p, ans);
            p.pop_back();
        }
    }
};