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