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;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *