Notes on Problem-Solving (POJ)

POJ3252

题意:求区间$[l, r]$内二进制表示中$0$的个数不少于$1$的个数的数字有多少个。
题解:只需分别求出$[1, r]$和$[1, l-1]$内满足要求的数的个数,相减即可。要求$[1, n]$内满足要求的个数,可以从高位到低位枚举$n$的二进制表示,如果某一位是$1$,那么这一位上是$0$的数一定都小于$n$(这一位前面的数和原数相同),因此可以直接暴力求出把这一位变成$0$之后满足要求的数的个数。当然也可以用数位DP的思想预处理。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  int l, r, c[40][40];
  void input() {
    cin >> l >> r;
  }
  void init() {
    for (int i = 0; i < 40; ++ i) c[i][0] = c[i][i] = 1;
    for (int i = 2; i < 40; ++ i)
      for (int j = 1; j < i; ++ j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
  }
  int get_sum(int t) {
    int p = t, w = 0, z = 0, nz = 0, ret = 0;
    bool first = true;
    while (p) ++ w, p >>= 1;
    while (~ (-- w)) {
      if (t & (1 << w)) {
        for (int i = 1; i <= w; ++ i) {
          int len = w - i;
          for (int j = 0; j <= len; ++ j) {
            if (nz + 1 + j > z + len - j + (first ? 0 : i)) break;
            ret += c[len][j];
          }
        }
        ++ nz, first = false;
        if (z + w >= nz) ++ ret;
      } else ++ z;
    }
    return ret;
  }
  void process() {
    cout << get_sum(r) - get_sum(l - 1) << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1850

题意:将所有严格上升的字符串按字典序排序后依次编号。求字符串$s$的编号。
题解:令$f_{i, j}$表示以字母$i$开头的长度为$j$的严格上升字符串的个数。根据容斥原理,答案等于长度不大于$s.length()$的严格上升字符串的个数减去长度等于$s.length()$且字典序大于$s$的严格上升字符串的个数。前者可以直接由$f$得到,后者可以用数位DP的思想得到。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  int f[200][12];
  string s;
  void input() {
    cin >> s;
  }
  void init() {
    for (int i = 'a'; i <= 'z'; ++ i) f[i][1] = 1;
    for (int i = 2; i <= 11; ++ i)
      for (int j = 'a'; j < 'z'; ++ j)
        for (int k = j + 1; k <= 'z'; ++ k)
          f[j][i] += f[k][i - 1];
  }
  void process() {
    for (int i = 1; i < s.length(); ++ i)
      if (s[i] <= s[i - 1]) {
        cout << 0 << endl;
        return;
      }
    int ans = 0;
    for (int i = 1; i <= s.length(); ++ i)
      for (int j = 'a'; j <= 'z'; ++ j)
        ans += f[j][i];
    for (int i = 0; i < s.length(); ++ i)
      for (int j = s[i] + 1; j <= 'z'; ++ j) ans -= f[j][s.length() - i];
    cout << ans << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1019

题意:定义字符串$s_i$为从$1$到$i$的数字连起来写。求$s_1s_2s_3…$中的第$n$个字符。
题解:先求出第$n$个字符在哪个$s$中,再求出它在$s$的哪个数字中,接着可以暴力出解。可以预处理出$s_i$的长度和$s_1s_2…s_i$的长度。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Solver {
private:
  static const int N = 50000;
  ll n, d[N], f[N], s[N], top, q[N];
  void input() {
    cin >> n;
  }
  int get_digit(int t) {
    int ret = 0;
    while (t) t /= 10, ++ ret;
    return ret;
  }
  void process() {
    int rec;
    for (int i = 1; i <= 50000; ++ i)
      if (n <= s[i]) {
        rec = i - 1; break;
      }
    n -= s[rec];
    for (int i = 1; i <= 50000; ++ i)
      if (n <= f[i]) {
        rec = i - 1; break;
      }
    n -= f[rec ++], top = 0;
    while (rec)
      q[++ top] = rec % 10, rec /= 10;
    if (n == 1) cout << q[top] << endl;
    if (n == 2) cout << q[top - 1] << endl;
    if (n == 3) cout << q[top - 2] << endl;
    if (n == 4) cout << q[top - 3] << endl;
    if (n == 5) cout << q[top - 4] << endl;
  }

public:
  void init() {
    for (int i = 1; i <= 50000; ++ i) {
      d[i] = get_digit(i);
      f[i] = f[i - 1] + d[i];
      s[i] = s[i - 1] + f[i];
      if (s[i] > 2147483647) break;
    }
  }
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  int T; cin >> T;
  solver.init();
  while (T --) solver.solve();
  return 0;
}

POJ1942

题意:求${n+m \choose n}$的值,$n, m$和答案均为32位无符号整数。
题解:${n+m \choose n}={(n+m)! \over n!m!}=(m+1) \times (m+2) \div 2 \times (m+3) \div 3 \times … \times (m + n)\div n$。除非$m=0$,否则这个数是按指数级增长的。因此可以直接计算。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  unsigned long long n, m;
  bool input() {
    cin >> n >> m;
    if (! n && ! m) return false;
    return true;
  }
  void process() {
    if (n > m) swap(n, m);
    n += m;
    if (m == 0 || m == n) {
      cout << 1 << endl;
      return;
    }
    if (m == 1 || m == n - 1) {
      cout << n << endl;
      return;
    }
    ll ans = (m + 1) * (m + 2) / 2;
    for (int i = 3; i <= n - m; ++ i) {
      (ans *= (m + i)) /= i;
    }
    cout << ans << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2635

题意:给定一个最多$100$位的数字,已知它是由两个质数相乘得到的。问那两个质数中较小的数是否比$l (l \le 10^6)$大。
题解:将$10^6$以内的质数全部筛出来,直接枚举每个质数,高精度取模,判断是否整除。压10位就能AC。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

const ll BASE[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

struct Prime {
private:
  static const ll N = 1000000;
  bool vis[N + 1];

public:
  ll prime[N + 1];
  void init() {
    memset(prime, 0, sizeof prime);
    memset(vis, false, sizeof vis);
    for (ll i = 2; i <= N; ++ i) {
      if (! vis[i]) prime[++ prime[0]] = i;
      for (ll j = 1; j <= prime[0] && i * prime[j] <= N; ++ j) {
        vis[i * prime[j]] = true;
        if (! (i % prime[j])) break;
      }
    }
  }
} prime;

struct Solver {
private:
  static const ll N = 15;
  ll l, a[N], b[N];
  string k;
  bool input() {
    cin >> k >> l;
    if (k == "0" && ! l) return false;
    return true;
  }
  bool check(ll t) {
    for (ll i = 0; i <= a[0]; ++ i) b[i] = a[i];
    for (ll i = *b; i > 1; -- i) b[i - 1] += b[i] % t * BASE[10];
    return ! (b[1] % t);
  }
  void init() {
    ll cnt = 0; a[0] = 1, a[a[0]] = 0;
    for (ll i = k.length() - 1; ~ i; -- i) {
      if (cnt == 10) cnt = 0, a[++ a[0]] = 0;
      a[a[0]] += (k[i] - '0') * BASE[cnt ++];
    }
    for (ll i = 1; i <= prime.prime[0] && prime.prime[i] < l; ++ i)
      if (check(prime.prime[i])) {
        cout << "BAD " << prime.prime[i] << endl;
        return;
      }
    cout << "GOOD" << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  prime.init();
  while (solver.solve()) ;
  return 0;
}

POJ3292

题意:定义H数为$4n+1 (n \in N)$。H数分为三类:单位($1$),不能由其他非单位H数相乘得到的数(H质数),以及剩下的所有数(H合数)。求给定数以内恰由两个H质数相乘得到的数的个数。
题解:筛出所有H质数,然后暴力枚举任意两个相乘。由于给定数的范围不超过$1000001$,因此相乘不超过这个范围的H质数对比较少。最后求一个前缀和即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Solver {
private:
  static const int N = 1000001;
  ll n, top, num[N + 1], tot, prime[N + 1], sum[N + 1];
  bool vis[N + 1];
  bool input() {
    cin >> n; return n;
  }
  void process() {
    cout << n << ' ' << sum[n] << endl;
  }

public:
  void init() {
    for (int i = 1; (i << 2) + 1 <= N; ++ i)
      num[++ top] = (i << 2) + 1;
    for (int i = 1; i <= top; ++ i)
      if (! vis[num[i]]) {
        prime[++ tot] = num[i];
        for (int j = num[i] << 1; j <= N; j += num[i]) vis[j] = true;
      }
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= tot; ++ i)
      for (int j = i; j <= tot && prime[i] * prime[j] <= N; ++ j)
        vis[prime[i] * prime[j]] = true;
    for (int i = 1; i <= N; ++ i) sum[i] = sum[i - 1] + vis[i];
  }
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.init();
  while (solver.solve()) ;
  return 0;
}

POJ1845

题意:求$A^B$的约数和$S$。
题解:若$n=p_1^{a_1}p_2^{a_2}…p_m^{a_m}$,则$S=(p_1^0+p_1^1+…+p_1^{a_1})(p_2^0+p_2^1+…+p_2^{a_2})…(p_m^0+p_m^1+…+p_m^{a_m})$。将$A$分解质因数,把每个因数的个数乘上$B$,用等比数列求和公式求和,最后累乘得到答案。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Solver {
private:
  static const ll MOD = 9901;
  ll a, b;
  void input() {
    cin >> a >> b;
  }
  ll power(ll a, ll b) {
    ll ret = 1;
    while (b) {
      if (b & 1) (ret *= a) %= MOD;
      (a *= a) %= MOD, b >>= 1;
    }
    return ret;
  }
  ll get_inv(ll t) {
    return power(t, MOD - 2);
  }
  void init() {
    if (a == 0) {
      cout << 0 << endl; return;
    }
    ll ans = 1, q = (ll) sqrt(a);
    for (int i = 2; i <= q; ++ i) {
      if (! (a % i)) {
        ll tot = 0;
        while (! (a % i)) ++ tot, a /= i; tot *= b;
        if (i % MOD == 1) {
          (ans *= tot + 1) %= MOD;
        } else {
          (ans *= (1 - power(i, tot + 1)) * get_inv(1 - i) % MOD) %= MOD;
        }
      }
    }
    if (a > 1) {
      ll tot = b;
      if (a % MOD == 1) (ans *= tot + 1) %= MOD;
      else (ans *= (1 - power(a, tot + 1)) * get_inv(1 - a) % MOD) %= MOD;
    }
    cout << (ans % MOD + MOD) % MOD << endl;
  }

public:
  void solve() {
    input(), init();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2115

题意:有如下程序:

for (variable = A; variable != B; variable += C) statement;

已知$A, B, C$均为$k$位无符号整型。给定$A, B, C, k$,问该循环能执行几次。
题解:由题意得到方程$A+Cx \equiv B \pmod {2^k}$,化简得$Cx \equiv B-A \pmod {2^k}$。这是一个单变元模线性方程。下面来解该方程。
设方程为$ax \equiv b \pmod n$,它等价于$ax-ny=b$。首先求出$d=gcd(a, n)$,如果$d \not \mid b$,则方程无解。否则,方程两边同除以$d$,得到$a’x-n’y=b’$,此时$(a’, n’)=1$,用exgcd求出$a’x-n’y=1$的解$x_0$,$x=x_0 \times b’$即得到原方程的一个解。其他$d-1$个解可以通过这个解加若干次$b’=b/d$得到。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

struct Solver {
private:
  ll a, b, c, k, mod;
  bool input() {
    cin >> a >> b >> c >> k;
    return a || b || c || k;
  }
  void init() {
    mod = 1ll << k, b -= a;
    if (b < 0) b += mod;
  }
  ll get_gcd(ll a, ll b, ll &x, ll &y) {
    if (! b) {
      x = 1, y = 0; return a;
    }
    ll ret = get_gcd(b, a % b, y, x);
    y -= a / b * x; return ret;
  }
  void process() {
    ll x, y, gcd = get_gcd(c, mod, x, y);
    ((x %= mod) += mod) %= mod;
    if (b % gcd) cout << "FOREVER" << endl;
    else cout << (ull) x * (b / gcd) % (mod / gcd) << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ3273

题意:有$N$个数排成一行,要将它们分成恰好$M$组,使得每一组数字之和的最大值最小,求这个最小值。
题解:直接二分答案,贪心判断是否可行。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Solver {
private:
  static const ll N = 100000;
  ll n, m, a[N + 1], ma;
  void input() {
    cin >> n >> m;
    for (ll i = 1; i <= n; ++ i) cin >> a[i], ma = max(ma, a[i]);
  }
  bool check(ll t) {
    ll tot = 0, cnt = 1;
    for (int i = 1; i <= n; ++ i) {
      tot += a[i];
      if (tot > t) tot = a[i], ++ cnt;
      if (cnt > m) return false;
    }
    return cnt <= m;
  }
  void process() {
    ll l = ma, r = ma * 10000;
    while (l < r) {
      ll mid = l + r >> 1;
      if (check(mid)) r = mid;
      else l = mid + 1;
    }
    cout << l << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ3258

题意:在$N$个数中恰好删去$M$个数,使得剩下的数中每两个数之差的最小值最大,求这个最大值。
题解:先将$N$个数排序,接着二分最大值,利用贪心判断是否可行。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Solver {
private:
  static const ll N = 50000;
  ll len, n, m, a[N + 1];
  void input() {
    scanf("%lld%lld%lld", &len, &n, &m);
    for (ll i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    a[++ n] = len;
  }
  void init() {
    sort(a, a + n + 1);
  }
  bool check(ll t) {
    ll last = 0, tot = 0;
    for (int i = 1; i <= n; ++ i) {
      if (a[i] - last < t) ++ tot;
      else last = a[i];
    }
    return tot <= m;
  }
  void process() {
    ll l = 1, r = len + 1;
    while (l + 1 < r) {
      ll mid = l + r >> 1;
      if (check(mid)) l = mid;
      else r = mid;
    }
    printf("%lld\n", l);
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ1905

题意:给定弓形的弧长$l$和弦长$a$,求弧的顶端到弦的距离。
题解:二分答案。可以发现距离越大弧越长。设距离为$x$,圆的半径为$r$,则$(r-x)^2+({a \over 2})^2=r^2$,化简得$r={x^2+({a \over 2})^2 \over 2x}$,接着可以用三角函数计算出弧长,和$l$比较,决定向哪边二分。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

typedef double ld;

using namespace std;

struct Solver {
private:
  ld a, b, c, l;

bool input() {
    cin >> a >> b >> c;
    return a >= 0 && b >= 0 && c >= 0;
  }
  void init() {
    l = (1 + b * c) * a;
  }
  void process() {
    ld L = 0.0, M, R = 0.5 * a;
    while (R - L > 1e-5) {
      M = (L + R) / 2;
      ld r = (M * M + a * a / 4) / 2 / M;
      ld len = 2 * r * asin(a / 2 / r);
      if (len < l) L = M; else R = M;
    }
    cout << setprecision(3) << fixed << M << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ3122

题意:有$N$块饼和$F$个人,要求每个人分到大小相同的饼,且任意一个人分到的饼都来自同一块饼上,求每个人最多能拿到多大的饼。
题解:二分答案。易知每个人分的饼越大,能分的人就越少。对于每个答案可以直接计算能分多少人。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

typedef double ld;

using namespace std;

struct Solver {
private:
  static const ld PI = 3.14159265359;
  static const int N = 10000;
  int n, f;
  ld a[N + 1];
  void input() {
    scanf("%d%d", &n, &f), ++ f;
    for (int i = 1; i <= n; ++ i) scanf("%lf", &a[i]), a[i] *= a[i];
  }
  void process() {
    ld l = 0, r = 100000000;
    while (r - l > 1e-7) {
      ld mid = (l + r) / 2;
      ld sum = 0;
      for (int i = 1; i <= n; ++ i) {
        sum += floor(a[i] / mid);
        if (sum >= f) break;
      }
      if (sum >= f) l = mid; else r = mid;
    }
    cout << setprecision(4) << fixed << l * PI << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  int T; scanf("%d", &T);
  while (T --) solver.solve();
  return 0;
}

POJ2031

题意:空间中有$N$个球,给定每个球的半径和球心的坐标,求将这些球全部连起来至少需要多长的线。两球相连的条件是两球相交或两球间有连线。
题解:易知两球间所需连线的长度为$len_{i, j}=max(0, dist_{i, j}-r_i-r_j)$。将所有$len_{i, j}$存下来之后做一次最小生成树就可以了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

typedef double ld;

using namespace std;

struct Ball {
public:
  ld x, y, z, r;
  ld get_dist(Ball a) {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z)) - r - a.r;
  }
};

struct Line {
public:
  int a, b;
  ld w;
  bool operator < (const Line &a) const {
    return w < a.w;
  }
};

struct UnionFind {
private:
  static const int N = 100;
  int fa[N + 1];
  int get_fa(int t) {
    return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
  }

public:
  void init() {
    for (int i = 1; i <= N; ++ i) fa[i] = i;
  }
  void merge(int a, int b) {
    fa[get_fa(b)] = get_fa(a);
  }
  bool query(int a, int b) {
    return get_fa(a) == get_fa(b);
  }
};

struct Solver {
private:
  static const int N = 100;
  int n, top;
  ld ans;
  Ball ball[N + 1];
  Line line[N * N];
  UnionFind union_find;
  bool input() {
    cin >> n; if (! n) return false;
    for (int i = 1; i <= n; ++ i) cin >> ball[i].x >> ball[i].y >> ball[i].z >> ball[i].r;
    return true;
  }
  void init() {
    top = ans = 0;
    for (int i = 1; i < n; ++ i) {
      for (int j = i + 1; j <= n; ++ j) {
        ld dist = ball[i].get_dist(ball[j]);
        if (dist < 0) line[++ top] = (Line) {i, j, 0};
        else line[++ top] = (Line) {i, j, dist};
      }
    }
    sort(line + 1, line + top + 1);
  }
  void process() {
    union_find.init();
    for (int i = 1; i <= top; ++ i) {
      if (! union_find.query(line[i].a, line[i].b)) {
        ans += line[i].w;
        union_find.merge(line[i].a, line[i].b);
      }
    }
    cout << setprecision(3) << fixed << ans << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1039

题意:有一个管道,其竖直截面的宽度恒为$1$。给定上半轨道折线各点的坐标,求从左管口射入一道光所能到达的$x$坐标的最大值。
题解:对于一条不经过上半轨道或下半轨道任何一个点的一条光线,一定存在一条光线分别经过上、下半轨道的至少一个折点,并且不比这条光线的最远距离近。因此可以枚举经过上半轨道的哪个点和下半轨道的哪个点,计算出这条光线能到达的最远距离。可以用叉积来判断线段和直线是否相交。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

typedef double ld;

using namespace std;

const ld EPS = 1e-8;

int cmp(ld t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

struct Point {
public:
  ld x, y;
  Point(ld a = 0, ld b = 0) : x(a), y(b) {}
  Point operator + (const Point &a) const {
    return Point(x + a.x, y + a.y);
  }
  Point operator - (const Point &a) const {
    return Point(x - a.x, y - a.y);
  }
  Point operator * (const ld &a) const {
    return Point(x * a, y * a);
  }
  Point operator / (const ld &a) const {
    return Point(x / a, y / a);
  }
  ld operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
  ld operator * (const Point &a) const {
    return x * a.y - y * a.x;
  }
  ld operator ^ (const Point &a) const {
    return x * a.x + y * a.y;
  }
};

struct Line {
public:
  Point a, b;
  Line(Point x = Point(), Point y = Point()) : a(x), b(y) {
    if (a.x > b.x) swap(a, b);
  }
  bool operator | (const Line &x) const {
    return cmp((b - a) * (x.a - b)) == 1 && cmp((b - a) * (x.b - b)) == -1 || cmp((b - a) * (x.a - b)) == -1 && cmp((b - a) * (x.b - b)) == 1;
  }
  Point operator * (const Line &x) const {
    Point ret = a;
    ld t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b));
    return ret + (b - a) * t;
  }
  ld ratio() {
    return (b.y - a.y) / (b.x - a.x);
  }
};

struct Solver {
private:
  static const int N = 20;
  int n;
  Point point[N + 1 << 1];
  Line line[N + 1 << 1];
  bool input() {
    cin >> n; if (! n) return false;
    for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y, point[i + n] = point[i] - Point(0, 1);
    return true;
  }
  void init() {
    for (int i = 1; i < n; ++ i) {
      line[(i << 1) - 1] = Line(point[i], point[i + 1]);
      line[i << 1] = Line(point[i + n], point[i + n + 1]);
    }
  }
  void process() {
    ld ans = -1e18, far;
    for (int i = 1; i <= n; ++ i) {
      for (int j = n + 1; j <= n << 1; ++ j) {
        if (i + n != j) {
          Line tmp = Line(point[i], point[j]);
          if (tmp | Line(point[1], point[1 + n]) || ! cmp((tmp.b - tmp.a) * (point[1] - tmp.b)) || ! cmp((tmp.b - tmp.a) * (point[1 + n] - tmp.b))) {
            far = point[n].x;
            for (int k = 1; k <= n - 1 << 1; ++ k) {
              if (tmp | line[k]) far = min(far, (tmp * line[k]).x);
              if (! cmp((tmp.b - tmp.a) * (line[k].a - tmp.b))) {
                if (k & 1) {
                  if (tmp.ratio() > line[k].ratio()) far = min(far, line[k].a.x);
                } else {
                  if (tmp.ratio() < line[k].ratio()) far = min(far, line[k].a.x);
                }
              }
            }
            if (far == point[n].x) {
              cout << "Through all the pipe." << endl; return;
            }
            ans = max(ans, far);
          }
        }
      }
    }
    cout << setprecision(2) << fixed << ans << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1408

题意:在一个$1 \times 1$的正方形的四条边上分别有$n$个点,从左往右依次将上下两条边上的点连接起来,从下往上依次将左右两条边上的点连接起来。求这些线和正方形所围成的$(n+1)^2$个区域中面积最大的区域的面积。
题解:先把所有交点求出来,然后枚举每一个区域,用叉积求出面积。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Point {
public:
  double x, y;
  Point(double a = 0, double b = 0) : x(a), y(b) {}
  Point operator + (const Point &a) const {
    return Point(x + a.x, y + a.y);
  }
  Point operator - (const Point &a) const {
    return Point(x - a.x, y - a.y);
  }
  Point operator * (const double &a) const {
    return Point(x * a, y * a);
  }
  Point operator / (const double &a) const {
    return Point(x / a, y / a);
  }
  double operator * (const Point &a) const {
    return x * a.y - y * a.x;
  }
  double operator ^ (const Point &a) const {
    return x * a.x + y * a.y;
  }
  double operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
};

struct Line {
public:
  Point a, b;
  Line(Point x = Point(), Point y = Point()) : a(x), b(y) {}
  double operator * (const Line &x) {
    return abs((b - a) * (x.b - x.a));
  }
  Point operator & (const Line &x) {
    double t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 30;
  int n;
  double pos[4][N + 1];
  Point inter[N + 2][N + 2];
  Line r[N + 2], c[N + 2];
  bool input() {
    cin >> n; if (! n) return false;
    for (int i = 1; i <= 4; ++ i)
      for (int j = 1; j <= n; ++ j) cin >> pos[i][j];
    return true;
  }
  void init() {
    r[0] = Line(Point(0, 0), Point(1, 0));
    for (int i = 1; i <= n; ++ i) r[i] = Line(Point(0, pos[3][i]), Point(1, pos[4][i]));
    r[n + 1] = Line(Point(0, 1), Point(1, 1));
    c[0] = Line(Point(0, 0), Point(0, 1));
    for (int i = 1; i <= n; ++ i) c[i] = Line(Point(pos[1][i], 0), Point(pos[2][i], 1));
    c[n + 1] = Line(Point(1, 0), Point(1, 1));
    for (int i = 0; i <= n + 1; ++ i)
      for (int j = 0; j <= n + 1; ++ j)
        inter[i][j] = r[i] & c[j];
  }
  void process() {
    double ans = 0;
    for (int i = 0; i <= n; ++ i)
      for (int j = 0; j <= n; ++ j)
        ans = max(ans, Line(inter[i][j], inter[i][j + 1]) * Line(inter[i][j + 1], inter[i + 1][j + 1]) + Line(inter[i][j], inter[i + 1][j]) * Line(inter[i + 1][j], inter[i + 1][j + 1]));
    cout << setprecision(6) << fixed << ans / 2 << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1584

题意:按顺/逆时针方向给定一个$n$边形的顶点坐标,判断它是否是凸包,若是,则判断给定的圆是否完全在它内部。
题解:因为已经按顺/逆时针方向给定顶点,因此可以直接枚举每一条边,判断下一个点在它的哪一侧(要注意处理共线的情况)。如果全部同侧则是凸包。要判断圆,得先判断圆心是否在凸包内部。显然,如果圆心在凸包内部,那么它和每条边两个端点所构成夹角的和等于$2 \pi$。接着,计算圆心到每条边的距离,如果到某条边的距离小于圆的半径,则圆不完全在凸包内部。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const double EPS = 1e-6;

int cmp(double t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

struct Point {
public:
  double x, y;
  Point(double a = 0, double b = 0) : x(a), y(b) {}
  Point operator + (const Point &a) const {
    return Point(x + a.x, y + a.y);
  }
  Point operator - (const Point &a) const {
    return Point(x - a.x, y - a.y);
  }
  Point operator * (const double &a) const {
    return Point(x * a, y * a);
  }
  Point operator / (const double &a) const {
    return Point(x / a, y / a);
  }
  double operator * (const Point &a) const {
    return x * a.y - y * a.x;
  }
  double operator & (const Point &a) const {
    return x * a.x + y * a.y;
  }
  double operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
  double operator ^ (const Point &a) const {
    return acos(( *this & a) / ( *this % Point() * (a % Point())));
  }
};

struct Line {
  Point a, b;
  Line(Point x = Point(), Point y = Point()) : a(x), b(y) {}
  int operator | (const Point &x) const {
    return cmp((b - a) * (x - b));
  }
  double operator % (const Point &x) const {
    return fabs((a - x) * (b - x) / (a % b));
  }
  double operator ^ (const Point &x) const {
    return (a - x) ^ (b - x);
  }
};

struct Solver {
private:
  static const int N = 100000;
  int n, dire[N + 1];
  double r, sum;
  Point point[N + 1], circle;
  Line line[N + 1];
  bool input() {
    cin >> n; if (n < 3) return false;
    cin >> r >> circle.x >> circle.y;
    for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y;
    for (int i = 1; i < n; ++ i) line[i] = Line(point[i], point[i + 1]);
    line[n] = Line(point[n], point[1]);
    return true;
  }
  void init() {
    sum = 0;
    for (int i = 1; i <= n; ++ i) sum += line[i] ^ circle;
    for (int i = 1; i < n - 1; ++ i) dire[i] = line[i] | point[i + 2];
    dire[n - 1] = line[n - 1] | point[1], dire[n] = line[n] | point[2];
  }
  void process() {
    bool f1 = false, f2 = false;
    for (int i = 1; i <= n; ++ i) {
      if (dire[i] == 1) f1 = true;
      if (dire[i] == -1) f2 = true;
    }
    if (f1 && f2) {
      cout << "HOLE IS ILL-FORMED" << endl; return;
    }
    if (! ~ cmp(sum - 2 * acos(-1))) {
      cout << "PEG WILL NOT FIT" << endl; return;
    }
    for (int i = 1; i <= n; ++ i) {
      if (! ~ cmp(line[i] % circle - r)) {
        cout << "PEG WILL NOT FIT" << endl; return;
      }
    }
    cout << "PEG WILL FIT" << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1026

题意:给定一个$n$的置换,求一个字符串$s$经过$k$次置换后得到的字符串。
题解:找出置换中的每个循环节,即可直接求出新字符串每一位对应原字符串的哪一位。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 200;
  int n, a[N + 1], top, num[N + 1][N + 1], belong[N + 1], pos[N + 1];
  bool vis[N + 1];
  bool input() {
    cin >> n; if (! n) return false;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    return true;
  }
  void init() {
    top = 0;
    memset(num, 0, sizeof num);
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= n; ++ i) {
      if (! vis[i]) {
        int t = i; ++ top;
        while (! vis[t]) {
          vis[t] = true;
          num[top][++ num[top][0]] = t;
          belong[t] = top;
          pos[t] = num[top][0];
          t = a[t];
        }
      }
    }
  }
  bool process() {
    int k; cin >> k;
    if (! k) return false;
    string s; getline(cin, s);
    int len = s.length() - 1;
    while (len < n) {
      s += " ", ++ len;
    }
    string ans = "";
    for (int i = 1; i <= len; ++ i) {
      int t = belong[i];
      ans += s[num[t][(pos[i] - k % num[t][0] + num[t][0] - 1) % num[t][0] + 1]];
    }
    cout << ans << endl;
    return true;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(); while (process()) ; return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) cout << endl;
  return 0;
}

POJ1054

题意:青蛙经过农田时的痕迹是一条直线。农田里的植物就在这个农田的二维坐标系的整数格点上。如果某只青蛙经过农田,也就是某条直线穿过农田,那么那条直线经过的所有的整数格点上的植物会都会被破坏掉。现在给出所有被破坏的植物的位置,问哪只青蛙破坏的最多。
题解:暴力枚举每两个点所构成的直线,直接计算直线上有几个整点。由于很多点对会重复计算,所以可以剪枝,降低复杂度。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 5000;
  static const int MOD = 8000009;
  int r, c, n;
  bool vis[N + 1][N + 1];
  struct Point {
    int x, y;
    bool operator < (const Point &a) const {
      return y == a.y ? x < a.x : y < a.y;
    }
  };
  Point point[N + 1];
  void input() {
    cin >> r >> c >> n;
    for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y, vis[point[i].x][point[i].y] = true;
  }
  void init() {
    sort(point + 1, point + n + 1);
    int ans = 0;
    for (int i = 1; i < n; ++ i) {
      for (int j = i + 1; j <= n; ++ j) {
        Point s = point[i], t = point[j];
        int dx = t.x - s.x, dy = t.y - s.y, tx = t.x + dx, ty = t.y + dy;
        if (s.x - dx > 0 && s.x - dx <= r && s.y - dy > 0 && s.y - dy <= c) continue;
        int cnt = 0;
        while (tx > 0 && tx <= r && ty > 0 && ty <= c) {
          if (vis[tx][ty]) ++ cnt;
          else { cnt = 0; break; }
          tx += dx, ty += dy;
        }
        ans = max(ans, cnt);
      }
    }
    if (ans) cout << ans + 2 << endl;
    else cout << 0 << endl;
  }

public:
  void solve() {
    input(), init();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1066

题意:有一个$100 \times 100$的正方形,内部有$n$条线,每条线的两个端点位于正方形两条不同的边上。给定正方形内部的一个点$p$,求它最少穿过多少条线能到达正方形外部。
题解:由于所有线的端点都在正方形的边上,所以从点$p$到正方形边上任意一点穿过线的最少数目就等于从点$p$到那个点的线段穿过线的数目。因此可以直接枚举每条线的端点,计算它和$p$点所构成的线段穿过了多少条线,取最小值加一就是最后答案。要注意$n$等于$0$时答案是$1$。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const double EPS = 1e-6;

int cmp(double t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

bool between(double a, double b, double c) {
  return cmp(a - min(b, c)) == 1 && cmp(max(b, c) - a) == 1;
}

struct Point {
public:
  double x, y;
  Point(double a = 0, double b = 0) : x(a), y(b) {}
  Point operator + (const Point &a) const {
    return Point(x + a.x, y + a.y);
  }
  Point operator - (const Point &a) const {
    return Point(x - a.x, y - a.y);
  }
  Point operator * (const double &a) const {
    return Point(x * a, y * a);
  }
  Point operator / (const double &a) const {
    return Point(x / a, y / a);
  }
  double operator * (const Point &a) const {
    return x * a.y - y * a.x;
  }
  double operator & (const Point &a) const {
    return x * a.x + y * a.y;
  }
  double operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
};

struct Line {
public:
  Point a, b;
  Line(Point x = Point(), Point y = Point()) : a(x), b(y) {}
  int operator | (const Line &x) const {
    return cmp((b - a) * (x.b - x.a));
  }
  Point operator & (const Line &x) const {
    double t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 30;
  int n;
  Point point[N + 1 << 1], p;
  Line line[N + 1];
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> point[(i << 1) - 1].x >> point[(i << 1) - 1].y >> point[i << 1].x >> point[i << 1].y;
      line[i] = Line(point[(i << 1) - 1], point[i << 1]);
    }
    cin >> p.x >> p.y;
  }
  void process() {
    if (n == 0) {
      cout << "Number of doors = " << 1 << endl;
      return;
    }
    int ans = 1000;
    for (int i = 1; i <= n << 1; ++ i) {
      Line tmp(p, point[i]);
      int cnt = 0;
      for (int j = 1; j <= n; ++ j) {
        if (! (tmp | line[j])) continue;
        Point inter = tmp & line[j];
        if ((between(inter.x, tmp.a.x, tmp.b.x) || between(inter.y, tmp.a.y, tmp.b.y)) && (between(inter.x, line[j].a.x, line[j].b.x) || between(inter.y, line[j].a.y, line[j].b.y))) ++ cnt;
      }
      ans = min(ans, cnt);
    }
    cout << "Number of doors = " << ans + 1 << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1095

题意:将二叉树按以下要求标号:①空节点为标号为$0$;②一个节点标号为$1$;③节点少的树比节点多的树的标号小;④节点相同的情况下,左子树标号较小的树标号较小;⑤节点相同且左子树标号相同的情况下,右子树标号较小的树标号较小。按格式输出第$n$棵树的形状。
题解:由$n$个节点构成的二叉树的数量满足卡特兰数。我们可以先求出这棵树由几个节点构成,以及这棵树在节点数和它相同的树中的排名。这样,就可以对左右子树递归处理。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int c[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190};

struct Solver {
private:
  static const int N = 100000;
  int n;
  bool input() {
    cin >> n; return n;
  }
  void process(int t, int node) {
    if (node == 1) {
      cout << 'X'; return;
    }
    int tmp = t, i;
    for (i = 0; i < 20; ++ i) {
      if (tmp <= c[i] * c[node - 1 - i]) break;
      tmp -= c[i] * c[node - 1 - i];
    }
    if (i) cout << '(', process((tmp - 1) / c[node - 1 - i] + 1, i), cout << ')';
    cout << 'X';
    if (node - 1 - i) cout << '(', process((tmp - 1) % c[node - 1 - i] + 1, node - 1 - i), cout << ')';
  }

public:
  bool solve() {
    if (! input()) return false;
    int tmp = n, i;
    for (i = 1; i < 20; ++ i) {
      if (tmp <= c[i]) break; tmp -= c[i];
    }
    process(tmp, i), cout << endl;
    return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1113

题意:要用尽量短的线将给定的$N$个点围起来,并且线上任意一点到每个点的距离不小于$L$,求线的长度。
题解:用尽量短的线将点围起来,显然是要求凸包。然而还要求到每个点的距离不小于$L$,可以将凸包上的每一条线段沿法线方向向外平移$L$,再用半径为$L$的圆弧将线段连起来。易知所有圆弧加起来刚好是一个圆。因此先求出凸包周长,再加上半径为$L$的圆的周长,就是最后答案。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const double EPS = 1e-6;

int cmp(double t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

struct Point {
public:
  double x, y;
  Point(double a = 0, double b = 0) : x(a), y(b) {}
  bool operator < (const Point &a) const {
    return x == a.x ? y < a.y : x < a.x;
  }
  Point operator - (const Point &a) const {
    return Point(x - a.x, y - a.y);
  }
  double operator * (const Point &a) const {
    return x * a.y - y * a.x;
  }
  double operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
};

struct Line {
public:
  Point a, b;
  Line(Point x = Point(), Point y = Point()) : a(x), b(y) {}
  int operator | (const Point &x) const {
    return cmp((b - a) * (x - b));
  }
};

struct Solver {
private:
  static const int N = 1000;
  int n, l, s[N + 1], res[N + 1];
  Point point[N + 1];
  void input() {
    cin >> n >> l;
    for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y;
  }
  void init() {
    sort(point + 1, point + n + 1);
    s[1] = 1;
    for (int i = 2; i <= n; ++ i)
      if (point[i].x > point[1].x) {
        s[s[0] = 2] = i; break;
      }
    for (int i = s[s[0]] + 1; i <= n; ++ i) {
      while (s[0] > 1 && (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) < 1) -- s[0];
      if (s[0] == 1 || (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) > -1) s[++ s[0]] = i;
    }
    for (int i = 1; i <= s[0]; ++ i) res[++ res[0]] = s[i];
    for (int i = n - 1; i; -- i)
      if (point[i].x < point[n].x) {
        s[1] = i + 1, s[s[0] = 2] = i; break;
      }
    for (int i = s[s[0]] - 1; i; -- i) {
      while (s[0] > 1 && (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) < 1) -- s[0];
      if (s[0] == 1 || (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) > -1) s[++ s[0]] = i;
    }
    for (int i = 2; i < s[0]; ++ i) res[++ res[0]] = s[i];
  }
  void process() {
    double ans = 0;
    for (int i = 1; i < res[0]; ++ i) ans += point[res[i]] % point[res[i + 1]];
    ans += point[res[res[0]]] % point[res[1]];
    cout << (int) (ans + 2 * acos(-1) * l + 0.5) << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1151

题意:给定平面直角坐标系内的$n$个矩形,求它们覆盖的面积。矩形顶点坐标不一定是整数。
题解:先将矩形离散化,接着用扫描线+线段树的方法求矩形面积并——从左往右扫描坐标系,扫到一个矩形的左边界时将它加入线段树,扫到一个矩形的右边界时将它从线段树中删除。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int N = 100;
double xmap[N + 1 << 1], ymap[N + 1 << 1];

struct Point {
  int id, nx, ny;
  double x, y;
};

struct Line {
  int x, y1, y2, val;
  bool operator < (const Line &a) const { return x == a.x ? val > a.val : x < a.x; }
};

bool cmpx(Point a, Point b) { return a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct SegmentTree {
private:
  static const int N = 1000;
  int tot;
  struct Node {
    int l, r, child[2], val;
    double sum;
  } node[N];
  void build_tree(int root) {
    node[root].child[0] = node[root].child[1] = node[root].sum = 0;
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[++ tot].l = node[root].l, node[tot].r = mid;
    node[root].child[0] = tot, build_tree(tot);
    node[++ tot].l = mid + 1, node[tot].r = node[root].r;
    node[root].child[1] = tot, build_tree(tot);
  }
  void update(int root) {
    if (node[root].l == node[root].r) return;
    if (node[root].val) node[root].sum = ymap[node[root].r + 1] - ymap[node[root].l];
    else node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
  }
  void insert_line(int root, int l, int r, int val) {
    if (node[root].l > r || node[root].r < l) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].val += val;
      if (node[root].val) node[root].sum = ymap[node[root].r + 1] - ymap[node[root].l];
      else node[root].sum = 0;
      update(root);
      return;
    }
    insert_line(node[root].child[0], l, r, val);
    insert_line(node[root].child[1], l, r, val);
    update(root);
  }

public:
  void init(int n) {
    node[node[tot = 1].l = 1].r = n, build_tree(1);
  }
  void add(int l, int r, int val) {
    insert_line(1, l, r - 1, val);
  }
  double get() {
    return node[1].sum;
  }
};

struct Solver {
private:
  static const int N = 100;
  int n, cas;
  Point point[N + 1 << 1];
  Line line[N + 1 << 1];
  SegmentTree tree;
  bool input() {
    cin >> n; if (! n) return false;
    for (int i = 1; i <= n; ++ i) {
      cin >> point[(i << 1) - 1].x >> point[(i << 1) - 1].y >> point[i << 1].x >> point[i << 1].y;
      point[(i << 1) - 1].id = (i << 1) - 1, point[i << 1].id = i << 1;
    }
    return true;
  }
  void init() {
    sort(point + 1, point + (n << 1) + 1, cmpx);
    point[1].nx = 1, xmap[1] = point[1].x;
    for (int i = 2; i <= n << 1; ++ i) {
      if (point[i].x == point[i - 1].x) point[i].nx = point[i - 1].nx;
      else point[i].nx = point[i - 1].nx + 1, xmap[point[i].nx] = point[i].x;
    }
    sort(point + 1, point + (n << 1) + 1, cmpy);
    point[1].ny = 1, ymap[1] = point[1].y;
    for (int i = 2; i <= n << 1; ++ i) {
      if (point[i].y == point[i - 1].y) point[i].ny = point[i - 1].ny;
      else point[i].ny = point[i - 1].ny + 1, ymap[point[i].ny] = point[i].y;
    }
    sort(point + 1, point + (n << 1) + 1, cmpi);
    for (int i = 1; i <= n; ++ i) {
      line[(i << 1) - 1].x = point[(i << 1) - 1].nx;
      line[(i << 1) - 1].y1 = point[(i << 1) - 1].ny;
      line[(i << 1) - 1].y2 = point[i << 1].ny;
      line[(i << 1) - 1].val = 1;
      line[i << 1].x = point[i << 1].nx;
      line[i << 1].y1 = point[(i << 1) - 1].ny;
      line[i << 1].y2 = point[i << 1].ny;
      line[i << 1].val = -1;
    }
    sort(line + 1, line + (n << 1) + 1);
    tree.init(n << 1);
  }
  void process() {
    int t; double ans = 0;
    for (int i = 1; i <= n << 1; ++ i) {
      if (line[i].x == line[1].x) tree.add(line[i].y1, line[i].y2, line[i].val);
      else { t = i; break; }
    }
    while (t <= n << 1) {
      ans += tree.get() * (xmap[line[t].x] - xmap[line[t - 1].x]);
      int xx = line[t].x;
      while (t <= n << 1 && line[t].x == xx)
        tree.add(line[t].y1, line[t].y2, line[t].val), ++ t;
    }
    cout << "Total explored area: " << setprecision(2) << fixed << ans << endl << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    cout << "Test case #" << ++ cas << endl;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1166

题意:有$9$个钟,排成三行三列。每个钟只会指向0、3、6、9点。现要求所有钟指向0点,每次只能顺时针旋转一次规定组合的钟:1245、2356、4578、5689、123、789、147、369、24568,求最少需要旋转几次,并输出方案。
题解:可以发现每种组合最多旋转$3$次,因此可以$4^9$枚举每种组合旋转了几次,判断是否满足要求,同时保存答案。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 9;
  int a[N + 1], b[N + 1], tot, ans[N + 1];
  void input() {
    for (int i = 1; i <= 9; ++ i) cin >> a[i];
  }
  void process() {
    tot = 1e9;
    for (int i1 = 0; i1 < 4; ++ i1)
      for (int i2 = 0; i2 < 4; ++ i2)
        for (int i3 = 0; i3 < 4; ++ i3)
          for (int i4 = 0; i4 < 4; ++ i4)
            for (int i5 = 0; i5 < 4; ++ i5)
              for (int i6 = 0; i6 < 4; ++ i6)
                for (int i7 = 0; i7 < 4; ++ i7)
                  for (int i8 = 0; i8 < 4; ++ i8)
                    for (int i9 = 0; i9 < 4; ++ i9) {
                      if (i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 >= tot) continue;
                      for (int i = 1; i <= 9; ++ i) b[i] = a[i];
                      b[1] += i1 + i2 + i4;
                      b[2] += i1 + i2 + i3 + i5;
                      b[3] += i2 + i3 + i6;
                      b[4] += i1 + i4 + i5 + i7;
                      b[5] += i1 + i3 + i5 + i7 + i9;
                      b[6] += i3 + i5 + i6 + i9;
                      b[7] += i4 + i7 + i8;
                      b[8] += i5 + i7 + i8 + i9;
                      b[9] += i6 + i8 + i9;
                      bool flag = true;
                      for (int i = 1; i <= 9; ++ i) if (b[i] % 4) flag = false;
                      if (flag && i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 < tot) {
                        tot = i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9;
                        ans[1] = i1, ans[2] = i2, ans[3] = i3, ans[4] = i4, ans[5] = i5;
                        ans[6] = i6, ans[7] = i7, ans[8] = i8, ans[9] = i9;
                      }
                    }
    for (int i = 1; i <= 9; ++ i)
      for (int j = 1; j <= ans[i]; ++ j) cout << i << ' ';
    cout << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2127

题意:求两个序列$s_1, s_2$的最长公共上升子序列。
题解:令$f_{i, j}$表示$s_1$的前$i$个数和$s_2$的前$j$个数的最长公共上升子序列长度,并且$s_1$的第$i$个和$s_2$的第$j$个匹配。显然,只有$s_{1, i}=s_{2, j}$时,$f_{i, j}$才有意义。转移方程:$f_{i, j}=max(f_{i’, j’} | i’ \lt i, j’ \lt j, s_{2, j’} \lt s_{2, j}) + 1$。令$g_{j’}=max(f_{i’, j’})$,则转移方程变为:$f_{i, j}=max(g_{j’} | j’ \lt j, s_{2, j’} \lt s_{1, i}) + 1$。这就可以从小到大枚举$i$,再从小到大枚举$j$,同时更新$g$。由于最后要输出序列,所以还需要一个$pre$数组来记录前一项。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 500;
  int n, m, a[N + 1], b[N + 1], g[N + 1], pre[N + 1][N + 1];
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++ i) cin >> b[i];
  }
  void print(int i, int j) {
    if (! i || ! j) return;
    while (pre[i][j] == j) -- i;
    print(i - 1, pre[i][j]);
    cout << b[j] << ' ';
  }
  void process() {
    for (int i = 1; i <= n; ++ i) {
      int ma = 0, p = 0;
      for (int j = 1; j <= m; ++ j) {
        pre[i][j] = j;
        if (b[j] < a[i] && g[j] > ma) ma = g[j], p = j;
        else if (b[j] == a[i] && ma + 1 > g[j]) g[j] = ma + 1, pre[i][j] = p;
      }
    }
    int ans = 0, p = 0;
    for (int i = 1; i <= m; ++ i)
      if (g[i] > ans) ans = g[i], p = i;
    cout << ans << endl;
    print(n, p), cout << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1177

题意:给定平面直角坐标系内的$n$个矩形,求它们覆盖区域的周长。
题解:扫描线+线段树,横着一次竖着一次。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Line {
  int x, y1, y2, val;
  bool operator < (const Line &a) const { return x < a.x; }
};

struct SegmentTree {
private:
  static const int N = 30000;
  int tot;
  struct Node {
    int l, r, child[2], val, sum;
  } node[N << 1];
  void build_tree(int root) {
    node[root].child[0] = node[root].child[1] = node[root].val = node[root].sum = 0;
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[++ tot].l = node[root].l, node[tot].r = mid;
    node[root].child[0] = tot, build_tree(tot);
    node[++ tot].l = mid + 1, node[tot].r = node[root].r;
    node[root].child[1] = tot, build_tree(tot);
  }
  void update(int root) {
    if (node[root].l == node[root].r) return;
    if (node[root].val) node[root].sum = node[root].r - node[root].l + 1;
    else node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
  }

void insert_line(int root, int l, int r, int val) {
    if (node[root].r < l || node[root].l > r) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].val += val;
      if (node[root].val) node[root].sum = node[root].r - node[root].l + 1;
      else node[root].sum = 0, update(root);
      return;
    }
    insert_line(node[root].child[0], l, r, val);
    insert_line(node[root].child[1], l, r, val);
    update(root);
  }

public:
  void init(int t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  void add(int l, int r, int val) {
    insert_line(1, l, r - 1, val);
  }
  int sum() {
    return node[1].sum;
  }
};

struct Solver {
private:
  static const int N = 5000;
  int n;
  pair<int, int> point[N << 1];
  Line line[N << 1];
  SegmentTree tree;
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> point[(i << 1) - 1].first >> point[(i << 1) - 1].second;
      point[(i << 1) - 1].first += 10001, point[(i << 1) - 1].second += 10001;
      cin >> point[i << 1].first >> point[i << 1].second;
      point[i << 1].first += 10001, point[i << 1].second += 10001;
    }
  }
  void process() {
    int ans = 0, last = 0;
    tree.init(20001);
    for (int i = 1; i <= n; ++ i) {
      line[(i << 1) - 1].x = point[(i << 1) - 1].first;
      line[(i << 1) - 1].y1 = point[(i << 1) - 1].second;
      line[(i << 1) - 1].y2 = point[i << 1].second;
      line[(i << 1) - 1].val = 1;
      line[i << 1].x = point[i << 1].first;
      line[i << 1].y1 = point[(i << 1) - 1].second;
      line[i << 1].y2 = point[i << 1].second;
      line[i << 1].val = -1;
    }
    sort(line + 1, line + (n << 1) + 1);
    for (int i = 1; i <= n << 1; ++ i) {
      tree.add(line[i].y1, line[i].y2, line[i].val);
      int sum = tree.sum();
      ans += abs(last - sum);
      last = sum;
    }
    last = 0;
    tree.init(20001);
    for (int i = 1; i <= n; ++ i) {
      line[(i << 1) - 1].x = point[(i << 1) - 1].second;
      line[(i << 1) - 1].y1 = point[(i << 1) - 1].first;
      line[(i << 1) - 1].y2 = point[i << 1].first;
      line[(i << 1) - 1].val = 1;
      line[i << 1].x = point[i << 1].second;
      line[i << 1].y1 = point[(i << 1) - 1].first;
      line[i << 1].y2 = point[i << 1].first;
      line[i << 1].val = -1;
    }
    sort(line + 1, line + (n << 1) + 1);
    for (int i = 1; i <= n << 1; ++ i) {
      tree.add(line[i].y1, line[i].y2, line[i].val);
      int sum = tree.sum();
      ans += abs(last - sum);
      last = sum;
    }
    cout << ans << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1191

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Solver {
private:
  static const int N = 8;
  int n, a[N + 1][N + 1], sum[N + 1][N + 1];
  double ans, avg, now, rec[N + 1];
  void input() {
    cin >> n;
    for (int i = 1; i <= N; ++ i)
      for (int j = 1; j <= N; ++ j) cin >> a[i][j];
  }
  void init() {
    ans = 1e9;
    for (int i = 1; i <= N; ++ i)
      for (int j = 1; j <= N; ++ j) sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
    avg = 1.0 * sum[N][N] / n;
  }
  double get_sum(int i1, int j1, int i2, int j2) {
    int s = sum[i2][j2] - sum[i1 - 1][j2] - sum[i2][j1 - 1] + sum[i1 - 1][j1 - 1];
    return (s - avg) * (s - avg);
  }
  void process(int i1, int j1, int i2, int j2, int t) {
    if (now >= ans) return;
    if (i2 - i1 + j2 - j1 < n - t + 1) return;
    if (t == n) { rec[t] = get_sum(i1, j1, i2, j2), now += rec[t], ans = min(ans, now), now -= rec[t]; return; }
    for (int i = i1; i < i2; ++ i) {
      rec[t] = get_sum(i1, j1, i, j2), now += rec[t];
      process(i + 1, j1, i2, j2, t + 1);
      now -= rec[t], rec[t] = get_sum(i + 1, j1, i2, j2), now += rec[t];
      process(i1, j1, i, j2, t + 1);
      now -= rec[t];
    }
    for (int j = j1; j < j2; ++ j) {
      rec[t] = get_sum(i1, j1, i2, j), now += rec[t];
      process(i1, j + 1, i2, j2, t + 1);
      now -= rec[t], rec[t] = get_sum(i1, j + 1, i2, j2), now += rec[t];
      process(i1, j1, i2, j, t + 1);
      now -= rec[t];
    }
  }

public:
  void solve() {
    input(), init(), process(1, 1, 8, 8, 1);
    cout << setprecision(3) << fixed << sqrt(ans / n) << endl;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1195

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct BinaryIndexedTree {
private:
  static const int N = 1024;
  int a[N + 1][N + 1];
  void add_row(int x, int y, int val) {
    for (int i = y; i <= N; i += i & -i) a[x][i] += val;
  }
  int sum_row(int x, int y) {
    int ret = 0;
    for (int i = y; i; i -= i & -i) ret += a[x][i];
    return ret;
  }

public:
  void add(int x, int y, int val) {
    for (int i = x; i <= N; i += i & -i) add_row(i, y, val);
  }
  int sum(int x, int y) {
    int ret = 0;
    for (int i = x; i; i -= i & -i) ret += sum_row(i, y);
    return ret;
  }
};

struct Solver {
private:
  static const int N = 1024;
  int n;
  BinaryIndexedTree tree;
  bool process() {
    int o; cin >> o;
    if (o == 3) return false;
    if (! o) cin >> n;
    if (o == 1) {
      int x, y, a;
      cin >> x >> y >> a;
      ++ x, ++ y;
      tree.add(x, y, a);
    }
    if (o == 2) {
      int l, b, r, t;
      cin >> l >> b >> r >> t;
      ++ l, ++ b, ++ r, ++ t;
      cout << tree.sum(r, t) - tree.sum(l - 1, t) - tree.sum(r, b - 1) + tree.sum(l - 1, b - 1) << endl;
    }
    return true;
  }

public:
  void solve() {
    while (process()) ;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1201

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 50000;
  int n, nume, h[N + 2], que[N << 4], dist[N + 2];
  bool in[N + 2];
  struct Edge {
    int v, c, nxt;
  } e[N << 2];
  void add_edge(int u, int v, int c) {
    e[++ nume].v = v, e[nume].c = c;
    e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      int a, b, c;
      cin >> a >> b >> c;
      ++ a, ++ b;
      add_edge(a - 1, b , -c);
    }
    for (int i = 1; i <= N + 1; ++ i) {
      add_edge(i - 1, i, 0);
      add_edge(i, i - 1, 1);
    }
    memset(dist, 0x1f, sizeof dist);
  }
  void process() {
    int s = 0, t = 1;
    que[1] = 0, dist[0] = 0, in[0] = true;
    while (s < t) {
      int u = que[++ s]; in[u] = false;
      for (int i = h[u]; i; i = e[i].nxt) {
        if (dist[u] + e[i].c < dist[e[i].v]) {
          dist[e[i].v] = dist[u] + e[i].c;
          if (! in[e[i].v]) que[++ t] = e[i].v, in[e[i].v] = true;
        }
      }
    }
    cout << - dist[N + 1] << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1222

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 10;
  int a[N + 1][N + 1], b[N + 1][N + 1], ans[N + 1][N + 1];
  void input() {
    for (int i = 1; i < 6; ++ i)
      for (int j = 1; j <= 6; ++ j) cin >> a[i][j];
  }
  void modify(int x, int y) {
    b[x][y] = ! b[x][y];
    b[x - 1][y] = ! b[x - 1][y];
    b[x][y - 1] = ! b[x][y - 1];
    b[x + 1][y] = ! b[x + 1][y];
    b[x][y + 1] = ! b[x][y + 1];
  }
  void process() {
    for (int f = 0; f < 1 << 6; ++ f) {
      for (int i = 1; i < 6; ++ i)
        for (int j = 1; j <= 6; ++ j) b[i][j] = a[i][j];
      memset(ans, 0, sizeof ans);
      for (int i = 1; i <= 6; ++ i) {
        ans[1][i] = f & (1 << (i - 1));
        if (ans[1][i]) modify(1, i);
      }
      for (int i = 2; i < 6; ++ i)
        for (int j = 1; j <= 6; ++ j)
          if (b[i - 1][j]) ans[i][j] = 1, modify(i, j);
      bool flag = true;
      for (int i = 1; i <= 6; ++ i)
        if (b[5][i]) flag = false;
      if (flag) {
        for (int i = 1; i < 6; ++ i) {
          for (int j = 1; j <= 6; ++ j) cout << (ans[i][j] > 0) << ' ';
          cout << endl;
        }
        return;
      }
    }
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  int T; cin >> T;
  for (int i = 1; i <= T; ++ i) cout << "PUZZLE #" << i << endl, solver.solve();
  return 0;
}

POJ1286

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  long long n;
  bool input() {
    cin >> n;
    return ~ n;
  }
  long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
  }
  long long power(long long a, long long b) {
    long long ret = 1;
    while (b) {
      if (b & 1) ret *= a;
      a *= a, b >>= 1;
    }
    return ret;
  }
  void process() {
    if (! n) { cout << 0 << endl; return; }
    long long ans = 0;
    for (int i = 0; i < n; ++ i) ans += power(3, gcd(i, n));
    if (n & 1) ans += n * power(3, n + 1 >> 1);
    else ans += (n >> 1) * power(3, n >> 1) + (n >> 1) * power(3, (n >> 1) + 1);
    cout << ans / (n << 1) << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ1691

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Rectangle {
  int x1, y1, x2, y2, col;
};

struct Solver {
private:
  static const int N = 15;
  int n, ans, nume, h[N + 1], in[N + 1];
  bool vis[N + 1];
  Rectangle a[N + 1];
  struct Edge {
    int v, nxt;
  } e[N * N];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
      cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].col;
  }
  bool has_inter(int a, int b, int c, int d) {
    if (a > c) swap(a, c), swap(b, d);
    return c >= a && c < b;
  }
  void init() {
    ans = 1e9, nume = 0;
    memset(h, 0, sizeof h);
    memset(in, 0, sizeof in);
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j)
        if (a[i].x2 == a[j].x1 && has_inter(a[i].y1, a[i].y2, a[j].y1, a[j].y2))
          add_edge(i, j), ++ in[j];
  }
  void process(int t, int tot, int col, int cnt) {
    if (tot == n) {
      ans = min(ans, cnt);
      return;
    }
    vis[t] = true;
    for (int i = h[t]; i; i = e[i].nxt) -- in[e[i].v];
    for (int i = 1; i <= n; ++ i) {
      if (! vis[i] && ! in[i]) process(i, tot + 1, a[i].col, cnt + (col != a[i].col));
    }
    for (int i = h[t]; i; i = e[i].nxt) ++ in[e[i].v];
    vis[t] = false;
  }

public:
  void solve() {
    input(), init();
    for (int i = 1; i <= n; ++ i) if (! in[i]) process(i, 1, a[i].col, 1);
    cout << ans << endl;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  int T; cin >> T;
  while (T --) solver.solve();
  return 0;
}

POJ1703

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 100000;
  int n, m, fa[N + 1], dist[N + 1];
  void input() {
    scanf("%d%d", &n, &m);
  }
  void init() {
    for (int i = 1; i <= n; ++ i) fa[i] = i, dist[i] = 0;
  }
  int get_fa(int t) {
    if (t == fa[t]) return t;
    int ret = get_fa(fa[t]);
    (dist[t] += dist[fa[t]]) &= 1;
    return fa[t] = ret;
  }
  void process() {
    int a, b; char c = ' ';
    while (c != 'A' && c != 'D') scanf("%c", &c);
    scanf("%d%d", &a, &b);
    int p = get_fa(a), q = get_fa(b);
    if (c == 'A') {
      if (p != q) printf("Not sure yet.\n");
      else if (dist[a] != dist[b]) printf("In different gangs.\n");
      else printf("In the same gang.\n");
    } else fa[p] = q, dist[p] = dist[a] + dist[b] + 1 & 1;
  }

public:
  void solve() {
    input(), init();
    while (m --) process();
  }
} solver;

int main() {
  int T; cin >> T;
  while (T --) solver.solve();
  return 0;
}

POJ1724

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 100;
  int k, n, r, nume, ans, h[N + 1];
  bool vis[N + 1];
  struct Edge {
    int v, l, t, nxt;
  } e[N * N + 1];
  void add_edge(int u, int v, int l, int t) {
    e[++ nume].v = v, e[nume].l = l, e[nume].t = t;
    e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    cin >> k >> n >> r;
    for (int i = 1; i <= r; ++ i) {
      int u, v, l, t;
      cin >> u >> v >> l >> t;
      add_edge(u, v, l, t);
    }
  }
  void init() { ans = 1e9; }
  void dfs(int u, int l, int t) {
    if (t < 0 || l >= ans) return;
    if (u == n) { ans = l; return; }
    vis[u] = true;
    for (int i = h[u]; i; i = e[i].nxt) {
      if (! vis[e[i].v]) dfs(e[i].v, l + e[i].l, t - e[i].t);
    }
    vis[u] = false;
  }

public:
  void solve() {
    input(), init(), dfs(1, 0, k);
    cout << ans << endl;
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ1819

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const double EPS = 1e-6;

int cmp(double t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

struct Solver {
private:
  static const int N = 1000;
  int n, top, sta[N + 1], tot, ans[N + 1];
  double r[N + 1], dist[N + 1];
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> r[i];
  }
  void init() {
    dist[1] = r[1], sta[top = 1] = 1;
    for (int i = 2; i <= n; ++ i) {
      dist[i] = r[i];
      for (int j = 1; j < i; ++ j)
        dist[i] = max(dist[i], dist[j] + sqrt((r[i] + r[j]) * (r[i] + r[j]) - (r[i] - r[j]) * (r[i] - r[j])));
      if (dist[i] == r[i]) sta[top = 1] = i;
      else for (int j = 1; j <= top; ++ j)
        if (! cmp(dist[i] - dist[sta[j]] - sqrt((r[i] + r[sta[j]]) * (r[i] + r[sta[j]]) - (r[i] - r[sta[j]]) * (r[i] - r[sta[j]])))) {
          sta[top = j + 1] = i; break;
        }
    }
  }
  void process() {
    int p = 0;
    double far = 0;
    for (int i = 1; i <= n; ++ i) far = max(far, dist[i] + r[i]);
    for (int i = 1; i <= n; ++ i) if (! cmp(far - dist[i] - r[i])) { p = i; break; }
    while (sta[top] > p) -- top;
    int pos = 1;
    for (int i = 1; i <= n; ++ i)
      if (i <= p && i == sta[pos]) ++ pos; else ans[++ tot] = i;
    cout << tot << endl;
    for (int i = 1; i <= tot; ++ i) cout << ans[i] << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1870

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 10000;
  int a, b;
  pair <int, int> point[N << 1];
  bool input() {
    cin >> a >> b;
    return a || b;
  }
  void process() {
    int x = point[a].first - point[b].first, y = point[a].second - point[b].second;
    if (x <= 0 && y >= 0 || x >= 0 && y <= 0) cout << abs(x) + abs(y); else cout << max(abs(x), abs(y));
  }

public:
  void init() {
    point[1] = make_pair(0, 0);
    int t = 2, cnt = 1;
    while (t <= 10000) {
      point[t] = make_pair(point[t - 1].first, point[t - 1].second - 1), ++ t;
      for (int i = 1; i < cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first - 1, point[t - 1].second - 1);
      for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first - 1, point[t - 1].second);
      for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first, point[t - 1].second + 1);
      for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first + 1, point[t - 1].second + 1);
      for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first + 1, point[t - 1].second);
      for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first, point[t - 1].second - 1);
      ++ cnt;
    }
  }
  bool solve() {
    if (! input()) return false;
    cout << "The distance between cells " << a << " and " << b << " is ";
    process(), cout << "." << endl; return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.init();
  while (solver.solve()) ;
  return 0;
}

POJ1925

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Point {
  long long x, y;
};

struct Solver {
private:
  static const long long N = 5000;
  static const long long M = 1000000;
  long long n, f[M + 1];
  Point point[N + 1];
  void input() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lld%lld", &point[i].x, &point[i].y);
  }
  void process() {
    memset(f, 0x1f, sizeof f);
    f[point[1].x] = 0;
    for (int i = 2; i <= n; ++ i) {
      int len = sqrt(point[i].y * point[i].y - (point[i].y - point[1].y) * (point[i].y - point[1].y));
      for (int j = max(point[1].x, point[i].x - len); j < point[i].x; ++ j) {
        int k = min(point[n].x, (point[i].x << 1) - j);
        f[k] = min(f[k], f[j] + 1);
      }
    }
    if (f[point[n].x] > 5000) printf("-1\n");
    else printf("%lld\n", f[point[n].x]);
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  int T; scanf("%d", &T);
  while (T --) solver.solve();
  return 0;
}

POJ1947

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 150;
  int n, m, nume, h[N + 1], size[N + 1], f[N + 1][N + 1];
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    cin >> n >> m;
    for (int i = 1; i < n; ++ i) {
      int u, v; cin >> u >> v;
      add_edge(u, v);
    }
  }
  void dfs(int t) {
    int cnt = 0; size[t] = 1;
    for (int i = h[t]; i; i = e[i].nxt, ++ cnt) {
      dfs(e[i].v);
      size[t] += size[e[i].v];
    }
    f[t][1] = cnt;
    for (int i = h[t]; i; i = e[i].nxt) {
      for (int j = size[t]; j; -- j)
        for (int k = 1; k < j; ++ k)
          f[t][j] = min(f[t][j], f[t][j - k] + f[e[i].v][k] - 1);
    }
  }
  void init() {
    memset(f, 0x1f, sizeof f), dfs(1);
  }
  void process() {
    int ans = f[1][m];
    for (int i = 2; i <= n; ++ i) ans = min(ans, f[i][m] + 1);
    cout << ans << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ1961

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 1000000;
  int T, n, nxt[N + 1];
  string s;
  bool input() {
    cin >> n; if (! n) return false;
    cin >> s; return true;
  }
  void init() {
    nxt[0] = nxt[1] = 0;
    int k = 0;
    for (int i = 2; i <= n; ++ i) {
      for (; k && s[k] != s[i - 1]; k = nxt[k]) ;
      if (s[k] == s[i - 1]) ++ k; nxt[i] = k;
    }
  }
  void process() {
    for (int i = 1; i <= n; ++ i) {
      if (! (i % (i - nxt[i])) && i / (i - nxt[i]) > 1) cout << i << ' ' << i / (i - nxt[i]) << endl;
    }
  }

public:
  bool solve() {
    if (! input()) return false;
    cout << "Test case #" << ++ T << endl;
    init(), process(), cout << endl; return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2029

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 100;
  int n, w, h, s, t, hor[N + 1][N + 1], ver[N + 1][N + 1];
  bool a[N + 1][N + 1];
  bool input() {
    cin >> n; if (! n) return false;
    cin >> w >> h, memset(a, false, sizeof a);
    for (int i = 1; i <= n; ++ i) {
      int x, y; cin >> x >> y, a[y][x] = 1;
    }
    cin >> s >> t;
    return true;
  }
  void init() {
    memset(hor, 0, sizeof hor);
    memset(ver, 0, sizeof ver);
    for (int i = 1; i <= h; ++ i) {
      for (int j = 1; j <= s; ++ j) hor[i][1] += a[i][j];
      for (int j = s + 1; j <= w; ++ j) hor[i][j - s + 1] = hor[i][j - s] + a[i][j] - a[i][j - s];
    }
    for (int i = 1; i <= w - s + 1; ++ i) {
      for (int j = 1; j <= t; ++ j) ver[1][i] += hor[j][i];
      for (int j = t + 1; j <= h; ++ j) ver[j - t + 1][i] = ver[j - t][i] + hor[j][i] - hor[j - t][i];
    }
  }
  void process() {
    int ans = 0;
    for (int i = 1; i <= h - t + 1; ++ i)
      for (int j = 1; j <= w - s + 1; ++ j) ans = max(ans, ver[i][j]);
    cout << ans << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2057

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int N = 1000;
int f[N + 1], size[N + 1];

bool cmp(int a, int b) {
  return f[a] * size[b] < f[b] * size[a];
}

int n, nume, h[N + 1];
int tim, ans, dfn[N + 1];
bool b[N + 1], leaf[N + 1];
struct Edge {
  int v, nxt;
} e[N << 1];

void add_edge(int u, int v) {
  e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
  e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}

bool input() {
  cin >> n; if (! n) return false;
  nume = 0, memset(h, 0, sizeof h);
  for (int i = 1; i <= n; ++ i) {
    int fa; char c;
    cin >> fa >> c;
    if (~ fa) add_edge(fa, i);
    b[i] = c == 'Y';
  }
  return true;
}

void init(int t, int fa) {
  f[t] = 2, size[t] = 0;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa)
      init(e[i].v, t), f[t] += f[e[i].v], size[t] += size[e[i].v];
  if (b[t]) f[t] = 2;
  if (leaf[t] = ! size[t]) size[t] = 1;
}

void dfs(int t, int fa) {
  int arr[10];
  memset(arr, 0, sizeof arr);
  int tmp = ++ tim; dfn[t] = tmp;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) arr[++ arr[0]] = e[i].v;
  sort(arr + 1, arr + arr[0] + 1, cmp);
  for (int i = 1; i <= arr[0]; ++ i) dfs(arr[i], t);
  if (b[t]) tim = tmp; ++ tim;
}

void process() {
  int cnt = 0;
  tim = -1, ans = 0, dfs(1, 0);
  for (int i = 1; i <= n; ++ i) cnt += leaf[i], ans += leaf[i] * dfn[i];
  cout << setprecision(4) << fixed << 1.0 * ans / cnt << endl;
}

bool solve() {
  if (! input()) return false;
  init(1, 0), process(); return true;
}

int main() {
  ios::sync_with_stdio(false);
  while (solve()) ;
  return 0;
}

POJ2065

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int p;

int power(int a, int b) {
  int ret = 1; a %= p, b %= p - 1;
  while (b) {
    if (b & 1) (ret *= a) %= p;
    (a *= a) %= p, b >>= 1;
  }
  return ret;
}

int get_inv(int t) {
  return power(t, p - 2);
}

struct Gauss {
  static const int N = 100;
  int n, a[N][N];
  void solve() {
    for (int i = 1; i <= n; ++ i) {
      if (! a[i][i])
        for (int j = i + 1; j <= n; ++ j)
          if (a[j][i]) {
            for (int k = i; k <= n + 1; ++ k) swap(a[i][k], a[j][k]);
            break;
          }
      int inv = get_inv(a[i][i]);
      for (int j = i; j <= n + 1; ++ j) (a[i][j] *= inv) %= p;
      for (int j = 1; j <= n; ++ j)
        if (j != i) {
          int tmp = a[j][i];
          for (int k = i; k <= n + 1; ++ k)
            (((a[j][k] -= a[i][k] * tmp % p) %= p) += p) %= p;
        }
    }
  }
};

struct Solver {
private:
  static const int N = 100;
  int n;
  string s;
  Gauss g;
  void input() {
    cin >> p >> s, n = s.length();
  }
  void init() {
    g.n = n;
    for (int i = 1; i <= n; ++ i) {
      int tmp = 1;
      for (int j = 1; j <= n; ++ j) g.a[i][j] = tmp, (tmp *= i) %= p;
      g.a[i][n + 1] = s[i - 1] - 'a' + 1;
      if (s[i - 1] == 42) g.a[i][n + 1] = 0;
    }
  }
  void process() {
    g.solve();
    for (int i = 1; i <= n; ++ i) cout << g.a[i][n + 1] << ' ';
    cout << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  int T; cin >> T;
  while (T --) solver.solve();
  return 0;
}

POJ2186

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 50000;
  int n, m, nume, tim, h[N + 1], fa[N + 1];
  int dfn[N + 1], low[N + 1], sta[N + 1], belong[N + 1];
  bool in[N + 1], vis[N + 1];
  struct Edge {
    int v, nxt;
  } e[N + 1];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
  }
  int get_fa(int t) {
    return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
  }
  void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
      int u, v; cin >> u >> v;
      add_edge(u, v);
    }
  }
  void dfs(int t) {
    in[sta[++ sta[0]] = t] = true, dfn[t] = low[t] = ++ tim;
    for (int i = h[t]; i; i = e[i].nxt) {
      if (in[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
      else if (! dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]);
    }
    if (dfn[t] == low[t]) {
      while (sta[sta[0]] != t) belong[sta[sta[0]]] = t, in[sta[sta[0] --]] = false;
      belong[sta[sta[0]]] = t, in[sta[sta[0] --]] = false;
    }
  }
  void process() {
    for (int i = 1; i <= n; ++ i) if (! dfn[i]) dfs(i);
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    memset(in, false, sizeof in);
    for (int i = 1; i <= n; ++ i)
      for (int j = h[i]; j; j = e[j].nxt) {
        if (belong[i] == belong[e[j].v]) continue;
        in[belong[i]] = true;
        int p = get_fa(belong[i]), q = get_fa(belong[e[j].v]);
        if (p != q) fa[p] = q;
      }
    int t = 0;
    for (int i = 1; i <= n; ++ i) if (! in[belong[i]] && ! vis[belong[i]]) vis[belong[i]] = true, ++ t;
    if (t > 1) { cout << 0 << endl; return; }
    int ans = 0;
    for (int i = 1; i <= n; ++ i) if (! in[belong[i]]) ++ ans;
    cout << ans << endl;
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2195

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 200;
  int n, m, cnt1, cnt2, dist[N + 1][N + 1];
  int match[N + 1], slack[N + 1], flag[2][N + 1];
  bool vis[2][N + 1];
  pair <int, int> a[N + 1], b[N + 1];
  bool input() {
    cin >> n >> m;
    cnt1 = cnt2 = 0;
    if (! n || ! m) return false;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        char c; cin >> c;
        if (c == 'H') a[++ cnt1].first = i, a[cnt1].second = j;
        else if (c == 'm') b[++ cnt2].first = i, b[cnt2].second = j;
      }
    return true;
  }
  void init() {
    memset(dist, 0, sizeof dist);
    for (int i = 1; i <= cnt1; ++ i)
      for (int j = 1; j <= cnt2; ++ j)
        dist[i][j] = -abs(a[i].first - b[j].first) - abs(a[i].second - b[j].second);
  }
  bool dfs(int t) {
    vis[0][t] = true;
    for (int i = 1; i <= cnt2; ++ i) {
      if (vis[1][i]) continue;
      int gap = flag[0][t] + flag[1][i] - dist[t][i];
      if (! gap) {
        vis[1][i] = true;
        if (! ~ match[i] || dfs(match[i])) {
          match[i] = t; return true;
        }
      } else slack[i] = min(slack[i], gap);
    }
    return false;
  }
  int km() {
    memset(match, -1, sizeof match);
    memset(flag[1], 0, sizeof flag[1]);
    for (int i = 1; i <= cnt1; ++ i) {
      flag[0][i] = dist[i][1];
      for (int j = 2; j <= cnt2; ++ j) flag[0][i] = max(flag[0][i], dist[i][j]);
    }
    for (int i = 1; i <= cnt1; ++ i) {
      memset(slack, 0x1f, sizeof slack);
      while (true) {
        memset(vis, false, sizeof vis);
        if (dfs(i)) break;
        int d = 1e9;
        for (int j = 1; j <= cnt2; ++ j)
          if (! vis[1][j]) d = min(d, slack[j]);
        for (int j = 1; j <= cnt2; ++ j) {
          if (vis[0][j]) flag[0][j] -= d;
          if (vis[1][j]) flag[1][j] += d; else slack[j] -= d;
        }
      }
    }
    int ret = 0;
    for (int i = 1; i <= cnt1; ++ i) ret += dist[match[i]][i];
    return ret;
  }
  void process() {
    cout << -km() << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2352

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct BinaryIndexedTree {
private:
  static const int N = 40000;
  int n, a[N];

public:
  void init(int t) { n = t; }
  void add(int p, int val) {
    for (; p <= n; p += p & -p) a[p] += val;
  }
  int sum(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret += a[p];
    return ret;
  }
};

struct Solver {
private:
  static const int N = 15000;
  int n, ans[N + 1];
  pair <int, int> point[N + 1];
  BinaryIndexedTree tree;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &point[i].first, &point[i].second), ++ point[i].first, ++ point[i].second;
  }
  void init() {
    tree.init(32001);
    sort(point + 1, point + n + 1);
  }
  void process() {
    int pnt = 1;
    for (int i = 1; i <= 32001; ++ i)
      for (; pnt <= n && point[pnt].first == i; ++ pnt) {
        ++ ans[tree.sum(point[pnt].second)];
        tree.add(point[pnt].second, 1);
      }
    for (int i = 0; i < n; ++ i) printf("%d\n", ans[i]);
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ2406

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 1000000;
  int n, nxt[N + 1];
  string s;
  bool input() {
    cin >> s;
    return s != ".";
  }
  void init() {
    nxt[0] = nxt[1] = 0;
    int k = 0; n = s.length();
    for (int i = 2; i <= n; ++ i) {
      for (; k && s[k] != s[i - 1]; k = nxt[k]) ;
      if (s[k] == s[i - 1]) ++ k; nxt[i] = k;
    }
  }
  void process() {
    if (n % (n - nxt[n])) cout << 1 << endl;
    else cout << n / (n - nxt[n]) << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2409

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  long long n, m, ans;
  long long power(long long a, long long b) {
    long long ret = 1;
    while (b) {
      if (b & 1) ret *= a;
      a *= a, b >>= 1;
    }
    return ret;
  }
  long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
  }
  bool input() {
    cin >> n >> m;
    return n && m;
  }
  void init() { ans = 0; }
  void process() {
    if (m == 1) { cout << n << endl; return; }
    if (m == 2) { cout << (n * (n - 1) >> 1) + n << endl; return; }
    for (int i = 0; i < m; ++ i) ans += power(n, gcd(m, i));
    if (m & 1) ans += m * power(n, (m + 1 >> 1));
    else ans += (m >> 1) * power(n, m >> 1) + (m >> 1) * power(n, (m >> 1) + 1);
    cout << ans / (m << 1) << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2411

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const long long N = 11;
  int n, m, pool[1 << N];
  long long f[N + 2][1 << N];
  bool check(int t) {
    bool flag = false;
    while (t) {
      if (t & 1) flag = ! flag;
      else if (flag) return false;
      t >>= 1;
    }
    return ! flag;
  }
  bool input() {
    cin >> n >> m;
    if (n > m) swap(n, m);
    return n && m;
  }
  void process() {
    if (n == 1) { cout << ! (m & 1) << endl; return; }
    int full = (1 << m) - 1;
    memset(f, 0, sizeof f);
    for (int i = 1; i <= pool[0] && pool[i] <= full; ++ i) f[1][pool[i]] = 1;
    for (int i = 0; i <= full; ++ i) f[2][full - i] = f[1][i];
    for (int i = 2; i <= n; ++ i)
      for (int j = 0; j <= full; ++ j)
        for (int k = 1; k <= pool[0] && pool[i] <= full; ++ k)
          if (! (j & pool[k]))
            f[i + 1][full - (j | pool[k])] += f[i][j];
    cout << f[n + 1][0] << endl;
  }

public:
  void init() {
    for (long long i = 0; i < 1 << N; ++ i)
      if (check(i)) pool[++ pool[0]] = i;
  }
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.init();
  while (solver.solve()) ;
  return 0;
}

POJ2454

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define random(n) (rand() % n + 1)

using namespace std;

struct Solver {
private:
  static const int N = 200;
  int n, r1, r2;
  pair <int, int> a[N];
  void input() {
    cin >> n;
    for (int i = 1; i <= n * 3; ++ i) cin >> a[i].first, a[i].second = i;
  }
  void init() {
    sort(a + 1, a + n * 3 + 1);
  }
  void process() {
    int s1 = 0, s2 = 0;
    for (int i = n + 1; i <= n << 1; ++ i) s1 += a[i].first;
    for (int i = (n << 1) + 1; i <= n * 3; ++ i) s2 += a[i].first;
    while (true) {
      if (s1 > 500 * n && s2 > 500 * n) break;
      r1 = random(n) + n, r2 = random(n) + (n << 1);
      s1 += a[r2].first - a[r1].first, s2 += a[r1].first - a[r2].first, swap(a[r1], a[r2]);
    }
    for (int i = 1; i <= n * 3; ++ i) cout << a[i].second << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2482

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct SegmentTree {
private:
  static const long long N = 50000;
  long long tot;
  struct Node {
    long long l, r, max, tag, child[2];
  } node[N];
  void push_down(long long root) {
    if (node[root].l == node[root].r) return;
    node[node[root].child[0]].max += node[root].tag, node[node[root].child[0]].tag += node[root].tag;
    node[node[root].child[1]].max += node[root].tag, node[node[root].child[1]].tag += node[root].tag;
    node[root].tag = 0;
  }
  void push_up(long long root) {
    if (node[root].l == node[root].r) return;
    node[root].max = max(node[node[root].child[0]].max, node[node[root].child[1]].max);
  }
  void build_tree(long long root) {
    node[root].max = node[root].tag = node[root].child[0] = node[root].child[1] = 0;
    if (node[root].l == node[root].r) return;
    long long mid = node[root].l + node[root].r >> 1;
    node[++ tot].l = node[root].l, node[tot].r = mid;
    node[root].child[0] = tot, build_tree(tot);
    node[++ tot].l = mid + 1, node[tot].r = node[root].r;
    node[root].child[1] = tot, build_tree(tot);
  }
  void insert_line(long long root, long long l, long long r, long long val) {
    if (node[root].r < l || node[root].l > r) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].max += val, node[root].tag += val; return;
    }
    push_down(root);
    insert_line(node[root].child[0], l, r, val);
    insert_line(node[root].child[1], l, r, val);
    push_up(root);
  }

public:
  void init(long long t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  void add(long long l, long long r, long long val) {
    insert_line(1, l, r, val);
  }
  long long get() { return node[1].max; }
};

struct Point {
  long long ox, oy, x, y, c, id;
};

bool cmpx(Point a, Point b) { return a.ox < b.ox; }
bool cmpy(Point a, Point b) { return a.oy < b.oy; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line {
  long long x1, x2, y, c;
  bool operator < (const Line &a) const {
    return y == a.y ? c > a.c : y < a.y;
  }
};

struct Solver {
private:
  static const long long N = 10000;
  Point point[N + 1 << 1];
  Line line[N + 1 << 1];
  SegmentTree tree;
  void input() {
    for (long long i = 1; i <= n; ++ i) {
      cin >> point[i].ox >> point[i].oy >> point[i].c, point[i].id = i;
      point[i + n].ox = point[i].ox + w - 1, point[i + n].oy = point[i].oy + h - 1;
      point[i + n].c = -point[i].c, point[i + n].id = i + n;
    }
  }
  void init() {
    tree.init(n << 1);
    sort(point + 1, point + (n << 1) + 1, cmpx), point[1].x = 1;
    for (long long i = 2; i <= n << 1; ++ i) point[i].x = point[i - 1].x + (point[i].ox != point[i - 1].ox);
    sort(point + 1, point + (n << 1) + 1, cmpy), point[1].y = 1;
    for (long long i = 2; i <= n << 1; ++ i) point[i].y = point[i - 1].y + (point[i].oy != point[i - 1].oy);
    sort(point + 1, point + (n << 1) + 1, cmpi);
    for (long long i = 1; i <= n; ++ i) {
      line[i].x1 = point[i].x, line[i].x2 = point[i + n].x;
      line[i].y = point[i].y, line[i].c = point[i].c;
      line[i + n].x1 = point[i].x, line[i + n].x2 = point[i + n].x;
      line[i + n].y = point[i + n].y, line[i + n].c = point[i + n].c;
    }
    sort(line + 1, line + (n << 1) + 1);
  }
  void process() {
    long long ans = 0, pnt = 1;
    for (long long i = 1; i <= n << 1; ++ i) {
      while (line[pnt].y == i && line[pnt].c > 0) tree.add(line[pnt].x1, line[pnt].x2, line[pnt].c), ++ pnt;
      ans = max(ans, tree.get());
      while (line[pnt].y == i && line[pnt].c < 0) tree.add(line[pnt].x1, line[pnt].x2, line[pnt].c), ++ pnt;
    }
    cout << ans << endl;
  }

public:
  long long n, w, h;
  void solve() {
    if (w < 2 || h < 2) { cout << 0 << endl; return; }
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (cin >> solver.n >> solver.w >> solver.h) solver.solve();
  return 0;
}

POJ2486

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 100;
  int nume, h[N + 1], a[N + 1], f[N + 1][N + 2 << 1], g[N + 1][N + 2 << 1];
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume;
  }
  void input() {
    nume = 0;
    memset(h, 0, sizeof h);
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    for (int i = 1; i < n; ++ i) {
      int u, v; cin >> u >> v, add_edge(u, v);
    }
  }
  void init() {
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
  }
  void dfs(int t, int fa) {
    for (int i = 0; i <= k; ++ i) f[t][i] = g[t][i] = a[t];
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa) {
        dfs(e[i].v, t);
        for (int j = k; ~ j; -- j)
          for (int l = 0; l <= j; ++ l) {
            f[t][j + 2] = max(f[t][j + 2], f[e[i].v][l] + f[t][j - l]);
            g[t][j + 2] = max(g[t][j + 2], f[e[i].v][l] + g[t][j - l]);
            g[t][j + 1] = max(g[t][j + 1], g[e[i].v][l] + f[t][j - l]);
          }
      }
  }
  void process() {
    dfs(1, 0), cout << g[1][k] << endl;
  }

public:
  int n, k;
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (cin >> solver.n >> solver.k) solver.solve();
  return 0;
}

POJ2492

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 2000;
  int T, n, m, fa[N + 1], dist[N + 1];
  void input() {
    scanf("%d%d", &n, &m);
  }
  void init() {
    memset(dist, 0, sizeof dist);
    for (int i = 1; i <= n; ++ i) fa[i] = i;
  }
  int get_fa(int t) {
    if (t == fa[t]) return t;
    int ret = get_fa(fa[t]);
    (dist[t] += dist[fa[t]]) &= 1;
    return fa[t] = ret;
  }
  void process() {
    bool flag = true;
    for (int i = 1; i <= m; ++ i) {
      int a, b; scanf("%d%d", &a, &b);
      int p = get_fa(a), q = get_fa(b);
      if (p != q) fa[p] = q, dist[p] = ! (dist[a] + dist[b] & 1);
      else if (dist[a] == dist[b]) flag = false;
    }
    printf("Scenario #%d:\n", ++ T);
    if (flag) printf("No suspicious bugs found!\n");
    else printf("Suspicious bugs found!\n");
    printf("\n");
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  int T; scanf("%d", &T);
  while (T --) solver.solve();
  return 0;
}

POJ2516

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct Solver {
private:
  static const int N = 50;
  int n, m, k, nume, h[N + 1 << 1], need[N + 1][N + 1], save[N + 1][N + 1];
  struct Edge {
    int v, c, f, nxt;
  } e[N * N * N];
  void add_edge(int u, int v, int c, int f) {
    e[++ nume].v = v, e[nume].c = c, e[nume].f = f, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].c = 0, e[nume].f = -f, e[nume].nxt = h[v], h[v] = nume;
  }
  bool input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= k; cin >> need[i][j ++]) ;
    for (int i = 1; i <= m; ++ i)
      for (int j = 1; j <= k; cin >> save[i][j ++]) ;
    return n && m && k;
  }
  bool vis[N + 1 << 1];
  int s, t, ans, dist[N + 1 << 1];
  bool spfa(int s, int t) {
    memset(vis, false, sizeof vis);
    memset(dist, 0x1f, sizeof dist);
    dist[t] = 0, vis[t] = true;
    deque <int> que; que.push_back(t);
    while (! que.empty()) {
      int u = que.front(); vis[u] = false, que.pop_front();
      for (int i = h[u]; i; i = e[i].nxt)
        if (e[i ^ 1].c && dist[e[i].v] > dist[u] - e[i].f) {
          dist[e[i].v] = dist[u] - e[i].f;
          if (! vis[e[i].v]) {
            vis[e[i].v] = true;
            if (! que.empty() && dist[e[i].v] < dist[que.front()]) que.push_front(e[i].v);
            else que.push_back(e[i].v);
          }
        }
    }
    return dist[s] < 5e8;
  }
  int dfs(int u, int low) {
    vis[u] = true;
    if (u == t) return low;
    int used = 0, a;
    for (int i = h[u]; i; i = e[i].nxt)
      if (! vis[e[i].v] && e[i].c && dist[u] - e[i].f == dist[e[i].v]) {
        a = dfs(e[i].v, min(e[i].c, low - used));
        if (a) ans += a * e[i].f, e[i].c -= a, e[i ^ 1].c += a, used += a;
        if (low == used) break;
      }
    return used;
  }
  int costflow() {
    int flow = 0;
    while (spfa(s, t)) {
      vis[t] = 1;
      while (vis[t]) {
        memset(vis, false, sizeof vis);
        flow += dfs(s, 1e9);
      }
    }
    return flow;
  }
  void process() {
    int tot = 0; s = 0, t = n + m + 1;
    bool flag = true;
    for (int i = 1; i <= k; ++ i) {
      nume = 1, memset(h, 0, sizeof h);
      for (int j = 1; j <= n; ++ j) add_edge(0, j, need[j][i], 0);
      for (int j = 1; j <= m; ++ j) add_edge(j + n, n + m + 1, save[j][i], 0);
      for (int j = 1; j <= n; ++ j)
        for (int k = 1; k <= m; ++ k) {
          int f; cin >> f, add_edge(j, k + n, min(need[j][i], save[k][i]), f);
        }
      ans = 0, costflow(), tot += ans;
      for (int j = h[0]; j; j = e[j].nxt) if (e[j].c) flag = false;
    }
    if (flag) cout << tot << endl; else cout << -1 << endl;
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  while (solver.solve()) ;
  return 0;
}

POJ2528

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct SegmentTree {
private:
  static const int N = 50000;
  int tot;
  struct Node {
    int l, r, val, child[2];
  } node[N];
  bool is_leaf(int root) {
    return node[root].l == node[root].r;
  }
  void push_down(int root) {
    if (is_leaf(root) || ! node[root].val) return;
    node[node[root].child[0]].val = node[node[root].child[1]].val = node[root].val, node[root].val = 0;
  }
  void build_tree(int root) {
    if (is_leaf(root)) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0 }, build_tree(tot);
  }
  void insert_line(int root, int l, int r, int val) {
    if (node[root].r < l || node[root].l > r) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].val = val; return;
    }
    push_down(root);
    insert_line(node[root].child[0], l, r, val);
    insert_line(node[root].child[1], l, r, val);
  }
  int get_val(int root, int p) {
    if (node[root].r < p || node[root].l > p) return 0;
    return node[root].val ? node[root].val : max(get_val(node[root].child[0], p), get_val(node[root].child[1], p));
  }

public:
  void init(int t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  void add(int l, int r, int val) {
    insert_line(1, l, r, val);
  }
  int get(int p) {
    return get_val(1, p);
  }
};

struct Point {
  int ox, x, id;
};

bool cmpx(Point a, Point b) { return a.ox < b.ox; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Solver {
private:
  static const int N = 20000;
  int n;
  bool disp[N];
  Point point[N + 1];
  SegmentTree tree;
  void input() {
    cin >> n;
    for (int i = 1; i <= n << 1; cin >> point[i].ox, point[i].id = i ++) ;
  }
  void init() {
    tree.init(n << 1);
    sort(point + 1, point + (n << 1) + 1, cmpx);
    for (int i = 1; i <= n << 1; ++ i) point[i].x = point[i - 1].x + (point[i].ox != point[i - 1].ox);
    sort(point + 1, point + (n << 1) + 1, cmpi);
  }
  void process() {
    for (int i = 1; i <= n; ++ i) tree.add(point[(i << 1) - 1].x, point[i << 1].x, i);
    memset(disp, 0, sizeof disp);
    for (int i = 1; i <= n << 1; disp[tree.get(i ++)] = true) ;
    int ans = 0;
    for (int i = 1; i <= n; ans += disp[i ++]) ;
    cout << ans << endl;
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  int T; cin >> T;
  while (T --) solver.solve();
  return 0;
}

POJ2750

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct SegmentTree {
private:
  static const int N = 100000;
  int tot;
  struct Node {
    int l, r, sum, lmin, rmin, min, lmax, rmax, max, child[2];
  } node[N << 2];
  void push_up(int root) {
    node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
    node[root].lmin = min(node[node[root].child[0]].lmin, node[node[root].child[0]].sum + node[node[root].child[1]].lmin);
    node[root].rmin = min(node[node[root].child[1]].rmin, node[node[root].child[1]].sum + node[node[root].child[0]].rmin);
    node[root].min = min(min(min(node[node[root].child[0]].min, node[node[root].child[1]].min), min(node[root].lmin, node[root].rmin)), node[node[root].child[0]].rmin + node[node[root].child[1]].lmin);
    node[root].lmax = max(node[node[root].child[0]].lmax, node[node[root].child[0]].sum + node[node[root].child[1]].lmax);
    node[root].rmax = max(node[node[root].child[1]].rmax, node[node[root].child[1]].sum + node[node[root].child[0]].rmax);
    node[root].max = max(max(max(node[node[root].child[0]].max, node[node[root].child[1]].max), max(node[root].lmax, node[root].rmax)), node[node[root].child[0]].rmax + node[node[root].child[1]].lmax);
  }
  void build_tree(int root) {
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, build_tree(tot);
  }
  void modify_point(int root, int p, int val) {
    if (node[root].r < p || node[root].l > p) return;
    if (node[root].l == node[root].r) {
      node[root] = (Node) { node[root].l, node[root].r, val, val, val, val, val, val, val, 0, 0 }; return;
    }
    modify_point(node[root].child[0], p, val), modify_point(node[root].child[1], p, val), push_up(root);
  }

public:
  void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); }
  void edit(int p, int val) { modify_point(1, p, val); }
  int get_max() { return node[1].max; }
  int get_min() { return node[1].min; }
};

struct Solver {
private:
  static const int N = 100000;
  int n, sum, cnt, a[N + 1];
  SegmentTree tree;
  void input() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i], sum += a[i], cnt += a[i] < 0;
  }
  void init() {
    tree.init(n);
    for (int i = 1; i <= n; ++ i) tree.edit(i, a[i]);
  }
  void process() {
    int T; cin >> T;
    while (T --) {
      int x, y; cin >> x >> y;
      sum += y - a[x], cnt += (y < 0) - (a[x] < 0), a[x] = y, tree.edit(x, y);
      cout << max(bool(cnt) * tree.get_max(), sum - tree.get_min()) << endl;
    }
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2777

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct SegmentTree {
private:
  static const int N = 100000;
  int tot;
  struct Node {
    int l, r, val, tag, child[2];
  } node[N << 2];
  void push_down(int root) {
    if (node[root].l == node[root].r || ! node[root].tag) return;
    node[node[root].child[0]].val = node[node[root].child[0]].tag = node[root].tag;
    node[node[root].child[1]].val = node[node[root].child[1]].tag = node[root].tag;
    node[root].tag = 0;
  }
  void push_up(int root) {
    if (node[root].l == node[root].r) return;
    node[root].val = node[node[root].child[0]].val | node[node[root].child[1]].val;
  }
  void build_tree(int root) {
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0, 0 }, build_tree(tot);
  }
  void insert_line(int root, int l, int r, int col) {
    if (node[root].r < l || node[root].l > r) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].val = node[root].tag = 1 << (col - 1); return;
    }
    push_down(root);
    insert_line(node[root].child[0], l, r, col);
    insert_line(node[root].child[1], l, r, col);
    push_up(root);
  }
  int query_line(int root, int l, int r) {
    if (node[root].r < l || node[root].l > r) return 0;
    if (node[root].l >= l && node[root].r <= r) return node[root].val;
    push_down(root);
    int ret = query_line(node[root].child[0], l, r) | query_line(node[root].child[1], l, r);
    push_up(root);
    return ret;
  }

public:
  void init(int t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  void add(int l, int r, int col) {
    insert_line(1, l, r, col);
  }
  int get(int l, int r) {
    int ret = query_line(1, l, r), cnt = 0;
    while (ret) cnt += ret & 1, ret >>= 1;
    return cnt;
  }
};

struct Solver {
private:
  static const int N = 100000;
  int n, m, a[N + 1];
  SegmentTree tree;
  void input() {
    int t; cin >> n >> t >> m;
  }
  void init() {
    tree.init(n), tree.add(1, n, 1);
  }
  void process() {
    while (m --) {
      char c; cin >> c;
      int x, y, z; cin >> x >> y;
      if (c == 'C') cin >> z, tree.add(min(x, y), max(x, y), z);
      else cout << tree.get(min(x, y), max(x, y)) << endl;
    }
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  ios::sync_with_stdio(false);
  solver.solve();
  return 0;
}

POJ2828

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

static const int N = 200000;
int a[N + 1];

struct SegmentTree {
private:
  int tot;
  struct Node {
    int l, r, res, child[2];
  } node[N << 2];
  void push_up(int root) {
    if (node[root].l == node[root].r) return;
    node[root].res = node[node[root].child[0]].res + node[node[root].child[1]].res;
  }
  void build_tree(int root) {
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 1, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 1, 0, 0 }, build_tree(tot);
    push_up(root);
  }
  void add_point(int root, int rank, int num) {
    if (rank < 1 || rank > node[root].res) return;
    if (node[root].l == node[root].r) {
      a[node[root].l] = num, -- node[root].res; return;
    }
    add_point(node[root].child[1], rank - node[node[root].child[0]].res, num);
    add_point(node[root].child[0], rank, num);
    push_up(root);
  }

public:
  void init(int t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  void add(int rank, int num) {
    add_point(1, rank, num);
  }
};

struct Solver {
private:
  int x[N + 1], y[N + 1];
  SegmentTree tree;
  void init() {
    tree.init(n);
    memset(a, 0, sizeof a);
  }
  void process() {
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &x[i], &y[i]), ++ x[i];
    for (int i = n; i; -- i) tree.add(x[i], y[i]);
    for (int i = 1; i <= n; ++ i) printf("%d ", a[i]);
    printf("\n");
  }

public:
  int n;
  void solve() {
    init(), process();
  }
} solver;

int main() {
  while (~ scanf("%d", &solver.n)) solver.solve();
  return 0;
}

POJ2886

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read_s(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    (x < 0) && (putchar('-'), x = -x);
    (x > 9) && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write_s(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct SegmentTree {
private:
  static const int N = 500000;
  int tot;
  struct Node {
    int l, r, val, child[2];
  } node[N << 2];
  void push_up(int root) {
    if (node[root].l == node[root].r) return;
    node[root].val = node[node[root].child[0]].val + node[node[root].child[1]].val;
  }
  void build_tree(int root) {
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 1, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 1, 0, 0 }, build_tree(tot);
    push_up(root);
  }
  int add_point(int root, int rank) {
    if (rank < 1 || rank > node[root].val) return 0;
    if (node[root].l == node[root].r) {
      -- node[root].val; return node[root].l;
    }
    int ret = add_point(node[root].child[1], rank - node[node[root].child[0]].val);
    ret += add_point(node[root].child[0], rank), push_up(root); return ret;
  }
  int query_sum(int root, int l, int r) {
    if (node[root].r < l || node[root].l > r) return 0;
    if (node[root].l >= l && node[root].r <= r) return node[root].val;
    return query_sum(node[root].child[0], l, r) + query_sum(node[root].child[1], l, r);
  }

public:
  void init(int t) {
    node[node[tot = 1].l = 1].r = t, build_tree(1);
  }
  int add(int rank) {
    return add_point(1, rank);
  }
  int get(int l, int r) {
    return query_sum(1, l, r);
  }
};

struct Solver {
private:
  static const int N = 500000;
  int a[N + 1];
  int prime[N + 1], e[N + 1], num[N + 1];
  bool flag[N + 1];
  char c[N + 1][20];
  SegmentTree tree;
  void input() {
    for (int i = 1; i <= n; ++ i) io.read_s(c[i]), io.read(a[i]);
  }
  void process() {
    if (n == 1) {
      io.write_s(c[1]), putchar(' '), putchar(1), putchar('\n'); return;
    }
    tree.init(n);
    int p = 0, mx = 0;
    for (int i = 1; i <= n; ++ i)
      if (num[i] > mx) mx = num[p = i];
    tree.add(k);
    int now = n;
    while (-- p) {
      if (a[k] > 0) a[k] = (a[k] - 1) % -- now + 1;
      else a[k] = (a[k] + 1) % -- now - 1;
      if (a[k] >= 0) {
        int j = k + 1;
        if (j <= n) {
          int sum = tree.get(j, n);
          if (a[k] <= sum) k = tree.add(tree.get(1, k) + a[k]); else k = tree.add(a[k] - sum);
        } else k = tree.add(a[k]);
      } else {
        int j = k - 1;
        if (j) {
          int sum = tree.get(1, j);
          if (-a[k] <= sum) k = tree.add(sum + a[k] + 1); else k = tree.add(tree.get(1, n) + sum + a[k] + 1);
        } else k = tree.add(tree.get(1, n) + a[k] + 1);
      }
    }
    io.write_s(c[k]), putchar(' '), io.write(mx), putchar('\n');
  }

public:
  int n, k;
  void init() {
    int cnt = 0;
    num[1] = 1;
    for (int i = 2; i <= N; ++ i) {
      if (! flag[i]) {
        prime[++ cnt] = i;
        e[i] = 1, num[i] = 2;
      }
      for (int j = 1; j <= cnt && i * prime[j] <= N; ++ j) {
        flag[i * prime[j]] = true;
        if (i % prime[j]) {
          num[i * prime[j]] = num[i] << 1, e[i * prime[j]] = 1;
        } else {
          num[i * prime[j]] = num[i] / (e[i] + 1) * (e[i] + 2);
          e[i * prime[j]] = e[i] + 1; break;
        }
      }
    }
  }
  void solve() {
    input(), process();
  }
} solver;

signed main() {
  solver.init();
  while (io.read(solver.n), io.read(solver.k)) solver.solve();
  return 0;
}

POJ2942

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    (x < 0) && (putchar('-'), x = -x);
    (x > 9) && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 1000;
  static const int M = 1000000;
  int n, m, tim, cnt, nume, h[N + 1], dfn[N + 1], low[N + 1], col[N + 1];
  int sta[M + 1];
  bool cut[N + 1], vis[N + 1], act[N + 1], a[N + 1][N + 1], con[N + 1][N + 1];
  struct Edge {
    int u, v, nxt;
  } e[M + 1 << 1];
  void add_edge(int u, int v) {
    e[++ nume].u = u, e[nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].u = v, e[nume].v = u, e[nume].nxt = h[v], h[v] = nume;
  }
  bool input() {
    io.read(n), io.read(m);
    if (! n || ! m) return false;
    memset(a, 0, sizeof a);
    for (int i = 1; i <= m; ++ i) {
      int u, v; io.read(u), io.read(v), a[u][v] = a[v][u] = true;
    }
    return true;
  }
  void init() {
    tim = cnt = nume = 0;
    memset(h, 0, sizeof h), memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low), memset(cut, 0, sizeof cut);
    memset(col, 0, sizeof col), memset(con, 0, sizeof con);
    memset(act, 0, sizeof act);
    for (int i = 1; i < n; ++ i)
      for (int j = i + 1; j <= n; ++ j)
        if (! a[i][j]) add_edge(i, j);
  }
  void dfs(int t, int fa) {
    int child = 0;
    dfn[t] = low[t] = ++ tim;
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa)
        if (! dfn[e[i].v]) {
          sta[++ sta[0]] = i, ++ child, dfs(e[i].v, t), low[t] = min(low[t], low[e[i].v]);
          if (low[e[i].v] >= dfn[t]) {
            ++ cnt, cut[t] = true;
            while (true) {
              int num = sta[sta[0] --];
              if (col[e[num].u] != cnt) con[cnt][e[num].u] = true, col[e[num].u] = cnt;
              if (col[e[num].v] != cnt) con[cnt][e[num].v] = true, col[e[num].v] = cnt;
              if (e[num].u == t && e[num].v == e[i].v) break;
            }
          }
        } else if (dfn[e[i].v] < dfn[t]) sta[++ sta[0]] = i, low[t] = min(low[t], dfn[e[i].v]);
    (! fa && child > 1) && (cut[t] = true);
  }
  bool color(int t, int cnt) {
    vis[t] = true;
    for (int i = h[t]; i; i = e[i].nxt)
      if (con[cnt][e[i].v])
        if (! vis[e[i].v]) {
          col[e[i].v] = ! col[t];
          if (color(e[i].v, cnt)) return true;
        } else if (col[e[i].v] == col[t]) return true;
    return false;
  }
  void process() {
    for (int i = 1; i <= n; ++ i) if (! dfn[i]) dfs(i, 0);
    for (int i = 1; i <= cnt; ++ i) {
      bool flag = false;
      memset(vis, 0, sizeof vis), memset(col, 0, sizeof col);
      for (int j = 1; j <= n; ++ j)
        (con[i][j] && ! vis[j]) && (flag = flag | color(j, i));
      if (flag)
        for (int j = 1; j <= n; ++ j) act[j] = act[j] | con[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++ i) ans += ! act[i];
    io.write(ans), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ2947

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    (x < 0) && (putchar('-'), x = -x);
    (x > 9) && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const int MOD = 7;

int power(int a, int b) {
  int ret = 1; a %= MOD, b %= MOD - 1;
  while (b) {
    if (b & 1) (ret *= a) %= MOD;
    (a *= a) %= MOD, b >>= 1;
  }
  return ret;
}

int get_inv(int t) {
  return power(t, MOD - 2);
}

struct Gauss {
  static const int N = 300;
  int n, m, a[N + 1][N + 2];
  void init() {
    n = m = 0, memset(a, 0, sizeof a);
  }
  int solve() {
    for (int i = 1; i <= min(n, m); ++ i) {
      if (! a[i][i]) {
        for (int j = i; j <= m; ++ j)
          if (a[j][i]) {
            for (int k = i; k <= n + 1; ++ k) swap(a[i][k], a[j][k]);
            break;
          }
        if (! a[i][i]) {
          for (int j = i; j <= m; ++ j) {
            bool flag = false;
            for (int k = i + 1; k <= n; ++ k) flag = flag || a[j][k];
            if (! flag && a[j][n + 1]) return -1;
          }
          return 1;
        }
      }
      int inv = get_inv(a[i][i]);
      for (int j = i; j <= n + 1; ++ j) (a[i][j] *= inv) %= MOD;
      for (int j = 1; j <= m; ++ j)
        if (j != i)
          for (int k = n + 1; k >= i; -- k) (a[j][k] += a[i][k] * (MOD - a[j][i])) %= MOD;
    }
    if (n > m) return 1;
    if (m > n)
      for (int i = n + 1; i <= m; ++ i) if (a[i][n + 1]) return -1;
    return 0;
  }
};

struct Solver {
private:
  static const int N = 300;
  int n, m, rank[N + 1], id[N + 1];
  bool flag[N + 1];
  char a[4], b[4];
  Gauss gauss;
  int get_num(char c[]) {
    if (c[0] == 'M') return 1;
    if (c[0] == 'T') if (c[1] == 'U') return 2; else return 4;
    if (c[0] == 'W') return 3;
    if (c[0] == 'F') return 5;
    if (c[0] == 'S') if (c[1] == 'A') return 6; else return 7;
  }
  bool input() {
    io.read(n), io.read(m);
    if (! n && ! m) return false;
    gauss.init(), gauss.n = n, gauss.m = m;
    for (int i = 1; i <= m; ++ i) {
      int k; io.read(k), io.read(a), io.read(b);
      gauss.a[i][n + 1] = (get_num(b) - get_num(a) + 1 + MOD) % MOD;
      for (int j = 1; j <= k; ++ j) {
        int x; io.read(x), (gauss.a[i][x] += 1) %= MOD;
      }
    }
    for (int i = 1; i <= n; ++ i) rank[i] = i;
    memset(flag, 0, sizeof flag);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) flag[i] = flag[i] || gauss.a[j][i];
    for (int i = 1; i <= n; ++ i)
      if (! flag[i])
        for (int j = i + 1; j <= n; ++ j)
          if (flag[j]) {
            for (int k = 1; k <= m; ++ k) swap(gauss.a[k][i], gauss.a[k][j]);
            swap(flag[i], flag[j]), swap(rank[i], rank[j]);
          }
    for (int i = 1; i <= n; ++ i) id[rank[i]] = i;
    return true;
  }
  void process() {
    int ans = gauss.solve();
    if (! ~ ans) io.write((char *) "Inconsistent data.");
    else if (! ans)
      for (int i = 1; i <= n; ++ i)
        io.write(gauss.a[id[i]][n + 1] < 3 ? gauss.a[id[i]][n + 1] + MOD : gauss.a[id[i]][n + 1]), putchar(' ');
    else io.write((char *) "Multiple solutions.");
    putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ2948

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 500;
  int n, m, a[N + 1][N + 1], b[N + 1][N + 1], f[2][N + 1][N + 1];
  bool input() {
    io.read(n), io.read(m);
    if (! n || ! m) return false;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) io.read(a[i][j]);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) io.read(b[i][j]);
    return true;
  }
  void init() {
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++ i)
      for (int j = 2; j <= m; ++ j) a[i][j] += a[i][j - 1];
    for (int i = 2; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) b[i][j] += b[i - 1][j];
  }
  void process() {
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        f[0][i][j] = max(f[0][i - 1][j], f[1][i - 1][j]) + a[i][j];
        f[1][i][j] = max(f[0][i][j - 1], f[1][i][j - 1]) + b[i][j];
      }
    io.write(max(f[0][n][m], f[1][n][m])), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ2976

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const double EPS = 1e-6;

struct Solver {
private:
  static const int N = 1000;
  int n, k;
  long long a[N + 1], b[N + 1];
  double c[N + 1];
  bool input() {
    io.read(n), io.read(k);
    if (! n && ! k) return false;
    for (int i = 1; i <= n; ++ i) io.read(a[i]);
    for (int i = 1; i <= n; ++ i) io.read(b[i]);
    return true;
  }
  bool check(double t) {
    double sum = 0;
    for (int i = 1; i <= n; ++ i) c[i] = t * b[i] - a[i];
    sort(c + 1, c + n + 1);
    for (int i = 1; i <= n - k; ++ i) sum += c[i];
    return sum <= 0;
  }
  void process() {
    double l = 0, r = 1;
    while (r - l > EPS) {
      double mid = (l + r) / 2;
      if (check(mid)) l = mid; else r = mid;
    }
    io.write((int) (l * 100 + 0.5)), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ2983

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 1000;
  int nume, h[N + 1], dist[N + 1], cnt[N + 1];
  int que[N * N];
  bool in[N + 1], vis[N + 1];
  struct Edge {
    int v, c, nxt;
  } e[N * N];
  void add_edge(int u, int v, int c) {
    e[++ nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    char ch; int a, b, c;
    memset(h, nume = 0, sizeof h);
    for (int i = 1; i <= m; ++ i) {
      io.read(ch), io.read(a), io.read(b);
      if (ch == 'P') io.read(c), add_edge(a, b, c), add_edge(b, a, -c);
      else add_edge(b, a, -1);
    }
  }
  bool spfa(int x) {
    int s = 0, t = 1;
    vis[que[1] = x] = true, dist[x] = 0, in[x] = cnt[x] = 1;
    while (s < t) {
      int u = que[++ s]; in[u] = false;
      for (int i = h[u]; i; i = e[i].nxt)
        if (dist[e[i].v] > dist[u] + e[i].c) {
          vis[e[i].v] = true;
          dist[e[i].v] = dist[u] + e[i].c;
          if (! in[e[i].v]) {
            que[++ t] = e[i].v, ++ cnt[e[i].v], in[e[i].v]= true;
            if (cnt[e[i].v] > 1000) return false;
          }
        }
    }
    return true;
  }
  void process() {
    memset(cnt, 0, sizeof cnt);
    memset(vis, 0, sizeof vis);
    memset(dist, 0x1f, sizeof dist);
    bool flag = true;
    for (int i = 1; i <= n; ++ i) if (! vis[i]) flag = flag && spfa(i);
    if (flag) io.write((char *) "Reliable");
    else io.write((char *) "Unreliable");
    putchar('\n');
  }

public:
  int n, m;
  void solve() {
    input(), process();
  }
} solver;

int main() {
  while (io.read(solver.n), io.read(solver.m)) solver.solve();
  return 0;
}

POJ3004

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const double EPS = 1e-6;
static const double PI = acos(-1);

int cmp(double t) {
  if (fabs(t) < EPS) return 0;
  if (t > 0) return 1; return -1;
}

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  double operator % (const Point &a) const {
    return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
  }
};

struct Line {
  double a, b;
  bool operator < (const Line &x) const {
    return ! cmp(a - x.a) ? cmp(b - x.b) == 1 : cmp(a - x.a) == -1; 
  }
};

struct Solver {
private:
  static const int N = 500;
  int n, d, top, mx;
  Point point[N + 1];
  Line line[N << 2];
  void input() {
    io.read(n), io.read(d);
    for (int i = 1; i <= n; ++ i) io.read(point[i].x), io.read(point[i].y);
  }
  void init() {
    top = 0;
    for (int i = 1; i <= n; ++ i) {
      double dist = point[i] % Point();
      if (cmp(dist - d) < 1) continue;
      double a = asin(point[i].y / dist);
      point[i].x < 0 && (a = PI - a);
      double b = asin(d / dist);
      a < b && (a += PI * 2);
      line[++ top].a = a - b, line[top].b = a + b;
    }
    for (int i = 1; i <= top; ++ i)
      line[i + top].a = line[i].a + PI * 2, line[i + top].b = line[i].b + PI * 2;
    sort(line + 1, line + (top << 1) + 1);
  }
  void process() {
    int ret = top;
    for (int i = 1; i <= top; ++ i) {
      int ans = 1;
      double r = line[i].b;
      for (int j = 1; j < top; ++ j) {
        ~ cmp(r - line[i + j].b) && (r = line[i + j].b);
        ! ~ cmp(r - line[i + j].a) && (++ ans, r = line[i + j].b);
      }
      ret = min(ret, ans);
    }
    io.write(ret), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  int T; io.read(T);
  while (T --) solver.solve();
  return 0;
}

POJ3034

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Point {
  int x, y, t;
};

struct Solver {
private:
  static const int N = 1000;
  int n, d, m, f[50][50][50];
  bool b[50][50];
  Point point[N + 1];
  bool input() {
    io.read(n), io.read(d), io.read(m);
    if (! n && ! d && ! m) return false;
    n += 10;
    for (int i = 1; i <= m; ++ i) io.read(point[i].x), io.read(point[i].y), io.read(point[i].t), point[i].x += 5, point[i].y += 5;
    return true;
  }
  void init() {
    memset(f, 0, sizeof f);
  }
  void process() {
    int ans = 0;
    for (int i = 1; i <= 10; ++ i) {
      memset(b, 0, sizeof b);
      for (int j = 1; j <= m; ++ j) if (point[j].t == i) b[point[j].x][point[j].y] = true;
      for (int j = 0; j < n; ++ j)
        for (int k = 0; k < n; ++ k) {
          f[i][j][k] = f[i - 1][j][k] + b[j][k];
          // 0 1
          if (j) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + b[j - 1][k] + b[j][k]);
          if (k) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + b[j][k - 1] + b[j][k]);
          if (j < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k] + b[j + 1][k] + b[j][k]);
          if (k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 1] + b[j][k + 1] + b[j][k]);
          if (d >= 2) {
            // 0 2
            if (j > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]);
            if (k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 2] + b[j][k - 2] + b[j][k - 1] + b[j][k]);
            if (j < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]);
            if (k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 2] + b[j][k + 2] + b[j][k + 1] + b[j][k]);
            // 1 1
            if (j && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + b[j - 1][k - 1] + b[j][k]);
            if (j && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 1] + b[j - 1][k + 1] + b[j][k]);
            if (j < n - 1 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 1] + b[j + 1][k - 1] + b[j][k]);
            if (j < n - 1 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 1] + b[j + 1][k + 1] + b[j][k]);
          }
          if (d >= 3) {
            // 0 3
            if (j > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]);
            if (k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 3] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]);
            if (j < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]);
            if (k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 3] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]);
            // 2 2
            if (j > 1 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 2] + b[j - 2][k - 2] + b[j - 1][k - 1] + b[j][k]);
            if (j > 1 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 2] + b[j - 2][k + 2] + b[j - 1][k + 1] + b[j][k]);
            if (j < n - 2 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 2] + b[j + 2][k - 2] + b[j + 1][k - 1] + b[j][k]);
            if (j < n - 2 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 2] + b[j + 2][k + 2] + b[j + 1][k + 1] + b[j][k]);
            // 1 2
            if (j && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 2] + b[j - 1][k - 2] + b[j][k]);
            if (j > 1 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 1] + b[j - 2][k - 1] + b[j][k]);
            if (j && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 2] + b[j - 1][k + 2] + b[j][k]);
            if (j < n - 2 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 1] + b[j + 2][k - 1] + b[j][k]);
            if (j > 1 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 1] + b[j - 2][k + 1] + b[j][k]);
            if (j < n - 1 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 2] + b[j + 1][k - 2] + b[j][k]);
            if (j < n - 2 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 1] + b[j + 2][k + 1] + b[j][k]);
            if (j < n - 1 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 2] + b[j + 1][k + 2] + b[j][k]);
          }
          if (d >= 4) {
            // 0 4
            if (j > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k] + b[j - 4][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]);
            if (k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 4] + b[j][k - 4] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]);
            if (j < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k] + b[j + 4][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]);
            if (k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 4] + b[j][k + 4] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]);
            // 1 3
            if (j && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 3] + b[j - 1][k - 3] + b[j][k]);
            if (j > 2 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 1] + b[j - 3][k - 1] + b[j][k]);
            if (j && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 3] + b[j - 1][k + 3] + b[j][k]);
            if (j < n - 3 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 1] + b[j + 3][k - 1] + b[j][k]);
            if (j > 2 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 1] + b[j - 3][k + 1] + b[j][k]);
            if (j < n - 1 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 3] + b[j + 1][k - 3] + b[j][k]);
            if (j < n - 3 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 1] + b[j + 3][k + 1] + b[j][k]);
            if (j < n - 1 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 3] + b[j + 1][k + 3] + b[j][k]);
            // 2 3
            if (j > 2 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 2] + b[j - 3][k - 2] + b[j][k]);
            if (j > 1 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 3] + b[j - 2][k - 3] + b[j][k]);
            if (j > 1 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 3] + b[j - 2][k + 3] + b[j][k]);
            if (j < n - 3 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 2] + b[j + 3][k - 2] + b[j][k]);
            if (j > 2 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 2] + b[j - 3][k + 2] + b[j][k]);
            if (j < n - 2 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 3] + b[j + 2][k - 3] + b[j][k]);
            if (j < n - 3 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 2] + b[j + 3][k + 2] + b[j][k]);
            if (j < n - 2 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 3] + b[j + 2][k + 3] + b[j][k]);
          }
          if (d >= 5) {
            // 0 5
            if (j > 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 5][k] + b[j - 5][k] + b[j - 4][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]);
            if (k > 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 5] + b[j][k - 5] + b[j][k - 4] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]);
            if (j < n - 5) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 5][k] + b[j + 5][k] + b[j + 4][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]);
            if (k < n - 5) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 5] + b[j][k + 5] + b[j][k + 4] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]);
            // 3 3
            if (j > 2 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 3] + b[j - 3][k - 3] + b[j - 2][k - 2] + b[j - 1][k - 1] + b[j][k]);
            if (j > 2 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 3] + b[j - 3][k + 3] + b[j - 2][k + 2] + b[j - 1][k + 1] + b[j][k]);
            if (j < n - 3 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 3] + b[j + 3][k - 3] + b[j + 2][k - 2] + b[j + 1][k - 1] + b[j][k]);
            if (j < n - 3 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 3] + b[j + 3][k + 3] + b[j + 2][k + 2] + b[j + 1][k + 1] + b[j][k]);
            // 1 4
            if (j && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 4] + b[j - 1][k - 4] + b[j][k]);
            if (j > 3 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 1] + b[j - 4][k - 1] + b[j][k]);
            if (j && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 4] + b[j - 1][k + 4] + b[j][k]);
            if (j < n - 4 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 1] + b[j + 4][k - 1] + b[j][k]);
            if (j > 3 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 1] + b[j - 4][k + 1] + b[j][k]);
            if (j < n - 1 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 4] + b[j + 1][k - 4] + b[j][k]);
            if (j < n - 4 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 1] + b[j + 4][k + 1] + b[j][k]);
            if (j < n - 1 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 4] + b[j + 1][k + 4] + b[j][k]);
            // 2 4
            if (j > 1 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 4] + b[j - 2][k - 4] + b[j - 1][k - 2] + b[j][k]);
            if (j > 3 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 2] + b[j - 4][k - 2] + b[j - 2][k - 1] + b[j][k]);
            if (j > 1 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 4] + b[j - 2][k + 4] + b[j - 1][k + 2] + b[j][k]);
            if (j < n - 4 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 2] + b[j + 4][k - 2] + b[j + 2][k - 1] + b[j][k]);
            if (j > 3 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 2] + b[j - 4][k + 2] + b[j - 2][k + 1] + b[j][k]);
            if (j < n - 2 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 4] + b[j + 2][k - 4] + b[j + 1][k - 2] + b[j][k]);
            if (j < n - 4 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 2] + b[j + 4][k + 2] + b[j + 2][k + 1] + b[j][k]);
            if (j < n - 2 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 4] + b[j + 2][k + 4] + b[j + 1][k + 2] + b[j][k]);
            // 3 4
            if (j > 2 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 4] + b[j - 3][k - 4] + b[j][k]);
            if (j > 3 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 3] + b[j - 4][k - 3] + b[j][k]);
            if (j > 3 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 3] + b[j - 4][k + 3] + b[j][k]);
            if (j < n - 3 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 4] + b[j + 3][k - 4] + b[j][k]);
            if (j > 2 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 4] + b[j - 3][k + 4] + b[j][k]);
            if (j < n - 4 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 3] + b[j + 4][k - 3] + b[j][k]);
            if (j < n - 3 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 4] + b[j + 3][k + 4] + b[j][k]);
            if (j < n - 4 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 3] + b[j + 4][k + 3] + b[j][k]);
          }
        }
    }
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < n; ++ j) ans = max(ans, f[10][i][j]);
    io.write(ans), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3070

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Matrix {
  int n, m, a[2][2];
  Matrix(int _n = 0, int _m = 0) : n(_n), m(_m) {
    memset(a, 0, sizeof a);
  }
  Matrix operator * (const Matrix &t) const {
    Matrix q(n, t.m);
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < t.m; ++ j) {
        for (int k = 0; k < m; ++ k) q.a[i][j] += a[i][k] * t.a[k][j];
        q.a[i][j] %= 10000;
      }
    return q;
  }
  Matrix operator ^ (const int &t) const {
    int b = t;
    Matrix p(n, n), q(n, n);
    p.a[0][0] = a[0][0], p.a[0][1] = a[0][1];
    p.a[1][0] = a[1][0], p.a[1][1] = a[1][1];
    q.a[0][0] = q.a[1][1] = 1;
    while (b) {
      if (b & 1) q = q * p;
      p = p * p, b >>= 1;
    }
    return q;
  }
};

struct Solver {
private:
  static const int N = 100000;
  int n;
  Matrix a;
  bool input() {
    io.read(n);
    return ~ n;
  }
  void process() {
    if (! n) io.write(0);
    else if (n < 3) io.write(1);
    else {
      a.n = a.m = 2;
      a.a[0][0] = a.a[0][1] = a.a[1][0] = 1, a.a[1][1] = 0;
      a = a ^ (n - 2), io.write((a.a[0][0] + a.a[0][1]) % 10000);
    }
    putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3071

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 7;
  int n;
  double a[1 << N][1 << N], f[N][1 << N];
  bool input() {
    scanf("%d", &n); if (! ~ n) return false;
    for (int i = 0; i < 1 << n; ++ i)
      for (int j = 0; j < 1 << n; ++ j) scanf("%lf", &a[i][j]);
    return true;
  }
  void init() {
    memset(f, 0, sizeof f);
    for (int i = 0; i < 1 << n; ++ i) f[0][i] = a[i][i ^ 1];
  }
  void process() {
    for (int i = 1; i < n; ++ i) {
      for (int j = 0; j < 1 << n; ++ j) {
        int tmp = (j >> i << i) ^ (1 << i);
        for (int k = 0; k < 1 << i; ++ k) f[i][j] += f[i - 1][j] * f[i - 1][tmp + k] * a[j][tmp + k];
      }
    }
    double mx(0); int p;
    for (int i = 0; i < 1 << n; ++ i) if (f[n - 1][i] > mx) mx = f[n - 1][p = i];
    printf("%d\n", p + 1);
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3101

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

long long get_gcd(long long a, long long b) {
  return b ? get_gcd(b, a % b) : a;
}

struct Fraction {
private:
  long long a, b;

public:
  Fraction(long long _a = 0, long long _b = 1) : a(_a), b(_b) {
    long long gcd = get_gcd(a, b);
    a /= gcd, b /= gcd;
  }
  Fraction operator + (const Fraction &_a) const {
    return Fraction(a * _a.b + b * _a.a, b * _a.b);
  }
  Fraction operator - (const Fraction &_a) const {
    return Fraction(a * _a.b - b * _a.a, b * _a.b);
  }
  Fraction operator * (const Fraction &_a) const {
    return Fraction(a * _a.a, b * _a.b);
  }
  Fraction operator / (const Fraction &_a) const {
    return Fraction(a * _a.b, b * _a.a);
  }
  int up() { return a; }
  int down() { return b; }
  void print() {
    io.write(a), putchar(' '), io.write(b);
  }
};

struct Solver {
private:
  static const int N = 1000;
  int n, top, a[N + 1], up[N * N + 1], ans[N * N + 1];
  Fraction v[N + 1], t[N + 1];
  void input() {
    io.read(n);
    for (int i = 1; i <= n; ++ i) io.read(a[i]);
  }
  void init() {
    sort(a + 1, a + n + 1);
    top = 0;
    memset(up, 0, sizeof up), memset(ans, 0, sizeof ans);
    for (int i = 1; i <= n; ++ i) if (a[i] != a[i - 1]) v[++ top] = Fraction(360, a[i]);
    for (int i = 2; i <= top; ++ i) t[i - 1] = Fraction(180) / (v[i - 1] - v[i]);
  }
  void process() {
    int down = 0;
    for (int i = 1; i < top; ++ i) {
      int tmp = t[i].up();
      for (int j = 2; j <= 10000; ++ j)
        if (! (tmp % j)) {
          int cnt = 0;
          while (! (tmp % j)) tmp /= j, ++ cnt;
          up[j] = max(up[j], cnt);
          if (tmp == 1) break;
        }
      if (tmp > 1) up[tmp] = 1;
      down = get_gcd(down, t[i].down());
    }
    for (int i = 2; i <= 1000000; ++ i)
      while (up[i] && ! (down % i)) down /= i, -- up[i];
    ans[ans[0] = 1] = 1;
    for (int i = 2; i <= 1000000; ++ i)
      while (up[i] > 0) {
        for (int j = 1; j <= ans[0]; ++ j) ans[j] *= i;
        for (int j = 1; j <= ans[0]; ++ j) ans[j + 1] += ans[j] / 100, ans[j] %= 100;
        while (ans[ans[0] + 1]) ++ ans[0], ans[ans[0] + 1] += ans[ans[0]] / 100, ans[ans[0]] %= 100;
        -- up[i];
      }
    for (int i = ans[0]; i; -- i) {
      int base = 10;
      while (i < ans[0] && ans[i] < base) putchar('0'), base /= 10;
      if (i == ans[0] || ans[i]) io.write(ans[i]);
    }
    putchar(' '), io.write(down), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3140

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Graph {
private:
  static const int N = 100000;
  int nume, h[N + 1];

public:
  struct Edge {
    int v, nxt;
  } e[N + 1 << 1];
  void init() {
    memset(h, nume = 0, sizeof h);
  }
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume;
  }
  Edge begin(int t) { return e[h[t]]; }
  Edge next(Edge t) { return e[t.nxt]; }
};

struct Solver {
private:
  static const int N = 100000;
  int T, n, m, sum, size[N + 1];
  Graph graph;
  int _abs(int t) {
    return t > 0 ? t : -t;
  }
  bool input() {
    io.read(n), io.read(m);
    if (! n && ! m) return false;
    graph.init(), sum = 0;
    for (int i = 1; i <= n; ++ i) io.read(size[i]), sum += size[i];
    for (int i = 1; i <= m; ++ i) {
      int u, v; io.read(u), io.read(v);
      graph.add_edge(u, v);
    }
    return true;
  }
  void dfs(int t, int fa) {
    for (Graph::Edge e = graph.begin(t); e.v; e = graph.next(e))
      if (e.v != fa) dfs(e.v, t), size[t] += size[e.v];
  }
  void process() {
    int ans = sum; dfs(1, 0);
    for (int i = 1; i <= n; ++ i) ans = min(ans, _abs((size[i] << 1) - sum));
    io.write((char *) "Case "), io.write(++ T), io.write((char *) ": "), io.write(ans), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

signed main() {
  while (solver.solve()) ;
  return 0;
}

POJ3150

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Matrix {
  static const int N = 500;
  int n, m, a[N + 1][N + 1];
  Matrix(int _n = 0, int _m = 1) : n(_n), m(_m) { memset(a, 0, sizeof a); }
  Matrix operator * (const Matrix &x) const {
    Matrix ret(n, m);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) (ret.a[1][i] += a[1][j] * x.a[j][i]) %= m;
    for (int i = 2; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) ret.a[i][j] = ret.a[i - 1][(j + n - 2) % n + 1];
    return ret;
  }
};

struct Solver {
private:
  static const int N = 500;
  int a[N + 1];
  Matrix p, ans;
  void input() {
    for (int i = 1; i <= n; ++ i) io.read(a[i]);
  }
  void init() {
    p.n = ans.n = n, p.m = ans.m = m;
    memset(p.a, 0, sizeof p.a);
    memset(ans.a, 0, sizeof ans.a);
    for (int i = 1; i <= n; ++ i)
      for (int j = -d; j <= d; ++ j)
        p.a[i][(i + j + n - 1) % n + 1] = 1;
    for (int i = 1; i <= n; ++ i) ans.a[i][i] = 1;
  }
  void process() {
    while (k) {
      if (k & 1) ans = ans * p;
      p = p * p, k >>= 1;
    }
    for (int i = 1; i <= n; ++ i) {
      int sum = 0;
      for (int j = 1; j <= n; ++ j) (sum += ans.a[i][j] * a[j]) %= m;
      io.write(sum), putchar(' ');
    }
    putchar('\n');
  }

public:
  int n, m, d, k;
  void solve() {
    input(), init(), process();
  }
} solver;

signed main() {
  while (io.read(solver.n), io.read(solver.m), io.read(solver.d), io.read(solver.k)) solver.solve();
  return 0;
}

POJ3227

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const double EPS = 1e-6;

int cmp(double t) {
  return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1;
}

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator * (const double &p) const { return Point(x * p, y * p); }
  double operator * (const Point &p) const { return x * p.y - y * p.x; }
  double operator % (const Point &p) const { return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  Line(double x1, double y1, double x2, double y2) : a(Point(x1, y1)), b(Point(x2, y2)) {}
  bool operator < (const Line &l) const {
    return ! ~ cmp(atan2(b.y - a.y, b.x - a.x) - atan2(l.b.y - l.a.y, l.b.x - l.a.x));
  }
  Point operator & (const Line &l) const {
    double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 1000;
  int n, h;
  double ans;
  Point point[N + 1];
  Line now;
  bool input() {
    io.read(n), io.read(h);
    if (! n && ! h) return false;
    for (int i = 1; i <= n; ++ i) {
      int x, y; io.read(x), io.read(y), point[i] = Point(x, y);
    }
    return true;
  }
  void init() {
    ans = 0, now = Line(0, h, point[1].x, 0);
  }
  void process() {
    for (int i = 1; i < n; ++ i)
      if (now < Line(Point(0, h), point[i + 1])) {
        Point tmp = now & Line(point[i], point[i + 1]);
        if (~ cmp(tmp.x - point[i].x) && ~ cmp(point[i + 1].x - tmp.x))
          ans += tmp % point[i + 1], now.b = point[i + 1];
      }
    printf("%.2lf\n", ans);
  }

public:
  bool solve() {
    if (! input()) return false;
    init(), process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3254

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 12;
  static const int MOD = 100000000;
  int n, m, tot, a[N + 1], pool[1 << N], f[N + 1][1 << N];
  void input() {
    io.read(n), io.read(m);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        int t; io.read(t), (a[i] <<= 1) += ! t;
      }
  }
  bool check(int t) {
    bool flag = false;
    while (t) {
      if (t & 1)
        if (flag) return false; else flag = true;
      else flag = false;
      t >>= 1;
    }
    return true;
  }
  void init() {
    for (int i = 0; i < 1 << m; ++ i) if (check(i)) pool[++ tot] = i;
  }
  void process() {
    int ans = 0; f[0][1] = 1;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= tot; ++ j)
        for (int k = 1; k <= tot; ++ k)
          if (! (pool[k] & a[i]) && ! (pool[k] & pool[j])) (f[i][k] += f[i - 1][j]) %= MOD;
    for (int i = 1; i <= tot; ++ i) (ans += f[n][i]) %= MOD;
    io.write(ans), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3264

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 50000;
  static const int M = 16;
  int n, q, a[N + 1], mx[N + 1][16], mn[N + 1][16], num[N + 1];
  void input() {
    io.read(n), io.read(q);
    for (int i = 1; i <= n; ++ i) io.read(a[i]);
  }
  void init() {
    for (int i = 1; i <= n; ++ i) mx[i][0] = mn[i][0] = a[i];
    for (int i = 1; i < 16; ++ i)
      for (int j = 1; j <= n; ++ j) {
        mx[j][i] = max(mx[j][i - 1], mx[min(n, j + (1 << i - 1))][i - 1]);
        mn[j][i] = min(mn[j][i - 1], mn[min(n, j + (1 << i - 1))][i - 1]);
      }
    for (int i = 1; 1 << i < n; ++ i) num[1 << i] = 1;
    for (int i = 2; i <= n; ++ i) num[i] += num[i - 1];
  }
  void process() {
    int l, r; io.read(l), io.read(r);
    int len = r - l + 1;
    io.write(max(mx[l][num[len]], mx[r - (1 << num[len]) + 1][num[len]]) - min(mn[l][num[len]], mn[r - (1 << num[len]) + 1][num[len]])), putchar('\n');
  }

public:
  void solve() {
    input(), init();
    while (q --) process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3270

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Number {
  int num, id, rank;
};

bool cmpn(Number a, Number b) { return a.num < b.num; }
bool cmpi(Number a, Number b) { return a.id < b.id; }

struct Solver {
private:
  static const int N = 10000;
  int n, t, cnt[N + 1], sum[N + 1], mn[N + 1], size[N + 1];
  bool vis[N + 1], st[N + 1];
  Number a[N + 1];
  void input() {
    io.read(n), t = 1e9;
    for (int i = 1; i <= n; ++ i) io.read(a[i].num), a[i].id = i, t = min(t, a[i].num);
  }
  void init() {
    sort(a + 1, a + n + 1, cmpn);
    for (int i = 1; i <= n; ++ i) a[i].rank = i;
    sort(a + 1, a + n + 1, cmpi);
  }
  void dfs(int t) {
    vis[t] = true, size[t] = 1, sum[t] = mn[t] = a[t].num;
    if (! vis[a[t].rank])
      dfs(a[t].rank), size[t] += size[a[t].rank], sum[t] += sum[a[t].rank], mn[t] = min(mn[t], mn[a[t].rank]);
  }
  void process() {
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
      if (! vis[i]) st[i] = true, dfs(i);
    for (int i = 1; i <= n; ++ i)
      if (st[i])
        ans += min(sum[i] + (size[i] - 2) * mn[i], sum[i] + mn[i] + (size[i] + 1) * t);
    io.write(ans), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

signed main() {
  solver.solve();
  return 0;
}

POJ3277

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct SegmentTree {
private:
  static const int N = 100000;
  int tot;
  struct Node { int l, r, val, child[2]; } node[N << 2];
  void build_tree(int root) {
    if (node[root].l == node[root].r) return;
    int mid = node[root].l + node[root].r >> 1;
    node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0 }, build_tree(tot);
    node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0 }, build_tree(tot);
  }
  void insert_line(int root, int l, int r, int val) {
    if (node[root].r < l || node[root].l > r) return;
    if (node[root].l >= l && node[root].r <= r) {
      node[root].val = max(node[root].val, val); return;
    }
    insert_line(node[root].child[0], l, r, val);
    insert_line(node[root].child[1], l, r, val);
  }
  int query_point(int root, int p) {
    if (node[root].r < p || node[root].l > p) return 0;
    if (node[root].l == node[root].r) return node[root].val;
    return max(node[root].val, max(query_point(node[root].child[0], p), query_point(node[root].child[1], p)));
  }

public:
  void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(tot); }
  void add(int l, int r, int val) { insert_line(1, l, r, val); }
  int get(int p) { return query_point(1, p); }
};

struct Point {
  int x, id, rank, h;
};

bool cmpx(Point a, Point b) { return a.x < b.x; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Solver {
private:
  static const int N = 100000;
  int n, mx, xmap[N];
  Point point[N];
  SegmentTree tree;
  void input() {
    io.read(n);
    for (int i = 1; i <= n; ++ i) {
      io.read(point[i].x), io.read(point[i + n].x), io.read(point[i].h);
      point[i].id = i, point[i + n].id = i + n;
    }
  }
  void init() {
    sort(point + 1, point + (n << 1) + 1, cmpx);
    for (int i = 1; i <= n << 1; ++ i) point[i].rank = point[i - 1].rank + (point[i].x != point[i - 1].x), xmap[point[i].rank] = point[i].x;
    mx = point[n << 1].rank;
    sort(point + 1, point + (n << 1) + 1, cmpi);
  }
  void process() {
    int ans = 0; tree.init(n << 1);
    for (int i = 1; i <= n; ++ i) tree.add(point[i].rank, point[i + n].rank - 1, point[i].h);
    for (int i = 1; i < mx; ++ i) ans += tree.get(i) * (xmap[i + 1] - xmap[i]);
    io.write(ans), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

signed main() {
  solver.solve();
  return 0;
}

POJ3280

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 2000;
  int n, m, cost[1 << 8][2], f[N + 1][N + 1];
  char s[N + 1];
  void input() {
    io.read(n), io.read(m), io.read(s);
    for (int i = 1; i <= n; ++ i) {
      char c; io.read(c);
      int x, y; io.read(x), io.read(y);
      cost[c][0] = x, cost[c][1] = y;
    }
  }
  void init() {
    memset(f, 0x1f, sizeof f);
    for (int i = 1; i <= m; ++ i)
      for (int j = 1; j <= i; ++ j) f[i][j] = 0;
    for (int i = 2; i <= m; ++ i)
      for (int j = 1; j <= m - i + 1; ++ j) {
        if (s[j - 1] == s[j + i - 2]) f[j][j + i - 1] = f[j + 1][j + i - 2];
        else f[j][j + i - 1] = min(f[j][j + i - 2] + min(cost[s[j + i - 2]][0], cost[s[j + i - 2]][1]), f[j + 1][j + i - 1] + min(cost[s[j - 1]][0], cost[s[j - 1]][1]));
      }
  }
  void process() {
    io.write(f[1][m]), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3286

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  int n, m;
  bool input() {
    io.read(n), io.read(m);
    return ~ n && ~ m;
  }
  int get(int t) {
    if (t < 0) return 0;
    int ret = 1 + t / 10, base = 10;
    for (int i = 1; i <= 10; ++ i, base *= 10) {
      int q = t / base / 10;
      if (! q) break;
      ret += (q - 1) * base + (t / base % 10 ? base : t % base + 1);
    }
    return ret;
  }
  void process() {
    io.write(get(m) - get(n - 1)), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

signed main() {
  while (solver.solve()) ;
  return 0;
}

POJ3296

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Solver {
private:
  static const int N = 100000;
  int k;
  double b, w, r, c;
  bool input() {
    scanf("%d%lf%lf%lf%lf", &k, &b, &w, &r, &c);
    return k;
  }
  void process() {
    double ans = w, tmp = 0;
    if (r > w) {
      double fi = r - w; b -= fi;
      if (b <= 0) { printf("0 \n"); return; }
      b /= k;
      printf("%d %.2lf ", k, min(b + fi, c - w));
      for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r));
      putchar('\n');
    } else {
      double fi = w - r;
      if ((b + fi) / k > fi) {
        (b += fi) /= k;
        printf("%d %.2lf ", k, min(b - fi, c - w));
        for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r));
        putchar('\n');
      } else {
        b /= k - 1;
        printf("%d 0.00 ", k);
        for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r));
        putchar('\n');
      }
    }
  }

public:
  bool solve() {
    if (! input()) return false;
    process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3301

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  Point operator ^ (const double &a) const {
    return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
};

static const double EPS = 1e-8;
static const double PI = acos(-1.0);

struct Solver {
private:
  static const int N = 30;
  int n;
  Point point[N + 1], tmp[N + 1];
  void input() {
    io.read(n);
    for (int i = 1; i <= n; ++ i) {
      int x, y; io.read(x), io.read(y), point[i] = Point(x, y);
    }
  }
  double get(double t) {
    for (int i = 1; i <= n; ++ i) tmp[i] = point[i] ^ t;
    double mxx = -500, mxy = -500, mnx = 500, mny = 500;
    for (int i = 1; i <= n; ++ i) {
      mxx = max(mxx, tmp[i].x), mxy = max(mxy, tmp[i].y);
      mnx = min(mnx, tmp[i].x), mny = min(mny, tmp[i].y);
    }
    return max(mxx - mnx, mxy - mny);
  }
  void process() {
    double l = 0, r = PI;
    while (r - l > EPS) {
      double ml = l + (r - l) / 3, mr = r - (r - l) / 3;
      double vl = get(ml), vr = get(mr);
      if (vl < vr) r = mr; else l = ml;
    }
    printf("%.2lf\n", get(l) * get(l));
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  int T; io.read(T);
  while (T --) solver.solve();
  return 0;
}

POJ3308

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const double EPS = 1e-8;
static const double MAX = 1e4;

struct Solver {
private:
  static const int N = 2000;
  int n, m, l, nume, h[N + 1];
  struct Edge {
    int v, nxt;
    double c;
  } e[N << 1];
  void add_edge(int u, int v, double c) {
    e[++ nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].c = 0, e[nume].nxt = h[v], h[v] = nume;
  }
  void input() {
    memset(h, 0, sizeof h), nume = 1;
    io.read(n), io.read(m), io.read(l);
    for (int i = 1; i <= n; ++ i) {
      double t; scanf("%lf", &t), add_edge(0, i, log(t));
    }
    for (int i = 1; i <= m; ++ i) {
      double t; scanf("%lf", &t), add_edge(n + i, n + m + 1, log(t));
    }
    for (int i = 1; i <= l; ++ i) {
      int u, v; io.read(u), io.read(v), add_edge(u, n + v, MAX);
    }
  }
  int s, t, g[N + 1], que[N + 1], dist[N + 1];
  bool bfs() {
    memset(dist, 0x1f, sizeof dist);
    int qb = 0, qe = 1; dist[que[1] = s] = 0;
    while (qb < qe) {
      int u = que[++ qb];
      for (int i = h[u]; i; i = e[i].nxt)
        if (e[i].c > 0 && dist[e[i].v] > dist[u] + 1)
          dist[que[++ qe] = e[i].v] = dist[u] + 1;
    }
    return dist[t] < 5e8;
  }
  double dfs(int u, double low) {
    if (u == t) return low;
    double used = 0;
    for (int i = g[u]; i; i = e[i].nxt)
      if (e[i].c > 0 && dist[e[i].v] == dist[u] + 1) {
        double delta = dfs(e[i].v, min(e[i].c, low - used));
        if (delta) e[i].c -= delta, e[i ^ 1].c += delta, used += delta;
        if (e[i].c > 0) g[u] = i;
        if (low == used) break;
      }
    return used;
  }
  void process() {
    s = 0, t = n + m + 1;
    double flow = 0;
    while (bfs()) {
      for (int i = 0; i <= n + m + 1; ++ i) g[i] = h[i];
      flow += dfs(s, MAX);
    }
    printf("%.4lf\n", exp(flow));
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  int T; io.read(T);
  while (T --) solver.solve();
  return 0;
}

POJ3318

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c = '\n'; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    if (! ~ c) return false;
    c == '-' && (flag = true, c = getchar());
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c = '\n'; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 500;
  int a[N + 1][N + 1], b[N + 1][N + 1], c[N + 1][N + 1];
  int d[N + 1], e[N + 1], f[N + 1], g[N + 1];
  void input() {
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) io.read(a[i][j]);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) io.read(b[i][j]);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) io.read(c[i][j]);
  }
  void init() {
    for (int i = 1; i <= n; ++ i) d[i] = rand() % 100;
    memset(e, 0, sizeof e), memset(f, 0, sizeof f), memset(g, 0, sizeof g);
  }
  void process() {
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) e[i] += d[j] * a[j][i];
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) f[i] += e[j] * b[j][i];
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) g[i] += d[j] * c[j][i];
    for (int i = 1; i <= n; ++ i) if (f[i] != g[i]) {
      io.write((char *) "NO\n"); return;
    }
    io.write((char *) "YES\n");
  }

public:
  int n;
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  srand(time(NULL));
  while (io.read(solver.n)) solver.solve();
  return 0;
}

POJ3321

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct BinaryIndexedTree {
private:
  static const int N = 100000;
  int a[N + 1];

public:
  int n;
  void add(int p, int val) {
    for (; p <= n; p += p & -p) a[p] += val;
  }
  int get(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret += a[p];
    return ret;
  }
  int sum(int l, int r) {
    return get(r) - get(l - 1);
  }
};

struct Solver {
private:
  static const int N = 100000;
  int n, m, nume, tim, h[N + 1], id[N + 1], last[N + 1];
  bool has[N + 1];
  BinaryIndexedTree tree;
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume;
  }
  void input() {
    io.read(n);
    for (int i = 1; i < n; ++ i) {
      int u, v; io.read(u), io.read(v), add_edge(u, v);
    }
  }
  void dfs(int t, int fa) {
    id[t] = ++ tim;
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa) dfs(e[i].v, t);
    last[t] = tim;
  }
  void process() {
    dfs(1, 0), io.read(m), tree.n = n, memset(has, 1, sizeof has);
    for (int i = 1; i <= n; ++ i) tree.add(i, 1);
    while (m --) {
      char c; int t; io.read(c), io.read(t);
      if (c == 'Q') io.write(tree.sum(id[t], last[t])), putchar('\n');
      else {
        if (has[t]) tree.add(id[t], -1); else tree.add(id[t], 1);
        has[t] = ! has[t];
      }
    }
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3352

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 1000;
  int nume, tim, h[N + 1], dfn[N + 1], low[N + 1], sta[N + 1], col[N + 1], in[N + 1];
  struct Edge {
    int v, nxt;
  } e[N + 1 << 1];
  void add_edge(int u, int v) {
    e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume;
  }
  void input() {
    memset(h, nume = 0, sizeof h);
    for (int i = 1; i <= r; ++ i) {
      int u, v; io.read(u), io.read(v), add_edge(u, v);
    }
  }
  void dfs(int t, int fa) {
    sta[++ sta[0]] = t;
    dfn[t] = low[t] = ++ tim;
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa)
        if (dfn[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
        else {
          dfs(e[i].v, t), low[t] = min(low[t], low[e[i].v]);
          if (low[e[i].v] > dfn[t]) {
            while (sta[sta[0]] != e[i].v) col[sta[sta[0] --]] = e[i].v;
            col[sta[sta[0] --]] = e[i].v;
          }
        }
  }
  void process() {
    tim = 0, memset(dfn, 0, sizeof dfn), dfs(1, 0);
    while (sta[0]) col[sta[sta[0] -- ]] = 1;
    memset(in, 0, sizeof in);
    for (int i = 1; i <= n; ++ i)
      for (int j = h[i]; j; j = e[j].nxt)
        if (col[i] < col[e[j].v]) ++ in[col[i]], ++ in[col[e[j].v]];
    int ans = 0;
    for (int i = 1; i <= n; ++ i) ans += in[i] == 1;
    io.write(ans + 1 >> 1), putchar('\n');
  }

public:
  int n, r;
  void solve() {
    input(), process();
  }
} solver;

int main() {
  while (io.read(solver.n), io.read(solver.r)) solver.solve();
  return 0;
}

POJ3368

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline bool read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return false;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', true);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 100000;
  int n, q, a[N + 1], b[N + 1], s[N + 1], t[N + 1], cnt[N + 1];
  int mx[N + 1][20], lo[N + 1];
  bool input() {
    io.read(n); if (! n) return false; io.read(q);
    for (int i = 1; i <= n; ++ i) io.read(a[i]);
    return true;
  }
  void init() {
    b[1] = 1;
    for (int i = 2; i <= n; ++ i) b[i] = b[i - 1] + (a[i] != a[i - 1]);
    s[1] = 1, t[b[n]] = n;
    for (int i = 2; i <= n; ++ i) if (b[i] != b[i - 1]) t[b[i - 1]] = i - 1, s[b[i]] = i;
    memset(cnt, 0, sizeof cnt), memset(lo, 0, sizeof lo);
    for (int i = 1; i <= n; ++ i) ++ cnt[b[i]];
    for (int i = 1; i <= b[n]; ++ i) mx[i][0] = cnt[i];
    for (int i = 1; i < 20; ++ i)
      for (int j = 1; j <= n; ++ j) mx[j][i] = max(mx[j][i - 1], mx[min(n, j + (1 << i - 1))][i - 1]);
    for (int i = 1; 1 << i <= b[n]; ++ i) ++ lo[1 << i];
    for (int i = 1; i <= b[n]; ++ i) lo[i] += lo[i - 1];
  }
  int query(int l, int r) {
    if (l > r) return 0;
    int len = r - l + 1;
    return max(mx[l][lo[len]], mx[r - (1 << lo[len]) + 1][lo[len]]);
  }
  void process() {
    int l, r; io.read(l), io.read(r);
    io.write(b[l] < b[r] ? max(max(t[b[l]] - l + 1, r - s[b[r]] + 1), query(b[l] + 1, b[r] - 1)) : r - l + 1), putchar('\n');
  }

public:
  bool solve() {
    if (! input()) return false;
    init(); while (q --) process(); return true;
  }
} solver;

int main() {
  while (solver.solve()) ;
  return 0;
}

POJ3373

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 110;
  static const int K = 10000;
  int k, base, f[N][K], nxt[N][K], cho[N][K];
  void input() { io.read(k); }
  void init() {
    memset(f, 0x1f, sizeof f);
    memset(cho, 0, sizeof cho);
    memset(nxt, 0, sizeof nxt);
  }
  void print(int a, int b) {
    if (a > len) return;
    io.write(cho[a][b]), print(a + 1, nxt[a][b]);
  }
  void process() {
    base = 10 % k;
    for (int i = 0; i < 10; ++ i)
      if ((i + '0' != c[len - 1]) < f[len][i % k])
        f[len][i % k] = i + '0' != c[len - 1], cho[len][i % k] = i;
    for (int i = len; i > 1; -- i, (base *= 10) %= k)
      for (int j = i == 2 ? 1 : 0; j < 10; ++ j)
        for (int l = 0; l < k; ++ l)
          if (f[i][l] + (j + '0' != c[i - 2]) < f[i - 1][(j * base + l) % k]) {
            f[i - 1][(j * base + l) % k] = f[i][l] + (j + '0' != c[i - 2]);
            nxt[i - 1][(j * base + l) % k] = l, cho[i - 1][(j * base + l) % k] = j;
          }
    print(1, 0), putchar('\n');
  }

public:
  int len;
  char c[N];
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  while (solver.len = io.read(solver.c)) solver.solve();
  return 0;
}

POJ3411

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 15;
  int n, m, nume, ans, h[N];
  int vis[N][1 << N];
  struct Edge {
    int v, c, p, r, nxt;
  } e[N];
  void add_edge(int u, int v, int c, int p, int r) {
    e[++ nume].v = v, e[nume].c = c;
    e[nume].p = p, e[nume].r = r;
    e[nume].nxt = h[u], h[u] = nume;
  }
  void input() {
    io.read(n), io.read(m);
    for (int i = 1; i <= m; ++ i) {
      int u, v, c, p, r;
      io.read(u), io.read(v), io.read(c), io.read(p), io.read(r);
      add_edge(u, v, c, p ,r);
    }
  }
  void dfs(int t, int status, int cost) {
    if (vis[t][status] <= cost) return;
    if (ans <= cost) return;
    if (t == n) { ans = cost; return; }
    vis[t][status] = cost;
    for (int i = h[t]; i; i = e[i].nxt)
      dfs(e[i].v, status | (1 << e[i].v - 1), cost + (status & (1 << e[i].c - 1) ? e[i].p : e[i].r));
  }
  void process() {
    memset(vis, 0x1f, sizeof vis), ans = 1e9, dfs(1, 0, 0);
    if (ans == 1e9) io.write((char *) "impossible\n");
    else io.write(ans), putchar('\n');
  }

public:
  void solve() {
    input(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3422

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Solver {
private:
  static const int N = 50;
  static const int M = N * N << 2;
  static const int K = 10;
  int n, k, nume, h[M + 1], a[N + 1][N + 1];
  struct Edge {
    int v, c, f, nxt;
  } e[N << K];
  void add_edge(int u, int v, int c, int f) {
    e[++ nume].v = v, e[nume].c = c, e[nume].f = f;
    e[nume].nxt = h[u], h[u] = nume;
    e[++ nume].v = u, e[nume].c = 0, e[nume].f = -f;
    e[nume].nxt = h[v], h[v] = nume;
  }
  void input() {
    io.read(n), io.read(k);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) io.read(a[i][j]);
  }
  int get_id(int x, int y) { return (x - 1) * n + y; }
  void init() {
    add_edge(0, nume = 1, k, 0);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j) {
        int id = get_id(i, j);
        add_edge((id << 1) - 1, id << 1, 1, -a[i][j]);
        add_edge((id << 1) - 1, id << 1, 10, 0);
        if (i < n) {
          int tmp = get_id(i + 1, j);
          add_edge(id << 1, (tmp << 1) - 1, 10, 0);
        }
        if (j < n) {
          int tmp = get_id(i, j + 1);
          add_edge(id << 1, (tmp << 1) - 1, 10, 0);
        }
      }
    add_edge(n * n << 1, (n * n << 1) + 1, k, 0);
  }
  int s, t, ans, que[M + 1], dist[M + 1];
  bool in[M + 1];
  bool spfa() {
    memset(dist, 0x1f, sizeof dist);
    memset(in, 0, sizeof in);
    int qb = 0, qe = 1; dist[que[1] = t] = 0, in[t] = true;
    while (qb != qe) {
      int u = que[(qb %= M) += 1]; in[u] = false;
      for (int i = h[u]; i; i = e[i].nxt)
        if (e[i ^ 1].c && dist[e[i].v] > dist[u] - e[i].f) {
          dist[e[i].v] = dist[u] - e[i].f;
          if (! in[e[i].v]) {
            in[e[i].v] = true;
            if (qb == qe || dist[que[qb % M + 1]] < dist[e[i].v]) que[(qe %= M) += 1] = e[i].v;
            else que[qb] = e[i].v, qb = (qb + M - 2) % M + 1;
          }
        }
    }
    return dist[s] < 5e8;
  }
  int dfs(int u, int low) {
    in[u] = true;
    if (u == t) return low;
    int used = 0;
    for (int i = h[u]; i; i = e[i].nxt)
      if (! in[e[i].v] && e[i].c && dist[e[i].v] == dist[u] - e[i].f) {
        int delta = dfs(e[i].v, min(e[i].c, low - used));
        if (delta) e[i].c -= delta, e[i ^ 1].c += delta, used += delta, ans += e[i].f * delta;
        if (low == used) break;
      }
    return used;
  }
  int costflow() {
    int flow = 0;
    while (spfa()) {
      in[t] = true;
      while (in[t]) {
        memset(in, 0, sizeof in);
        flow += dfs(s, 1e9);
      }
    }
    return flow;
  }
  void process() {
    s = 0, t = (n * n << 1) + 1, ans = 0, costflow(), io.write(-ans), putchar('\n');
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

POJ3429

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

struct Fraction {
  int a, b;
  int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
  }
  Fraction(int _a = 0, int _b = 1) : a(_a), b(_b) {
    int gcd = get_gcd(a, b); a /= gcd, b /= gcd;
  }
  Fraction operator + (const Fraction &f) const {
    return Fraction(a * f.b + b * f.a, b * f.b);
  }
  Fraction operator - (const Fraction &f) const {
    return Fraction(a * f.b - b * f.a, b * f.b);
  }
  Fraction operator * (const Fraction &f) const {
    return Fraction(a * f.a, b * f.b);
  }
  Fraction operator / (const Fraction &f) const {
    return Fraction(a * f.b, b * f.a);
  }
};

struct Point {
  Fraction x, y;
  Point(Fraction _x = Fraction(), Fraction _y = Fraction()) : x(_x), y(_y) {}
  Point operator + (const Point &p) const {
    return Point(x + p.x, y + p.y);
  }
  Point operator - (const Point &p) const {
    return Point(x - p.x, y - p.y);
  }
  Point operator * (const Fraction &p) const {
    return Point(x * p, y * p);
  }
  Fraction operator * (const Point &p) const {
    return x * p.y - y * p.x;
  }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  Point operator & (const Line &l) const {
    Fraction t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 100;
  int m;
  Point point[N << 1];
  void input() {
    for (int i = 1; i <= n; ++ i) {
      int x, y; io.read(x), io.read(y), point[i] = Point(Fraction(x), Fraction(y));
    }
    io.read(m);
  }
  void process() {
    int ans = 0;
    for (int i = 1; i <= m; ++ i) {
      int a, b, c, d;
      io.read(a), io.read(b), io.read(c), io.read(d);
      Point tmp = Line(point[a], point[b]) & Line(point[c], point[d]);
      if (! tmp.x.a && ! tmp.y.a && ! ans) ans = i;
      point[n + i] = tmp;
    }
    io.write(ans), putchar('\n');
  }

public:
  int n;
  void solve() {
    input(), process();
  }
} solver;

signed main() {
  while (io.read(solver.n)) solver.solve();
  return 0;
}

POJ3440

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
} io;

static const double PI = acos(-1.0);

struct Solver {
private:
  static const int N = 100000;
  int T, n, m, t, c;
  double ans[5];
  void input() {
    io.read(n), io.read(m), io.read(t), io.read(c);
  }
  void process() {
    io.write((char *) "Case "), io.write(++ T), io.write((char *) ":\n");
    memset(ans, 0, sizeof ans);
    ans[1] = n * m * (t - c) * (t - c) + (n + m) * (t - c) * c + c * c;
    ans[2] = (n * (m - 1) + (n - 1) * m) * (t - c) * c + (n + m - 2) * c * c;
    ans[3] = (n - 1) * (m - 1) * (c * c - c * c * PI / 4);
    ans[4] = n * m * t * t - ans[1] - ans[2] - ans[3] - ans[4];
    for (int i = 1; i <= 4; ++ i)
      printf("Probability of covering %lld tile%c = %.4lf%%\n", i, i > 1 ? 's' : ' ', ans[i] / n / m / t / t * 100);
    putchar('\n');
  }

public:
  void solve() {
    input(), process();
  }
} solver;

signed main() {
  int T; io.read(T);
  while (T --) solver.solve();
  return 0;
}

Choosing Balls

题目描述

There are $n$ balls. They are arranged in a row. Each ball has a color (for convenience an integer) and an integer value. The color of the $i$-th ball is $c_i$ and the value of the $i$-th ball is $v_i$.
Squirrel Liss chooses some balls and makes a new sequence without changing the relative order of the balls. She wants to maximize the value of this sequence.
The value of the sequence is defined as the sum of following values for each ball (where $a$ and $b$ are given constants):

  • If the ball is not in the beginning of the sequence and the color of the ball is same as previous ball’s color, add $\text{the value of the ball} \times a$.
  • Otherwise, add $\text{the value of the ball} \times b$.

You are given $q$ queries. Each query contains two integers $a_i$ and $b_i$. For each query find the maximal value of the sequence she can make when $a=a_i$ and $b=b_i$.
Note that the new sequence can be empty, and the value of an empty sequence is defined as zero.

题意概述

$n$个球排成一行,第$i$个球的颜色是$c_i$,价值是$v_i$。一个序列的价值等于与前一个球颜色相同的球的价值之和乘以$a$加其他球的价值之和乘以$b$。空序列的价值为$0$。有$q$组询问,每组询问给定$a, b$,求这$n$个球的最大价值子序列。
数据范围:$1 \le c_i \le n \le 10^5, \; 1 \le q \le 500, \; 0 \le |v_i|, |a|, |b| \le 10^5$。

算法分析

令$f_i$表示以第$i$种颜色结尾的序列的最大价值。设当前处理到第$i$个球,转移方程如下
$$f_{c_i}=\max(\max(f_x \mid x \neq c_i, 0)+v_i \times b, f_{c_i}+v_i \times a)$$
转移时维护当前$f_i$的最大值和次大值,这样可以直接得到$\max(f_x \mid x \neq c_i)$。

代码

import std.stdio;

static immutable MAX_NUM = 1000000000000000;

int n, q;
int[] c;
long[] v, f;

int main() {
  auto input = stdin;
  auto output = stdout;
  input.readf(" %d %d", &n, &q);
  v.length = c.length = f.length = n + 1;
  for (int i = 1; i <= n; ++ i) input.readf(" %d", &v[i]);
  for (int i = 1; i <= n; ++ i) input.readf(" %d", &c[i]);
  while (q --) {
    long a, b, max = -MAX_NUM, sec = -MAX_NUM, ans = 0;
    input.readf(" %d %d", &a, &b);
    for (int i = 1; i <= n; ++ i) f[i] = -MAX_NUM;
    for (int i = 1; i <= n; ++ i) {
      long p = f[c[i]] == max ? sec : max, q = f[c[i]];
      bool flag = f[c[i]] == max;
      if (f[c[i]] < v[i] * b) f[c[i]] = v[i] * b;
      if (f[c[i]] < p + v[i] * b) f[c[i]] = p + v[i] * b;
      if (f[c[i]] < q + v[i] * a) f[c[i]] = q + v[i] * a;
      if (f[c[i]] >= max) {
        if (! flag) sec = max;
        max = f[c[i]];
      } else if (f[c[i]] > sec) sec = f[c[i]];
    }
    for (int i = 1; i <= n; ++ i) {
      if (ans < f[i]) ans = f[i];
    }
    output.writeln(ans);
  }
  return 0;
}

Vasya’s Function

题目描述

Vasya is studying number theory. He has denoted a function $f(a, b)$ such that:

  • $f(a, 0)=0$;
  • $f(a, b)=1+f(a, b-(a, b))$, where $(a, b)$ is the greatest common divisor of $a$ and $b$.

Vasya has two numbers $x$ and $y$, and he wants to calculate $f(x, y)$. He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

题意概述

函数$f(a, b)$的定义如下:
$$
\begin{align}
f(a, 0)&=0 \\
f(a, b)&=1+f(a, b-(a, b))
\end{align}
$$
给定$x, y$,求$f(x, y)$。
数据范围:$1 \le x, y \le 10^{12}$。

算法分析

有个显然的结论:$f(a, b)=f(ka, kb) \; (k \gt 0)$。所以只需要考虑$(a, b)=1$的情况。
设$(x, y)=1$,由于$x$始终不变,因此先将$x$分解质因数。质因子最多只有$12$个,因为$2 \times 3 \times 5 \times 7 \times \cdots \times 31 \times 37 \gt 10^{12}$。找出最大的$s$满足$s \lt y$且$s$是$x$某个质因子的倍数,将答案加上$y-s$,并令$y=s$。将$x, y$同时除以$(x, y)$,问题转化成了一个更小的子问题,可以迭代处理。

代码

import std.stdio;
import std.math;

static immutable int N = 13;

uint top;
long x, y, p, q, ans;
long[N] prime, cnt;

long gcd(long a, long b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  readf(" %d %d", &x, &y);
  p = x, q = cast(long) sqrt(real(x));
  for (int i = 2; i <= q; ++ i) {
    while (! (p % i)) {
      p /= i;
      if (prime[top] == i) ++ cnt[top];
      else prime[++ top] = i, cnt[top] = 1;
    }
  }
  if (p > 1) prime[++ top] = p, cnt[top] = 1;
  while (y) {
    long max = 0;
    for (int i = 1; i <= top; ++ i)
      if (cnt[i])
        if (y / prime[i] * prime[i] > max)
          max = y / prime[i] * prime[i];
    ans += y - max, y = max;
    long g = gcd(x, y);
    x /= g, y /= g;
    for (int i = 1; i <= top; ++ i)
      while (! (g % prime[i]))
        g /= prime[i], -- cnt[i];
  }
  writeln(ans);
  return 0;
}

Visit of the Great

题目描述

The Great Mushroom King descended to the dwarves, but not everyone managed to see him. Only the few chosen ones could see the King.
We know that only $LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$ dwarves can see the Great Mushroom King. Numbers $k, l, r$ are chosen by the Great Mushroom King himself in some complicated manner which is unclear to common dwarves.
The dwarven historians decided to document all visits of the Great Mushroom King. For each visit the dwarven historians know three integers $k_i, l_i, r_i$, chosen by the Great Mushroom King for this visit. They also know a prime number $p_i$. Help them to count the remainder of dividing the number of dwarves who can see the King, by number $p_i$, for each visit.

题意概述

给定$t$组$k, l, r, p$,对于每一组求出$LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \bmod p$。保证$p$是质数。
数据范围:$1 \le t \le 10^5, \; 1 \le k \le 10^6, \; 0 \le l \le r \le 10^{18}, \; 2 \le p \le 10^9$。

算法分析

可以证明$(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \le 2$。证明如下:

令$g=(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$
$g \mid k^{2^n}+1 \Leftrightarrow k^{2^n} \equiv -1 \pmod g$
两边同时平方可得$k^{2^{n+1}} \equiv 1 \pmod g \Leftrightarrow g \mid k^{2^{n+1}}-1$
$\because g \mid k^{2^{n+1}}+1$
$\therefore g \le 2$

由此得证。
令$s=\prod_{i=l}^r (k^{2^i}+1)={k^{2^{l+1}}-1 \over k^{2^l}-1} \cdot {k^{2^{l+2}}-1 \over k^{2^{l+1}}-1} \cdots {k^{2^{r+1}}-1 \over k^{2^r}-1}={k^{2^{r+1}}-1 \over k^{2^l}-1}$。根据费马小定理,$x^{p-1} \equiv 1 \pmod p$,可以在$O(\log r)$的时间内求出$s$。如果$k$是奇数,那么答案是${s \over 2^{r-l}} \bmod p$,否则答案就是$s \bmod p$。
还要考虑到两种特殊情况。一种是$p=2$,直接特判即可;另一种是$p \mid k^{2^l}-1$,这就意味着$\forall i \ge l, \; p \mid k^{2^i}-1$,这等价于$\forall i \ge l, \; k^{2^i}+1 \equiv 2 \pmod p$,因此答案是$2^{r-l+1} \bmod p$。

代码

import std.stdio;

long power(long a, long b, long mod) {
  if (b && ! (a % mod)) return 0;
  long ret = 1;
  while (b) {
    if (b & 1) (ret *= a) %= mod;
    (a *= a) %= mod, b >>= 1;
  }
  return ret;
}

long inv(long a, long p) {
  return power(a, p - 2, p);
}

int main() {
  int T; readf(" %d", &T);
  while (T--) {
    long k, l, r, p, q, ans;
    readf(" %d %d %d %d", &k, &l, &r, &p), q = p - 1;
    if (p == 2) {
      if (k & 1) writeln(0); else writeln(1);
      continue;
    }
    ans = (power(k, power(2, l, q) + q, p) + q) % p;
    if (! ans) ans = power(2, r - l + 1, p);
    else ans = (power(k, power(2, r + 1, q) + q, p) + q) * inv(ans, p) % p;
    if (k & 1) (ans *= power((p >> 1) + 1, r - l, p)) %= p;
    writeln(ans);
  }
  return 0;
}

Sereja and Subsequences

题目描述

Sereja has a sequence that consists of $n$ positive integers, $a_1, a_2, \ldots, a_n$.
First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence $a$. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.
A sequence of positive integers $x=x_1, x_2, \ldots, x_r$ doesn’t exceed a sequence of positive integers $y=y_1, y_2, \ldots, y_r$, if the following inequation holds: $x_1 \le y_1, x_2 \le y_2, \ldots, x_r \le y_r$.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $1000000007$ ($10^9+7$).

题意概述

定义一个序列$a_1, a_2, \ldots, a_k$的数量等于长度为$k$且第$i$个元素不大于$a_i$的序列的个数。给定一个长度为$n$的序列,求其所有不下降子序列的数量之和。
数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 10^6$。

算法分析

显然,对于一个序列$a_1, a_2, \ldots, a_k$,它的数量为$a_1a_2 \cdots a_k$。令$f_i$表示以$i$结尾的不下降子序列的数量之和。设当前枚举到第$i$个数,转移方程如下
$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$
可以用树状数组来维护前缀和。最后得到的$f_1+f_2+ \cdots +f_{10^6}$就是答案。

代码

<?php
  const MAX_NUM = 1000000;
  const MOD = 1000000007;

  $tree = array();
  for ($i = 0; $i <= MAX_NUM; ++ $i) array_push($tree, 0);

  function add($pos, $val) {
    global $tree;
    for (; $pos <= MAX_NUM; $pos += $pos & -$pos) {
      $tree[$pos] += $val;
      $tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD;
    }
  }

  function get($pos) {
    global $tree;
    $ret = 0;
    for (; $pos; $pos -= $pos & -$pos) {
      $ret += $tree[$pos];
      $ret -= (int) ($ret / MOD) * MOD;
    }
    return $ret;
  }

  $n = fgets(STDIN);
  $a = explode(' ', trim(fgets(STDIN)));
  for ($i = 0; $i < $n; ++ $i) {
    $sum = get($a[$i]);
    add($a[$i], $sum * $a[$i] + $a[$i] - $sum + get($a[$i] - 1));
  }
  $ans = get(MAX_NUM);
  $ans -= (int) ($ans / MOD) * MOD;
  echo $ans . "\n";
?>