## POJ3252

#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

#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

#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

#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

#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

#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

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


#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

#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

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

#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

#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

#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

#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

#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

#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

#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

#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

#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

#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

#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)
}
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

#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

#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

#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) {
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) {
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;
}
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) {
}
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))
}
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;
}
}
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;
}
}
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;
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;
}
}
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)];
}
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() {
}
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;
}
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) {
}
};

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>
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);
}
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 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];
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 {
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();
return 0;
}


## POJ2942

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
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() {
if (! n || ! m) return false;
memset(a, 0, sizeof a);
for (int i = 1; i <= m; ++ i) {
}
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)
}
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>
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);
}
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() {
if (! n && ! m) return false;
gauss.init(), gauss.n = n, gauss.m = m;
for (int i = 1; i <= m; ++ i) {
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>
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);
}
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() {
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>
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);
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
}
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() {
return 0;
}


## POJ3004

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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) {
}
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
return 0;
}


## POJ3227

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
if (! n && ! h) return false;
for (int i = 1; i <= n; ++ i) {
}
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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 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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
for (int i = 1; i <= n; ++ i) {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
for (int i = 1; i <= n; ++ i) {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
for (int i = 1; i <= n; ++ i) {
}
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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;
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 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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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));
return 0;
}


## POJ3321

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
for (int i = 1; i < n; ++ i) {
}
}
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 --) {
if (c == 'Q') io.write(tree.sum(id[t], last[t])), putchar('\n');
else {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
}
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() {
return 0;
}


## POJ3368

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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 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() {
return 0;
}


## POJ3411

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
for (int i = 1; i <= m; ++ i) {
int 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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
}
void process() {
int ans = 0;
for (int i = 1; i <= m; ++ i) {
int a, b, c, 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() {
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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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() {
}
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() {
while (T --) solver.solve();
return 0;
}


## 题目描述

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

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

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

## 题意概述

$n$个球排成一行，第$i$个球的颜色是$c_i$，价值是$v_i$。一个序列的价值等于与前一个球颜色相同的球的价值之和乘以$a$加其他球的价值之和乘以$b$。空序列的价值为$0$。有$q$组询问，每组询问给定$a, b$，求这$n$个球的最大价值子序列。

## 算法分析

$$f_{c_i}=\max(\max(f_x \mid x \neq c_i, 0)+v_i \times b, f_{c_i}+v_i \times a)$$

## 代码

import std.stdio;

static immutable MAX_NUM = 1000000000000000;

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

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


## 题目描述

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

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

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

## 题意概述

\begin{align} f(a, 0)&=0 \\ f(a, b)&=1+f(a, b-(a, b)) \end{align}

## 代码

import std.stdio;
import std.math;

static immutable int N = 13;

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

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

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


## 题目描述

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

## 算法分析

$g \mid k^{2^n}+1 \Leftrightarrow k^{2^n} \equiv -1 \pmod g$

$\because g \mid k^{2^{n+1}}+1$
$\therefore g \le 2$

## 代码

import std.stdio;

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

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

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


## 题目描述

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

## 算法分析

$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$

## 代码

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

$tree = array(); for ($i = 0; $i <= MAX_NUM; ++$i) array_push($tree, 0); function add($pos, $val) { global$tree;
for (; $pos <= MAX_NUM;$pos += $pos & -$pos) {
$tree[$pos] += $val;$tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD; } } function get($pos) {
global $tree;$ret = 0;
for (; $pos;$pos -= $pos & -$pos) {
$ret +=$tree[$pos];$ret -= (int) ($ret / MOD) * MOD; } return$ret;
}

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