POJ.3977 Subset

1.Problem
http://poj.org/problem?id=3977

2.Idea
Semi enumeration + Binary search

3.Source (WA code)

 struct Item {  
      ll v;  
      int num;  
      bool operator < (const Item &a)const {  
           return v < a.v;  
      }  
 } A[262149], B[262149];  
 ll a[20];  
 ll b[20];  
 int n, n1, n2, N1, N2;  
 void solve()  
 {  
      for (int i = 0; i < N1; i++) {  
           int k = i;  
           int j = 0;  
           int cnt = 0;  
           ll sum = 0;  
           while (k) {  
                sum += a[j];  
                cnt++;  
                j++;  
                k = k >> 1;  
           }  
           A[i].v = sum;  
           A[i].num = cnt;  
      }  
      for (int i = 0; i < N2; i++) {  
           int k = i;  
           int j = 0;  
           int cnt = 0;  
           ll sum = 0;  
           while (k) {  
                sum += b[j];  
                cnt++;  
                j++;  
                k = k >> 1;  
           }  
           B[i].v = sum;  
           B[i].num = cnt;  
      }  
      sort(A, B + N1);  
      sort(B, B + N2);  
      ll retVal = 1LL << 40 , retNum = 0;  
      for (int i = 0; i < N1; i++) {  
           ll tmp = A[i].v;  
           if (tmp < 0) tmp *= -1;  
           if (A[i].num > 0 && tmp < retVal) {  
                retVal = tmp;  
                retNum = A[i].num;  
           }  
      }  
      for (int i = 0; i < N2; i++) {  
           ll tmp = B[i].v;  
           if (tmp < 0) tmp *= -1;  
           if (B[i].num > 0 && tmp < retVal) {  
                retVal = tmp;  
                retNum = B[i].num;  
           }  
      }  
      for (int i = 0; i < N1; i++) {  
           A[i].v *= -1;  
           int ind = lower_bound(B, B + N2, A[i]) - B;  
           A[i].v *= -1;  
           for (int j = ind-2; j < ind + 2; j++) {  
                if (j >= 0 && j < N2) {  
                     ll tmp = A[i].v + B[j].v;  
                     if (tmp < 0) tmp = -tmp;  
                     ll num = A[i].num + B[j].num;  
                     if (num > 0 && tmp < retVal) {  
                          retVal = tmp;  
                          retNum = num;  
                     }  
                }  
           }  
      }  
      for (int i = 0; i < N2; i++) {  
           B[i].v *= -1;  
           int ind = lower_bound(A, A + N2, B[i]) - A;  
           B[i].v *= -1;  
           for (int j = ind - 2; j < ind + 2; j++) {  
                if (j >= 0 && j < N2) {  
                     ll tmp = B[i].v + A[j].v;  
                     if (tmp < 0) tmp = -tmp;  
                     ll num = B[i].num + A[j].num;  
                     if (num > 0 && tmp < retVal) {  
                          retVal = tmp;  
                          retNum = num;  
                     }  
                }  
           }  
      }  
      printf("%lld %lld\n", retVal, retNum);  
 }  
 int main()  
 {  
      while (scanf("%d", &n), n) {  
           if (n == 1) {  
                ll tmp;  
                cin >> tmp;  
                cout << tmp << " " << 1 << endl;  
                continue;  
           }  
           n1 = n / 2;  
           n2 = (n + 1) / 2;  
           N1 = (int)pow(2.0, n2);  
           N2 = (int)pow(2.0, n2);  
           for (int i = 0; i < n1; i++) {  
                scanf("%lld", &a[i]);  
           }  
           for (int i = 0; i < n2; i++) {  
                scanf("%lld", &b[i]);  
           }  
           solve();  
      }  
      return 0;  
 }  

POJ.2549 Sumsets

1.Problem
http://poj.org/problem?id=2549

2.Idea
Semi-enumeration

3.Source

 #define MAX_N 1000  
 int n;  
 ll a[1003];  
 struct Item {  
      ll v;  
      int s, t;  
      bool operator < (const Item &a)const {  
           return v < a.v;  
      }  
 } ab[MAX_N * MAX_N], cd[MAX_N * MAX_N];  
 void solve()  
 {  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                ab[i*n + j].v = a[i] + a[j];  
                ab[i*n + j].s = i;  
                ab[i*n + j].t = j;  
                cd[i*n + j].v = a[i] - a[j];  
                cd[i*n + j].s = i;  
                cd[i*n + j].t = j;  
           }  
      }  
      ll ans = -1LL << 40;  
      sort(ab, ab + n*n);  
      for (int i = 0; i < n*n; i++) {  
           int j = lower_bound(ab, ab + n*n, cd[i]) - ab;  
           while (j < n*n && ab[j].v == cd[i].v) {  
                if (ab[j].s != ab[j].t &&  
                     cd[i].s != cd[i].t &&  
                     ab[j].s != cd[i].s &&  
                     ab[j].s != cd[i].t &&  
                     ab[j].t != cd[i].s &&  
                     ab[j].t != cd[i].t) {  
                     ans = max(ans, a[cd[i].s]);  
                }  
                j++;  
           }  
      }  
      if (ans == -1LL << 40) cout << "no solution" << endl;  
      else cout << ans << endl;  
 }  
 int main()  
 {  
      while (cin >> n) {  
           if (n == 0) break;  
           for (int i = 0; i < n; i++) cin >> a[i];  
           solve();  
      }  
      return 0;  
 }  

POJ.2785 4 Values whose Sum is 0

1.Problem
http://poj.org/problem?id=2785

2.Idea
Semi-Enumeration

3.Source

 #define MAX_N 4004  
 int n;  
 int A[MAX_N], B[MAX_N], C[MAX_N], D[MAX_N];  
 int CD[MAX_N * MAX_N];  
 void solve()  
 {  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++) {  
                CD[i * n + j] = C[i] + D[j];  
           }  
      sort(CD, CD + n*n);  
      ll res = 0;  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++) {  
                int cd = -(A[i] + B[j]);  
                res += (upper_bound(CD, CD + n*n, cd) - lower_bound(CD, CD + n*n, cd));  
           }  
      printf("%lld\n", res);  
 }  
 int main()  
 {  
      scanf("%d", &n);  
      for (int i = 0; i < n; i++) {  
           scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);  
      }  
      solve();  
      return 0;  
 }  

POJ.2674 Linear world

1.Problem
http://poj.org/problem?id=2674

2.Idea
When 2 animal meets, they exchanges the name and pass thru each other.

3.Source

 #define maxn 32005  
 int dir[maxn];  
 double pos;  
 char name[maxn][300];  
 int n;  
 double len, v;  
 int main()  
 {  
      while (~scanf("%d", &n)) {  
           if (!n) break;  
           scanf("%lf %lf", &len, &v);  
           char ch;  
           int id;  
           double t = -1;  
           for (int i = 0; i < n; i++) {  
                ch = getchar();  
                while (ch == '\n' || ch == ' ') ch = getchar();  
                if (ch == 'p' || ch == 'P')  
                     dir[i] = 1;  
                else dir[i] = -1;  
                scanf("%lf", &pos);  
                scanf("%s", name[i]);  
                double tmp;  
                if (dir[i] == 1)  
                     tmp = (len - pos);  
                else  
                     tmp = pos;  
                if (tmp > t) {  
                     t = tmp;  
                     id = i;  
                }  
           }  
           int cnt = 0;  
           if (dir[id]>0) {  
                for (int i = id + 1; i < n; i++)  
                     if (dir[i]<0)  
                          cnt++;  
           }  
           else {  
                for (int i = id - 1; i >= 0; i--)  
                     if (dir[i]>0)  
                          cnt++;  
           }  
           if (dir[id]>0)  
                id += cnt;  
           else  
                id -= cnt;  
           t = t / v;  
           printf("%13.2lf %s\n", (int)(t * 100) / 100.0, name[id]);  
      }  
      return 0;  
 }  

POJ.3684 Physics Experiment

1.Problem
http://poj.org/problem?id=3684

2.Idea
Assume each of ball is transparent and could pass by one another when collide.

3.Source

 #define MAX_N 111  
 const double g = 10.0;  
 int N, H, R, T;  
 double y[MAX_N];  
 double calc(int T)  
 {  
      if (T < 0) return H;  
      double t = sqrt(2 * H / g);  
      int k = int(T / t);  
      if (k % 2 == 0) {  
           double d = T - k*d;  
           return H - g * d *d / 2;  
      }  
      else {  
           double d = k * t + t - T;  
           return H - g * d *d / 2;  
      }  
 }  
 void solve()  
 {  
      for (int i = 0; i < N; i++) y[i] = calc(T - i);  
      sort(y, y + N);  
      for (int i = 0; i < N; i++) {  
           printf("%.2f%c", y[i] + 2 * R * i / 100.0, i + 1 == N ? '\n' : ' ');  
      }  
 }  
 int main()  
 {  
      int c;  
      cin >> c;  
      while (c--) {  
           cin >> N >> H >> R >> T;  
           solve();  
      }  
      return 0;  
 }  

POJ.2566 Bound Found

1.Problem
http://poj.org/problem?id=2566

2.Idea
Two Pointers

3.Source

 struct Item {  
      int sum;  
      int end;  
      bool operator < (const Item &a)const {  
           return sum < a.sum;  
      }  
 } items[100005];  
 int N, K, T;  
 void solve()  
 {  
      int x, y, s = 0, t = 0, ans = 1000000007, maxn = 1000000007;  
      while (s <= N && t <= N && maxn) {  
           if (s == t) {  
                t++;  
           }  
           else {  
                int sum = items[t].sum - items[s].sum;  
                if (maxn > abs(sum - T)) {  
                     ans = sum;  
                     maxn = abs(sum - T);  
                     x = min(items[s].end, items[t].end) + 1;  
                     y = max(items[s].end, items[t].end);  
                }  
                if (sum > T) {  
                     s++;  
                }  
                if (sum < T) {  
                     t++;  
                }  
           }  
      }  
      printf("%d %d %d\n", ans, x, y);  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &K) > 0, N + K) {  
           items[0].end = 0;  
           items[0].sum = 0;  
           for (int i = 1; i <= N; i++) {  
                int x;  
                scanf("%d", &x);  
                items[i].end = i;  
                items[i].sum = items[i - 1].sum + x;  
           }  
           sort(items, items + N + 1);  
           for (int i = 0; i < K; i++) {  
                scanf("%d", &T);  
                solve();  
           }  
      }  
      return 0;  
 }  

POJ.1222 EXTENDED LIGHTS OUT

1.Problem
http://poj.org/problem?id=1222

2.Idea
Flipping

3.Source

 #define MAX_M 15  
 #define MAX_N 15  
 const int dx[5] = { -1, 0, 0, 0, 1 };  
 const int dy[5] = { 0, -1, 0, 1, 0 };  
 int N, M;  
 int tile[MAX_M][MAX_N];  
 int opt[MAX_M][MAX_N];  
 int flip[MAX_M][MAX_N];  
 int get(int x, int y)  
 {  
      int c = tile[x][y];  
      for (int d = 0; d < 5; d++) {  
           int x2 = x + dx[d], y2 = y + dy[d];  
           if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {  
                c += flip[x2][y2];  
           }  
      }  
      return c % 2;  
 }  
 int calc()  
 {  
      for (int i = 1; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                if (get(i - 1, j) != 0) {  
                     flip[i][j] = 1;  
                }  
           }  
      }  
      for (int j = 0; j < N; j++) {  
           if (get(M - 1, j) != 0) return -1;  
      }  
      int res = 0;  
      for (int i = 0; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                res += flip[i][j];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int res = -1;  
      for (int i = 0; i < 1 << N; i++) {  
           memset(flip, 0, sizeof flip);  
           for (int j = 0; j < N; j++) {  
                flip[0][N - j - 1] = i >> j & 1;  
           }  
           int num = calc();  
           if (num >= 0 && (res < 0 || res > num)) {  
                res = num;  
                memcpy(opt, flip, sizeof(flip));  
           }  
      }  
      if (res < 0) {  
           cout << "IMPOSSIBLE" << endl;  
      }  
      else {  
           for (int i = 0; i < M; i++) {  
                for (int j = 0; j < N; j++)  
                     printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      int T;  
      scanf("%d",&T);  
      for (int t = 1; t <= T; t++) {  
           M = 5;  
           N = 6;  
           for (int i = 0; i < M; i++)  
                for (int j = 0; j < N; j++)  
                     scanf("%d", &tile[i][j]);  
           printf("PUZZLE #%d\n", t);  
           solve();  
      }  
      return 0;  
 }  

POJ.3185 The Water Bowls

1.Problem
http://poj.org/problem?id=3185

2.Idea
Flipping

3.Source

 vector<int> A(20);  
 int solve()  
 {  
      vector<int> a = A;  
      int ans = 0;  
      for (int i = 1; i < 20; i++) {  
           if (a[i - 1] == 1) {  
                //cout << i << endl;  
                a[i - 1] = 1 - a[i - 1];  
                a[i] = 1 - a[i];  
                a[i + 1] = 1 - a[i + 1];  
                ans++;  
           }  
      }  
      return ans;  
 }  
 int main()  
 {  
      for (int i = 0; i < 20; i++) {  
           cin >> A[i];  
      }  
      int ans = solve();  
      reverse(A.begin(), A.end());  
      ans = min(ans, solve());  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3279 Fliptile

1.Problem
http://poj.org/problem?id=3279

2.Idea
Flipping

3.Source

 #define MAX_M 15  
 #define MAX_N 15  
 const int dx[5] = { -1, 0, 0, 0, 1 };  
 const int dy[5] = { 0, -1, 0, 1, 0 };  
 int N, M;  
 int tile[MAX_M][MAX_N];  
 int opt[MAX_M][MAX_N];  
 int flip[MAX_M][MAX_N];  
 int get(int x, int y)  
 {  
      int c = tile[x][y];  
      for (int d = 0; d < 5; d++) {  
           int x2 = x + dx[d], y2 = y + dy[d];  
           if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {  
                c += flip[x2][y2];  
           }  
      }  
      return c % 2;  
 }  
 int calc()  
 {  
      for (int i = 1; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                if (get(i - 1, j) != 0) {  
                     flip[i][j] = 1;  
                }  
           }  
      }  
      for (int j = 0; j < N; j++) {  
           if (get(M - 1, j) != 0) return -1;  
      }  
      int res = 0;  
      for (int i = 0; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                res += flip[i][j];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int res = -1;  
      for (int i = 0; i < 1 << N; i++) {  
           memset(flip, 0, sizeof flip);  
           for (int j = 0; j < N; j++) {  
                flip[0][N - j - 1] = i >> j & 1;  
           }  
           int num = calc();  
           if (num >= 0 && (res < 0 || res > num)) {  
                res = num;  
                memcpy(opt, flip, sizeof(flip));  
           }  
      }  
      if (res < 0) {  
           cout << "IMPOSSIBLE" << endl;  
      }  
      else {  
           for (int i = 0; i < M; i++) {  
                for (int j = 0; j < N; j++)  
                     printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      cin >> M >> N;  
      for (int i = 0; i < M; i++)  
           for (int j = 0; j < N; j++)  
                cin >> tile[i][j];  
      solve();  
      return 0;  
 }  

POJ.3276 Face The Right Way

1.Problem
http://poj.org/problem?id=3276

2.Idea
Flipping method.

3.Source

 #define MAX_N 5000  
 int N;  
 int dir[MAX_N];  
 int f[MAX_N];  
 int calc(int k)  
 {  
      memset(f, 0, sizeof f);  
      int res = 0;  
      int sum = 0;  
      for (int i = 0; i + k <= N; i++) {  
           if ((dir[i] + sum) % 2) {  
                res++;  
                f[i] = 1;  
           }  
           sum += f[i];  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      //residual  
      for (int i = N - k + 1; i < N; i++) {  
           if ((dir[i] + sum) % 2) return -1;  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int K = 1, M = N;  
      for (int k = 1; k <= N; k++) {  
           int m = calc(k);  
           if (m > 0 && M > m) {  
                M = m;  
                K = k;  
           }  
      }  
      cout << K << " " << M << endl;  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {  
           char c;  
           cin >> c;  
           if (c == 'B') dir[i] = 1;  
           else dir[i] = 0;  
      }  
      solve();  
      return 0;  
 }  

POJ.2100 Graveyard Design

1.Problem
http://poj.org/problem?id=2100

2.Idea
Two Pointers

3.Source

 ll S;  
 ll s, t;  
 int n = 10000000;  
 vector<int> ans1, ans2;  
 void solve()  
 {  
      int res = 0;  
      ll s = 0, t = 0;  
      ll sum = 0;  
      for (;;) {  
           while (t < n && sum < S) {  
                sum += t*t; t++;  
           }  
           if (sum < S) break;  
           if (sum == S) {  
                if (s == 0) s++;  
                ans1.push_back(s);  
                ans2.push_back(t - 1);  
           }  
           sum -= s*s;  
           s++;  
      }  
      printf("%d\n", ans1.size());  
      for (int i = 0; i < ans1.size(); i++) {  
           printf("%d", ans2[i] - ans1[i] + 1);  
           for (int j = ans1[i]; j <= ans2[i]; j++) printf(" %d", j);  
           printf("\n");  
      }  
 }  
 int main()  
 {  
      scanf("%lld", &S);  
      n = sqrt(1.0 * S) + 1;  
      solve();  
      return 0;  
 }  

POJ.2739 Sum of Consecutive Prime Numbers

1.Problem
http://poj.org/problem?id=2739

2.Idea
Two Pointers

3.Source

 bool isPrime[10001];  
 bool visited[10001];  
 vector<int> a;  
 int n, S;  
 int s, t;  
 void solve()  
 {  
      int res = 0;  
      int s = 0, t = 0, sum = 0;  
      for (;;) {  
           while (t < n && sum < S) sum += a[t++];  
           if (sum < S) break;  
           if (sum == S) res++;  
           sum -= a[s++];  
      }  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      // get all primes   
      for (int i = 0; i < 10001; i++) isPrime[i] = true;  
      isPrime[0] = isPrime[1] = false;  
      for (int i = 2; i < 10001; i++) {  
           if (isPrime[i]) {  
                a.push_back(i);  
                for (int j = 2 * i; j < 10001; j += i) {  
                     isPrime[j] = false;  
                }  
           }  
      }  
      while (cin >> S)  
      {  
           if (!S) break;  
           n = a.size();  
           solve();  
      }  
      return 0;  
 }  

POJ.3320 Jessica's Reading Problem

1.Problem
http://poj.org/problem?id=3320

2.Idea
Two Pointers method

3.Source

 int P;  
 int a[1000006];  
 void solve()  
 {  
      set<int> all;  
      for (int i = 0; i < P; i++) all.insert(a[i]);  
      int n = all.size();  
      map<int, int> count;  
      int s = 0, t = 0, num = 0, res = P;  
      for (;;) {  
           while (t < P && num < n) {  
                if (count[a[t++]]++ == 0) num++;  
           }  
           if (num < n) break;  
           res = min(res, t - s);  
           if (--count[a[s++]] == 0) {  
                num--;  
           }  
      }  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      scanf("%d", &P);  
      for (int i = 0; i < P; i++) scanf("%d", &a[i]);  
      solve();  
      return 0;  
 }  

POJ.3061 Subsequence

1.Problem
http://poj.org/problem?id=3061

2.Idea
Two Pointers method

3.Source

 int n, S;  
 int a[1000006];  
 void solve()  
 {  
      int res = n + 1;  
      int s = 0, t = 0, sum = 0;  
      for (;;) {  
           while (t < n && sum < S) sum += a[t++];  
           if (sum < S) break;  
           res = min(res, t - s);  
           sum -= a[s++];  
      }  
      if (res > n) res = 0;  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      int t;  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%d%d", &n, &S);  
           for (int i = 0; i < n; i++) scanf("%d", &a[i]);  
           solve();  
      }  
      return 0;  
 }  

POJ.3484 Showstopper

1.Problem
http://poj.org/problem?id=3484

2.Idea
Binary Search

3.Source

 #define MAXN 1000006  
 ll x[MAXN], y[MAXN], z[MAXN];  
 int n;  
 char A[MAXN];  
 bool init() {   
      n = 0;       
      bool f = false;       
      while ((f = (gets_s(A) != NULL)) && strlen(A) > 0)   
      {   
           sscanf(A, "%lld %lld %lld", &x[n], &y[n], &z[n]);  
           n++;   
      }       
      return f || n;   
 }  
 ll C(ll m)  
 {  
      ll sum = 0;  
      for (int i = 0; i < n; i++) {  
           if (m < x[i]) continue;  
           ll t = min(m, y[i]);  
           sum += ((t - x[i]) / z[i] + 1);  
      }  
      return sum;  
 }  
 void solve()  
 {  
      if (n == 0) return;  
      ll l = 0;  
      ll r = 1LL << 32;  
      while (r - l > 1) {  
           ll m = (l + r) / 2;  
           if (C(m) & 1) {  
                r = m;  
           }  
           else {  
                l = m;  
           }  
      }  
      if (r == 1LL << 32) cout << "no corruption" << endl;  
      else cout << r << " " << C(r) - C(r - 1) << endl;  
 }  
 int main()  
 {  
      while (init()) {  
           solve();  
      }  
      return 0;  
 }  

POJ.1759 Garland

1.Problem
http://poj.org/problem?id=1759

2.Idea
Binary_Search by 0<=h[2]<=INF.
h[n+1] = 2 * h[n] - h[n-1] + 2

3.Source

 int N;  
 double A;  
 double B = 1000000000.0;  
 bool C(double x)  
 {  
      double a3, a2, a1;  
      a2 = x;  
      a1 = A;  
      for (int i=0; i < N - 2; i++) {  
           a3 = 2.0 * a2 - a1 + 2.0;  
           if (a3 < 0) return false;  
           a1 = a2;  
           a2 = a3;            
      }  
      if (a2 < B) B = a2;  
      return true;  
 }  
 void solve()  
 {  
      double r = A;  
      double l = 0.0;  
      for(int i=0;i<100;i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                r = m;  
           }  
           else {  
                l = m;  
           }  
      }  
      cout << fixed << std::setprecision(2) << B << endl;  
 }  
 int main()  
 {  
      cin >> N >> A;  
      solve();  
      return 0;  
 }  

POJ.3685 Matrix

1.Problem
http://poj.org/problem?id=3685

2.Idea
Binary Search + Binary Search

3.Source

 #define MAX_N 50010  
 ll N, M;  
 ll getVal(ll i, ll j)  
 {  
      return i*i + 100000 * i + j * j - 100000 * j + i * j;  
 }  
 bool C(ll x)  
 {  
      ll cnt = 0;  
      for (ll j = 1LL; j <= N; j++) {  
           ll l = 0;  
           ll r = N + 1;  
           while (r - l > 1) {  
                ll m = (l + r) / 2;  
                if (getVal(m, j) < x) {  
                     l = m;  
                }  
                else {  
                     r = m;  
                }  
           }  
           cnt += l;  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      ll r = MAX_N * MAX_N * 3 + MAX_N * 100000 * 2;  
      ll l = -r;  
      while(r - l > 1) {  
           ll m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%lld\n", l);  
 }  
 int main()  
 {  
      int t;  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%lld%lld", &N, &M);  
           solve();  
      }  
      return 0;  
 }  

POJ.3579 Median

1.Problem
http://poj.org/problem?id=3579

2.Idea
Binary Search + Lower_Bound

3.Source

 int N;  
 ll M;  
 int x[100005];  
 bool C(int f)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           cnt += lower_bound(x + i + 1, x + N, x[i] + f) - (x + (i + 1));  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      sort(x, x + N);  
      M = (ll)N * (N - 1) / 2;  
      if (M % 2) M = M / 2 + 1;  
      else   M = M / 2;  
      int l = 0;  
      int r = 1000000010;  
      while(r - l > 1) {  
           int m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%d\n", l);  
 }  
 int main()  
 {  
      while (scanf("%d", &N) > 0) {  
           for (int i = 0; i < N; i++) scanf("%d", &x[i]);  
           solve();  
      }  
      return 0;  
 }  

POJ.3111 K Best

1.Problem
http://poj.org/problem?id=3111

2.Idea
Binary Search

3.Source

 int N, K;  
 int v[100005];  
 int w[100005];  
 pair<double, int> y[100005];  
 bool C(double x)  
 {  
      for (int i = 0; i < N; i++) {  
           y[i] = make_pair((double)v[i] - x * (double)w[i], i + 1);  
      }  
      sort(y, y + N);  
      double sum = 0.0;  
      for (int i = N - K; i < N; i++) sum += y[i].first;  
      return sum >= 0;  
 }  
 void solve()  
 {  
      double l = 0.0, r = 100000000.0;  
      for (int i = 0; i < 50; i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      C(l);  
      for (int i = N - K; i < N; i++) {  
           printf("%d ", y[i].second);  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &K);  
      for (int i = 0; i < N; i++) scanf("%d%d", &v[i], &w[i]);  
      solve();  
      return 0;  
 }  

POJ.2976 Dropping tests

1.Problem
http://poj.org/problem?id=2976

2.Idea
Binary Search

3.Source

 int N, K;  
 int a[1003];  
 int b[1003];  
 double y[1003];  
 bool C(double x)  
 {  
      for (int i = 0; i < N; i++) {  
           y[i] = (double)a[i] - x * (double)b[i];  
      }  
      sort(y, y + N);  
      double sum = 0.0;  
      for (int i = K; i < N; i++) sum += y[i];  
      return sum >= 0;  
 }  
 void solve()  
 {  
      double l = 0.0, r = 1.0;  
      for (int i = 0; i < 100; i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      cout << (int)(100.0 * l + 0.5) << endl;  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &K) > 0) {  
           if (N + K == 0) break;  
           for (int i = 0; i < N; i++) cin >> a[i];  
           for (int i = 0; i < N; i++) cin >> b[i];  
           solve();  
      }  
      return 0;  
 }  

POJ.3045 Cow Acrobats

1.Problem
http://poj.org/problem?id=3045

2.Idea
Greedy approach is accepted. Order the cows in (W_i + S_i).

3.Source

 int N;  
 struct Test {  
      ll w, s;  
      bool operator < (const Test &a)const {  
           return w + s < a.w + a.s;  
      }  
 } Tests[50004];  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d%d", &Tests[i].w, &Tests[i].s);  
      sort(Tests, Tests + N);  
      ll ans = -123456789;  
      ll cum = 0;  
      for (int i = 0; i < N; i++) {  
           ll tmp = cum - Tests[i].s;  
           cum += Tests[i].w;  
           ans = max(ans, tmp);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3104 Drying

1.Problem
http://poj.org/problem?id=3104

2.Idea
Binary Search

3.Source

 ll N, K;  
 ll a[100005];  
 ll MaxL = 0;  
 bool C(ll d)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           if (a[i] > d) {  
                cnt += ceil((a[i] - d) * 1.0 / (K - 1));  
           }  
      }  
      return cnt <= d;  
 }  
 void solve()  
 {  
      if (K == 1) {  
           printf("%d\n", MaxL);  
           return;  
      }  
      ll lb = 0, ub = MaxL;  
      while (ub - lb > 1) {  
           //cout << lb << " " << ub << endl;  
           ll mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {   
           scanf("%d", &a[i]);  
           MaxL = max(MaxL, a[i]);  
      }  
      cin >> K;  
      solve();  
      return 0;  
 }  

POJ.3273 Monthly Expense

1.Problem
http://poj.org/problem?id=3273

2.Idea
Binary Search

3.Source

 int N, M;  
 int x[100005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int sum = 0;  
      for (int i = 0; i < N; i++) {  
           if (x[i] > d) return false;  
           else if(sum + x[i] > d){  
                cnt++;  
                sum = x[i];  
           }  
           else {  
                sum += x[i];  
           }  
      }  
      if (cnt < M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      ll lb = 0, ub = 12345678900;  
      while (ub - lb > 1) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) cin >> x[i];  
      solve();  
      return 0;  
 }  

POJ.3258 River Hopscotch

1.Problem
http://poj.org/problem?id=3258

2.Idea
Binary Search

3.Source

 int L, N, M;  
 int x[50005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int last = 0;  
      for (int i = 1; i <= N + 1; i++) {  
           if (x[i] - x[last] < d) {  
                cnt++;  
           }  
           else {  
                last = i;  
           }  
      }  
      if (cnt <= M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      sort(x, x + N + 2);  
      int ans;  
      int lb = 0, ub = L;  
      while (lb <= ub) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) {  
                ans = mid;  
                lb = mid + 1;  
           }  
           else ub = mid - 1;  
      }  
      printf("%d\n", ans);  
 }  
 int main()  
 {  
      cin >> L >> N >> M;  
      for (int i = 1; i <= N; i++) cin >> x[i];  
      x[N + 1] = L;  
      solve();  
      return 0;  
 }  

POJ.1064 Cable master

1.Problem
http://poj.org/problem?id=1064

2.Idea
Binary Search

3.Source

 int N, K;  
 double L[10004];  
 bool C(double x)  
 {  
      int num = 0;  
      for (int i = 0; i < N; i++) {  
           num += (int)(L[i] / x);  
      }  
      return num >= K;  
 }  
 void solve()  
 {  
      double lb = 0, ub = INF;  
      for (int i = 0; i < 100; i++) {  
           double mid = (lb + ub) / 2;  
           if (C(mid)) lb = mid;  
           else ub = mid;  
      }  
      printf("%.2f\n", floor(ub * 100) / 100);  
 }  
 int main()  
 {  
      cin >> N >> K;  
      for (int i = 0; i < N; i++) cin >> L[i];  
      solve();  
      return 0;  
 }  

POJ.2456 Aggressive cows

1.Problem
http://poj.org/problem?id=2456

2.Idea
Binary Search

3.Source

 int N, M;  
 double x[100005];  
 bool C(int d)  
 {  
      int last = 0;  
      for (int i = 1; i < M; i++) {  
           int crt = last + 1;  
           while (crt < N && x[crt] - x[last] < d) {  
                crt++;  
           }  
           if (crt == N) return false;  
           last = crt;  
      }  
      return true;  
 }  
 void solve()  
 {  
      sort(x, x + N);  
      int lb = 0, ub = INF;  
      while (ub - lb > 1) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) lb = mid;  
           else ub = mid;  
      }  
      printf("%d\n", lb);  
 }  
 int main()  
 {  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) cin >> x[i];  
      solve();  
      return 0;  
 }  

POJ.2429 GCD & LCM Inverse

1.Problem
http://poj.org/problem?id=2429

2.Idea
this one was above than my level so quoted a very nice blog here.

3.Source

 #include <iostream>  
 #include <vector>  
 #include <map>  
 #include <cstdlib>  
 using namespace std;  
 typedef long long LL;  
 // return (a * b) % m  
 LL mod_mult(LL a, LL b, LL m) {  
  LL res = 0;  
  LL exp = a % m;  
  while (b) {  
   if (b & 1) {  
    res += exp;  
    if (res > m) res -= m;  
   }  
   exp <<= 1;  
   if (exp > m) exp -= m;  
   b >>= 1;  
  }  
  return res;  
 }  
 // return (a ^ b) % m  
 LL mod_exp(LL a, LL b, LL m) {  
  LL res = 1;  
  LL exp = a % m;  
  while (b) {  
   if (b & 1) res = mod_mult(res, exp, m);  
   exp = mod_mult(exp, exp, m);  
   b >>= 1;  
  }  
  return res;  
 }  
 // ミラー-ラビン素数判定法  
 bool miller_rabin(LL n, LL times) {  
  if (n < 2) return false;  
  if (n == 2) return true;  
  if (!(n & 1)) return false;  
  LL q = n-1;  
  int k = 0;  
  while (q % 2 == 0) {  
   k++;  
   q >>= 1;  
  }  
  // n - 1 = 2^k * q (qは奇素数)  
  // nが素数であれば、下記のいずれかを満たす  
  // (i) a^q ≡ 1 (mod n)  
  // (ii) a^q, a^2q,..., a^(k-1)q のどれかがnを法として-1  
  //  
  // なので、逆に(i)(ii)いずれも満たしていない時は合成数と判定できる  
  //  
  for (int i = 0; i < times; i++) {  
   LL a = rand() % (n-1) + 1; // 1,..,n-1からランダムに値を選ぶ  
   LL x = mod_exp(a, q, n);  
   // (i)をチェック  
   if (x == 1) continue;  
   // (ii)をチェック  
   bool found = false;  
   for (int j = 0; j < k; j++) {  
    if (x == n-1) {  
     found = true;  
     break;  
    }  
    x = mod_mult(x, x, n);  
   }  
   if (found) continue;  
   return false;  
  }  
  return true;  
 }  
 LL get_gcd(LL n, LL m) {  
  if (n < m) swap(n, m);  
  while (m) {  
   swap(n, m);  
   m %= n;  
  }  
  return n;  
 }  
 // ポラード・ロー素因数分解法  
 LL pollard_rho(LL n, int c) {  
  LL x = 2;  
  LL y = 2;  
  LL d = 1;  
  while (d == 1) {  
   x = mod_mult(x, x, n) + c;  
   y = mod_mult(y, y, n) + c;  
   y = mod_mult(y, y, n) + c;  
   d = get_gcd((x-y >= 0 ? x-y : y-x), n);  
  }  
  if (d == n) return pollard_rho(n, c+1);  
  return d;  
 }  
 const int MAX_PRIME = 200000;  
 vector<int> primes;  
 vector<bool> is_prime;  
 // 小さい素数(MAX_PRIMEまで)は先に用意しとく  
 void init_primes() {  
  is_prime = vector<bool>(MAX_PRIME + 1, true);  
  is_prime[0] = is_prime[1] = false;  
  for (int i = 2; i <= MAX_PRIME; i++) {  
   if (is_prime[i]) {  
    primes.push_back(i);  
    for (int j = i*2; j <= MAX_PRIME; j+=i) {  
     is_prime[j] = false;  
    }  
   }  
  }  
 }  
 // 素数かどうか判定。大きければミラーラビンを使う  
 bool isPrime(LL n) {  
  if (n <= MAX_PRIME) return is_prime[n];  
  else return miller_rabin(n, 20);  
 }  
 // 素因数分解する。小さい数は用意した素数で試し割り、大きければポラード・ロー  
 void factorize(LL n, map<LL, int>& factors) {  
  if (isPrime(n)) {  
   factors[n]++;  
  } else {  
   for (int i = 0; i < primes.size(); i++) {  
    int p = primes[i];  
    while (n % p == 0) {  
     factors[p]++;  
     n /= p;  
    }  
   }  
   if (n != 1) {  
    if (isPrime(n)) {  
     factors[n]++;  
    } else {  
     LL d = pollard_rho(n, 1);  
     factorize(d, factors);  
     factorize(n/d, factors);  
    }  
   }  
  }  
 }  
 pair<LL, LL> solve(LL a, LL b) {  
  LL c = b / a;  
  map<LL, int> factors;  
  factorize(c, factors);  
  vector<LL> mult_factors;  
  for (map<LL, int>::iterator it = factors.begin(); it != factors.end(); it++) {  
   LL mul = 1;  
   while (it->second) {  
    mul *= it->first;  
    it->second --;  
   }  
   mult_factors.push_back(mul);  
  }  
  LL best_sum = 1e18, best_x = 1, best_y = c;  
  for (int mask = 0; mask < (1 << mult_factors.size()); mask++) {  
   LL x = 1;  
   for (int i = 0; i < mult_factors.size(); i++) {  
    if (mask & (1 << i)) x *= mult_factors[i];  
   }  
   LL y = c / x;  
   if (x < y && x + y < best_sum) {  
    best_sum = x + y;  
    best_x = x;  
    best_y = y;  
   }  
  }  
  return make_pair(best_x * a, best_y * a);  
 }  
 int main() {  
  cin.tie(0);  
  ios::sync_with_stdio(false);  
  init_primes();  
  LL a, b;  
  while (cin >> a >> b) {  
   pair<LL, LL> ans = solve(a, b);  
   cout << ans.first << " " << ans.second << endl;  
  }  
 }  

POJ.1930 Dead Fraction

1.Problem
http://poj.org/problem?id=1930

2.Idea
All credit to this.

3.Source

 int gcd(const int a, const int b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 static char str[1000];  
 int main()  
 {  
      int sum, last, k, c, i, a, b, div, min_b, min_a, length;  
      while (~scanf("%s", str))  
      {  
           if (strlen(str) == 1 && str[0] == '0')  
                break;  
           sum = 0; length = 0; min_b = INT_MAX;  
           for (i = 2; str[i] != '.'; i++)  
           {  
                sum = sum * 10 + str[i] - '0';  
                length++;  
           }  
           c = (int)pow(10.0, length);  
           for (i = 1, last = sum, k = 1; i <= length; i++)  
           {  
                last /= 10; k *= 10; c /= 10;  
                a = sum - last;  
                b = c*(k - 1);  
                div = gcd(a, b);  
                if (b / div < min_b)  
                {  
                     min_a = a / div;  
                     min_b = b / div;  
                }  
           }  
           printf("%d/%d\n", min_a, min_b);  
      }  
      return 0;  
 }  

POJ.3292 Semi-prime H-numbers

1.Problem
http://poj.org/problem?id=3292

2.Idea
Sieve of Eratosthenes

3.Source

 bool isPrime[1000006];  
 vector<ll> p;  
 int dp[1000006];  
 void prep()  
 {  
      for (int i = 5; i < 1000006; i += 4) {  
           if (!isPrime[i]) {  
                p.push_back(i);  
                for (int j = i * 5; j < 1000006; j += i*4) {  
                     isPrime[j] = true;  
                }  
           }  
      }  
      int n = p.size();  
      for (int i = 0; i < n; i++)  
           for (int j = i; j < n && (p[i] * p[j]) < 1000006; j++) {  
                int k = p[i] * p[j];  
                dp[k] = 1;  
           }  
      for (int i = 1; i < 1000006; i++) {  
           dp[i] += dp[i - 1];  
      }  
 }  
 void solve()  
 {  
      int h;  
      while (1) {  
           cin >> h;  
           if (h == 0) break;  
           cout << h << " " << dp[h] << endl;  
      }  
 }  
 int main()  
 {  
      prep();  
      solve();  
      return 0;  
 }  

POJ.3421 X-factor Chains

1.Problem
http://poj.org/problem?id=3421

2.Idea
Prime number factorize.

3.Source

 ll fac[20];  
 void solve(int x)  
 {  
      map<int, int> res;  
      for (int i = 2; i*i <= x; i++) {  
           while (x%i == 0) {  
                ++res[i];  
                x /= i;  
           }  
      }  
      if (x != 1) res[x] = 1;  
      fac[0] = 1;  
      fac[1] = 1;  
      for (int i = 2; i < 20; i++) {  
           fac[i] = fac[i - 1] * (ll)i;  
      }  
      if (res.size() == 1) {  
           cout << res.begin()->second << " 1" << endl;  
           return;  
      }  
      //calc  
      ll total = 0, dup = 1;  
      for (map<int, int>::iterator itr = res.begin(); itr != res.end(); itr++) {  
           total += itr->second;  
           dup = dup * fac[itr->second];  
      }  
      cout << total << " " << fac[total] / dup << endl;  
 }  
 int main()  
 {  
      int x;  
      while (scanf("%d", &x) > 0) {  
           solve(x);  
      }  
      return 0;  
 }  

POJ.3126 Prime Path

1.Problem
http://poj.org/problem?id=3126

2.Idea
Sieve of Eratosthenes

3.Source

 bool isPrime[10000];  
 bool visited[10000];  
 int n;  
 int s, t;  
 vector<int> GetNei(int cur)  
 {  
      vector<int> ans;  
      for (int i = 0; i < 10; i++) {  
           int tmp = cur - cur % 10 + i;  
           if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);  
           tmp = cur - cur % 100 + cur % 10 + 10 * i;  
           if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);  
           tmp = cur - cur % 1000 + cur % 100 + 100 * i;  
           if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);  
           tmp = cur % 1000 + 1000 * i;  
           if (i > 0 && tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);  
      }  
      return ans;  
 }  
 int solve()  
 {  
      for (int i = 0; i < 10000; i++) isPrime[i] = true;  
      isPrime[0] = isPrime[1] = false;  
      for (int i = 2; i < 10000; i++) {  
           if (isPrime[i]) {  
                for (int j = 2 * i; j < 10000; j += i) {  
                     isPrime[j] = false;  
                }  
           }  
      }  
      cin >> n;  
      while (n--) {  
           memset(visited, 0, sizeof visited);  
           cin >> s >> t;  
           queue<pair<int, int>> q;  
           q.push(make_pair(s, 0));  
           while (!q.empty()) {  
                int cur = q.front().first, d = q.front().second; q.pop();  
                if (cur == t) {  
                     cout << d << endl;  
                     break;  
                }  
                //cout << cur << endl;  
                visited[cur] = true;  
                vector<int> neibors = GetNei(cur);  
                for (int i = 0; i < neibors.size(); i++) {  
                     q.push(make_pair(neibors[i], d + 1));  
                }  
           }  
      }  
 }  
 int main()  
 {  
      solve();  
      return 0;  
 }  

POJ.1995 Raising Modulo Numbers

1.Problem
http://poj.org/problem?id=1995

2.Idea
Fast Power.

3.Source

 ll mod_pow(ll x, ll n, ll mod)  
 {  
      if (n == 0) return 1;  
      ll res = mod_pow(x * x % mod, n / 2, mod);  
      if (n & 1) res = res * x % mod;  
      return res;  
 }  
 int main()  
 {  
      int z;  
      cin >> z;  
      while (z--) {  
           ll sum = 0;  
           ll mod;  
           cin >> mod;  
           int h;  
           cin >> h;  
           for (int i = 0; i < h; i++) {  
                ll a, b;  
                cin >> a >> b;  
                sum = (sum + mod_pow(a, b, mod)) % mod;  
           }  
           cout << sum << endl;  
      }  
      return 0;  
 }  

POJ.3641 Pseudoprime numbers

1.Problem
http://poj.org/problem?id=3641

2.Idea
Prime num check and Fast Power

3.Source

 bool is_prime(ll n)  
 {  
      for (ll i = 2; i*i <= n; i++) {  
           if (n % i == 0) return false;  
      }  
      return n != 1;  
 }  
 ll mod_pow(ll x, ll n, ll mod)  
 {  
      if (n == 0) return 1;  
      ll res = mod_pow(x * x % mod, n / 2, mod);  
      if (n & 1) res = res * x % mod;  
      return res;  
 }  
 int main()  
 {  
      while (true) {  
           ll p, a;  
           cin >> p >> a;  
           if (a + p == 0) break;  
           if (!is_prime(p) && a - mod_pow(a, p, p) == 0) cout << "yes" << endl;  
           else cout << "no" << endl;  
      }  
      return 0;  
 }  

POJ.3268 Silver Cow Party

1.Problem
http://poj.org/problem?id=3268

2.Idea
From X to arbitrary node: Using Dijkstra algorithm
From arbitrary node to X: Reverse all edges direction, and using Dijkstra too.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int from, to, cost; } es[MAX_E];  
 int V, E, X;  
 int cost[MAX_V][MAX_V];  
 int d[MAX_V];  
 int d1[MAX_V];  
 bool used[MAX_V];  
 void dijkstra(int s)  
 {  
      fill(d, d + V, INF);  
      fill(used, used + V, false);  
      d[s] = 0;  
      while (true) {  
           int v = -1;  
           for (int u = 0; u < V; u++) {  
                if (!used[u] && (v == -1 || d[v] > d[u])) v = u;  
           }  
           if (v == -1) break;  
           used[v] = true;  
           for (int u = 0; u < V; u++) {  
                d[u] = min(d[u], d[v] + cost[v][u]);  
           }  
      }  
 }  
 int main()  
 {  
      cin >> V >> E >> X;  
      X--;  
      for (int i = 0; i < V; i++)  
           for (int j = 0; j < V; j++) {  
                if (i == j) cost[i][j] = 0;  
                else cost[i][j] = INF;  
           }  
      for (int i = 0; i < E; i++) {  
           int a, b, t;  
           cin >> a >> b >> t;  
           a--;  
           b--;  
           cost[a][b] = t;  
      }  
      dijkstra(X);  
      for (int i = 0; i < V; i++) d1[i] = d[i];  
      for (int i = 0; i < V; i++)  
           for (int j = i + 1; j < V; j++) {  
                swap(cost[i][j], cost[j][i]);  
           }  
      dijkstra(X);  
      int ans = 0;  
      for (int i = 0; i < V; i++) {  
           ans = max(ans, d1[i] + d[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ. Wormholes

1.Problem
http://poj.org/problem?id=3259

2.Idea
Using Bellman-Ford algorithm to detect negative loop in the graph.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int from, to, cost; } es[MAX_E];  
 int V, E;  
 int d[MAX_V];  
 bool find_negative_loop() //Bellman-Ford  
 {  
      memset(d, 0, sizeof d);  
      for (int i = 0; i < V; i++) {  
           for (int j = 0; j < E; j++) {  
                edge e = es[j];  
                if (d[e.to] > d[e.from] + e.cost) {  
                     d[e.to] = d[e.from] + e.cost;  
                     if (i == V - 1) return true;  
                }  
           }  
      }  
      return false;  
 }  
 int main()  
 {  
      int t;  
      int x, y, z, cnt = 0;  
      cin >> t;  
      while (t--) {  
           int n, m, w;  
           cin >> n >> m >> w;  
           V = n;  
           E = m * 2 + w;  
           cnt = 0;  
           for (int i = 0; i < m; i++) {  
                cin >> x >> y >> z;  
                x--; y--;  
                es[cnt].from = x;  
                es[cnt].to = y;  
                es[cnt].cost = z;  
                cnt++;  
                es[cnt].to = x;  
                es[cnt].from = y;  
                es[cnt].cost = z;  
                cnt++;  
           }  
           for (int i = 0; i < w; i++) {  
                cin >> x >> y >> z;  
                x--; y--;  
                es[cnt].from = x;  
                es[cnt].to = y;  
                es[cnt].cost = -z;  
                cnt++;  
           }  
           if (find_negative_loop()) cout << "YES" << endl;  
           else cout << "NO" << endl;  
      }  
      return 0;  
 }  

POJ.2395 Out of Hay

1.Problem
http://poj.org/problem?id=2395

2.Idea
Minimum Spanning Tree.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      int res = -1;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res = max(res, e.cost);  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      cin >> V >> E;  
      for (int j = 0; j < E; j++) {  
           cin >> es[j].v >> es[j].u >> es[j].cost;  
      }  
      cout << kruskal() << endl;  
      return 0;  
 }  

POJ.2377 Bad Cowtractors

1.Problem
http://poj.org/problem?id=2377

2.Idea
Get maximum spanning tree by Kruskal algorithm.

3.Source

 #define MAX_E 20004  
 #define MAX_V 1011  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost > e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      ll res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += (ll)e.cost;  
           }  
      }  
      set<int> st;  
      for (int i = 0; i < V; i++) {  
           st.insert(find_set(i));  
      }  
      if (st.size() > 1) return -1;  
      return res;  
 }  
 int main()  
 {  
      cin >> V >> E;  
      for (int j = 0; j < E; j++) {  
           cin >> es[j].v >> es[j].u >> es[j].cost;  
      }  
      cout << kruskal() << endl;  
      return 0;  
 }  

POJ.1258 Agri-Net

1.Problem
http://poj.org/problem?id=1258

2.Idea
Minimum Spanning Tree.

3.Source

 #define MAX_E 20004  
 #define MAX_V 111  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      ll res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += e.cost;  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      int tmp;  
      while (cin >> V) {  
           E = 0;  
           for (int i = 0; i < V; i++)  
                for (int j = 0; j < V; j++) {  
                     cin >> tmp;  
                     if (i < j) {  
                          es[E].u = i;  
                          es[E].v = j;  
                          es[E].cost = tmp;  
                          E++;  
                     }  
                }  
           cout << kruskal() << endl;  
      }  
      return 0;  
 }  

POJ.3723 Conscription

1.Problem
http://poj.org/problem?id=3723

2.Idea
Calculating the minimum cost by Kruskal algorithm.

3.Source

 #define MAX_R 50004  
 #define MAX_V 20003  
 struct edge { int u, v, cost; };  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int N, M, R, V, E;  
 edge es[MAX_R];  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      int res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += e.cost;  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> N >> M >> R;  
           V = N + M;  
           E = R;  
           for (int i = 0; i < R; i++) {  
                scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].cost);  
                es[i].v += N;  
                es[i].cost *= -1;  
           }  
           cout << 10000 * V + kruskal() << endl;  
      }  
      return 0;  
 }  

POJ.3169 Layout

1.Problem
http://poj.org/problem?id=3169

2.Idea
This problem is a special case of "Linear programming", which can be solved by graph shortest path problem. Here, Bellman-Ford method is used.

3.Source

 #define MAX_ML 10004  
 #define MAX_MD 10004  
 #define MAX_N 1003  
 int N, ML, MD;  
 int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];  
 int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];  
 int d[MAX_N];  
 void solve()  
 {  
      fill(d, d + N, INF);  
      d[0] = 0;  
      for (int k = 0; k < N; k++) {  
           for (int i = 0; i + 1 < N; i++) {  
                if (d[i + 1] < INF) d[i] = min(d[i], d[i + 1]);  
           }  
           for (int i = 0; i < ML; i++) {  
                if (d[AL[i] - 1] < INF) d[BL[i] - 1] = min(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);  
           }  
           for (int i = 0; i < MD; i++) {  
                if (d[BD[i] - 1] < INF) d[AD[i] - 1] = min(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);  
           }  
      }  
      int res = d[N - 1];  
      if(d[0] < 0) {  
           res = -1;  
      }  
      else if (res == INF) {  
           res = -2;  
      }  
      cout << res << endl;  
 }  
 int main()  
 {  
      cin >> N >> ML >> MD;  
      for (int i = 0; i < ML; i++) {  
           cin >> AL[i] >> BL[i] >> DL[i];  
      }  
      for (int i = 0; i < MD; i++) {  
           cin >> AD[i] >> BD[i] >> DD[i];  
      }  
      solve();  
      return 0;  
 }  

POJ. 2139 Six Degrees of Cowvin Bacon

1.Problem
http://poj.org/problem?id=2139

2.Idea
Calculate all distance between 2 nodes by Warshall-Floyd.

3.Source:

 
 int n, m;  
 int d[333][333];  
 void solve()  
 {  
      //fill(d, d + 333 * 333, INF);  
      for (int k = 0; k < n; k++)  
           for (int i = 0; i < n; i++)  
                for (int j = 0; j < n; j++) {  
                     d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  
                }  
      int ans = INF;  
      for (int i = 0; i < n; i++) {  
           int sum = 0;  
           for (int j = 0; j < n; j++) {  
                sum += d[i][j];  
           }  
           ans = min(ans, sum * 100 / (n - 1));  
      }  
      cout << ans << endl;  
 }  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++) {  
                if (i == j) d[i][j] = 0;  
                else d[i][j] = INF;  
           }  
      for (int i = 0; i < m; i++) {  
           int k;  
           cin >> k;  
           int x[333];  
           for (int j = 0; j < k; j++) {  
                cin >> x[j];  
                x[j]--;  
           }  
           for (int i = 0; i < k; i++)   
                for (int j = i + 1; j < k; j++) {  
                     d[x[i]][x[j]] = d[x[j]][x[i]] = 1;  
                }  
      }  
      solve();  
      return 0;  
 }  

POJ.3255 Roadblocks

1.Problem
http://poj.org/problem?id=3255

2.Idea
Using 2 arrays for the shortest and the second shortest paths while updating by Dijkstra.

3.Source

 #define MAX_N 5000  
 struct edge { int to, cost; };  
 int N, R;  
 vector<edge> G[MAX_N];  
 int dist[MAX_N];  
 int dist2[MAX_N];  
 void solve()  
 {  
      priority_queue<P, vector<P>, greater<P>> que;  
      fill(dist, dist + N, INF);  
      fill(dist2, dist2 + N, INF);  
      dist[0] = 0;  
      que.push(P(0, 0));  
      while (!que.empty()) {  
           P p = que.top(); que.pop();  
           int v = p.second, d = p.first;  
           if (dist2[v] < d) continue;  
           for (int i = 0; i < G[v].size(); i++) {  
                edge e = G[v][i];  
                int d2 = d + e.cost;  
                if (dist[e.to] > d2) {  
                     swap(dist[e.to], d2);  
                     que.push(P(dist[e.to], e.to));  
                }  
                if (dist2[e.to] > d2 && dist[e.to] < d2) {  
                     dist2[e.to] = d2;  
                     que.push(P(dist2[e.to], e.to));  
                }  
           }  
      }  
      cout << dist2[N - 1] << endl;  
 }  
 int main()  
 {  
      cin >> N >> R;  
      for (int i = 0; i < R; i++) {  
           int a, b, d;  
           cin >> a >> b >> d;  
           a--;  
           b--;  
           edge e1; e1.to = b; e1.cost = d;  
           edge e2; e2.to = a; e2.cost = d;  
           G[a].push_back(e1);  
           G[b].push_back(e2);  
      }  
      solve();  
      return 0;  
 }