class Solution {
public:
  int numberofprize(int a, int b, int c) {
    int lo = 0, hi = 1E9;
    int ret = 0;

    auto check = [&](int val) {
      int tmp = 0;
      int x = a, y = b, z = c;
      x -= val, y -= val, z -= val;
      if (x >= 0) tmp += x, x = 0;
      if (y >= 0) tmp += y, y = 0;
      if (z >= 0) tmp += z, z = 0;
      return tmp / 2 >= -(x + y + z);
    };

    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (check(mid)) {
        ret = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return ret;
  }
};

class Solution {
public:
  int getHouses(int t, int* xa, int xaLen) {
    int ret = 2;
    vector<int> x, a;
    for (int i = 0; i < xaLen; i += 2) {
      x.emplace_back(xa[i]);
      a.emplace_back(xa[i + 1]);
    }
    int n = x.size();
    if (n == 1) return 2;
    for (int i = 0; i < n - 1; i++) {
      double lo = (double)x[i] + (double)a[i] / 2.0;
      double hi = (double)x[i + 1] - (double)a[i + 1] / 2.0;
      if (hi - lo < t) continue;
      if (hi - lo == t) {
        ret++;
      } else {
        ret += 2;
      }
    }
    return ret;
  }
};

using LL = long long;

class Solution {
public:
  long long getPasswordCount(string password) {
    int n = password.length();
    LL f[11][55];
    memset(f, -1, sizeof f);
    function<LL(int, int, int flag)> dfs = [&](int i, int len, int flag) {
      if (~f[i][len]) return f[i][len];
      if (len == n) return 1LL - flag;
      LL ret = 0;
      double tmp = password[len] - '0' + i;
      tmp =  (double)(tmp) / 2.0;
      if (tmp != (int)tmp) {
        tmp++;
        ret += dfs((int)tmp, len + 1, flag && ((int)tmp == password[len] - '0'));
      }
      tmp = (password[len] - '0' + i) / 2.0;
      ret += dfs((int)tmp, len + 1, flag && ((int)tmp == password[len] - '0'));
      return f[i][len] = ret;
    };
    LL ret = 0;
    if (n == 1) return 9;
    for (int i = 0; i <= 9; i++) {
      memset(f, -1, sizeof f);
      ret += dfs(i, 1, i == password[0] - '0');
    }
    return ret;
  }
};