[2018 ICPC 青岛] 解题记录ing

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int get(int x) {
  if (x == 0) return 1;
  int sum = 0;
  while (x) {
    int d = x % 10;
    x /= 10;
    if (d == 0 || d == 4 || d == 6 || d == 9) sum += 1;
    else if (d == 8) sum += 2;
  }
  return sum;
}
int main() {
  int t; scanf("%d", &t);
  while (t--) {
    int x, k; scanf("%d%d", &x, &k);
    int res;
    if (k == 0) {
      res = x;
      printf("%d\n", res);
      continue;
    }
    while (k--) {
      x = get(x);
      res = x;
      if (x == 1) {
        if (k % 2 == 0) {
          res = 1;
        }
        else res = 0;
        break;
      }
    }
    printf("%d\n", res);
  }
  return 0;
}

const int maxn=1e6+7;
int T,n,a[maxn],b[maxn],f;
char x[maxn],y[maxn];
ll sum;
int main(){
  T=read();
  while(T--){
    n=read();
    scanf("%s%s",x,y);
    f=0;
    for(int i=0;i<n;i++){
      a[i+1]=x[i]-'0';
      b[i+1]=y[i]-'0';
      if(a[i]==b[i]&&a[i+1]!=b[i+1])  f++;
    }
    if(n==1){
      if(a[1]!=b[1])  sum=0;
      else  sum=1;
      out(sum); putchar('\n');
      continue;
    }
    if(f==0)  sum=1ll*n*(n+1)/2;
    else if(f==1) sum=(n-1)*2;
    else if(f==2) sum=6;
    else  sum=0;
    out(sum); putchar('\n');
  }
}

#define Clear(x,val) memset(x,val,sizeof x)
ll a[maxn];
ll nowCnt[maxn],needCnt[maxn];
ll n,m;
bool check(ll mid) {
  if(mid == 0LL) return true;
  for(int i=1; i<=n; i++) {
    nowCnt[i] = 0;
    needCnt[i] = (mid - 1) / a[i] + 1;
  }
  for(int i=1; i<=n; i++) {
    if(n == i && nowCnt[i] >= needCnt[i]) return true;
    /**
    if(nowCnt[i] >= needCnt[i]) {
      if(i == n) return true;
    //      continue;
    }
    **/
    if(m <= 0) return false;
    ++ nowCnt[i];
    -- m;
    if(nowCnt[i] >= needCnt[i]) continue;/// already okay
    ///else:
    ll stillNeed = needCnt[i] - nowCnt[i];
    if(stillNeed*2 > m) return false;
    m -= 2 * stillNeed;
    nowCnt[i+1] += stillNeed;/// * 2
    /**
    cur_pos + 1
    **/
  }
  return true;
}
int main() {
  int _ = read;
  while (_ --) {
    n = read,m = read;
    ll tm = m;
    ll mini = 0x3f3f3f3f;
    for(int i=1; i<=n; i++) {
      a[i] = read;
      mini = min(mini,a[i]);
    }
//    /**
    if(m == 0) {
      puts("0");
    } else if(m < n) {
      puts("0");
    } else if(m == n) {
      printf("%lld\n",mini);
    } else {
//      **/
      ll l = 0,r = 1e17 + 1;
      while(l < r) {
        ll mid = l + r + 1>> 1;
        m = tm;
        if(check(mid)) l = mid;
        else r = mid - 1;
      }
      printf("%lld\n",l);
    }
  }
  return 0;
}
/**
2
4 8
3 2 6 6
3 9
10 10 1
**/

int a[maxn];
vector<int> vet;
int main() {
  int _ = read;
  while (_ --) {
    int n = read,m = read;
    int cnt = 0;
    vet.clear();
    vet.push_back(0);
    int zero = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
      if (a[i] == 0) zero++;
      else vet.push_back(a[i]);
    }
    if (zero > m) {
      puts("Impossible");
      continue;
    }
    if (n == m) {
      puts("Richman");
      continue;
    }
    int mini = 0x3f3f3f3f;
    int siz = vet.size() - 1;
    m -= zero;
    ll ans = 0;
    int select = 0;
    for(int i=1; i<=siz; i++) {
      ++ select;
      if(select <= m) {
        ans += vet[i];
      } else {
        mini = min(mini,vet[i]);
      }
    }
//    cout << ans << endl;
//    cout << mini << endl;
    ans += mini - 1;
//    cout << ans << endl;
    printf("%lld\n",ans);
  }
  return 0;
}
/**
2
1
5 4
0 0 0 0 1
1
10 3
100000 100000 100000 1 1 1 1 1 1 1
1
10 6
10000 1 1 1 1 1 1 1 10000 10000
4
4 2
1 2 4 8
4 0
100 99 98 97
2 2
10000 10000
5 3
0 0 0 0 1
**/

typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod =  (int)1e9+7;
const int N = 1e5 + 100;
int a[N][2];
pll p[N<<1];
bool cmp(pll & x, pll & y){
    return a[x.fi][x.se] < a[y.fi][y.se];
}
int tree[N<<2][2][2];
void Build(int l, int r, int rt){
    tree[rt][0][0] = tree[rt][0][1] = tree[rt][1][0] = tree[rt][1][1] = 0;
    if(l == r) {
        tree[rt][1][0] = 1;
        return ;
    }
    int m = l+r >> 1;
    Build(lson); Build(rson);
}
void PushUp(int rt){
    tree[rt][0][0] = (tree[rt<<1][0][0] && tree[rt<<1|1][0][0]) || (tree[rt<<1][0][1] && tree[rt<<1|1][1][0]);
    tree[rt][0][1] = (tree[rt<<1][0][0] && tree[rt<<1|1][0][1]) || (tree[rt<<1][0][1] && tree[rt<<1|1][1][1]);
    tree[rt][1][0] = (tree[rt<<1][1][0] && tree[rt<<1|1][0][0]) || (tree[rt<<1][1][1] && tree[rt<<1|1][1][0]);
    tree[rt][1][1] = (tree[rt<<1][1][1] && tree[rt<<1|1][1][1]) || (tree[rt<<1][1][0] && tree[rt<<1|1][0][1]);
}
void Update(int L, int op,int l, int r, int rt){
    if(l == r){
        tree[rt][0][op] ^= 1;
        return ;
    }
    int m = l+r >> 1;
    if(L <= m) Update(L, op, lson);
    else Update(L, op, rson);
    PushUp(rt);
}
int main(){
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        int m = 0;
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a[i][0]);
            p[++m] = pll(i,0);
            if(i-1) {
                a[i-1][1] = a[i-1][0] + a[i][0];
                p[++m] = pll(i-1,1);
            }
        }
        sort(p+1, p+1+m, cmp);
        Build(1,n,1);
        LL ans = INF;
        for(int i = 1, j=1; i <= m; ++i){
            while(j <= m && !tree[1][0][0]){
                Update(p[j].fi, p[j].se, 1, n, 1);
                j++;
            }
            if(tree[1][0][0]) ans = min(ans, 1ll*a[p[j-1].fi][p[j-1].se] - a[p[i].fi][p[i].se]);
            Update(p[i].fi, p[i].se, 1, n, 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}