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.2718 Smallest Difference

Problem:
http://poj.org/problem?id=2718

Idea:
Using std.algortihm next_permutation to generate all possible permutations, and only need to check the 2 numbers that you get when splitting the seq in the middle. Also watch out 0 included 2 number cases.

Source:

 int main()  
 {  
      int t;  
      scanf("%d\n", &t);  
      for (int i = 0; i < t; i++) {  
           int ans = 123456789;  
           vector<int> a;  
           char cc;  
           while (cc = getchar()) {  
                if (cc == '\n') break;  
                if (cc >= '0' && cc <= '9') a.push_back((int)(cc - '0'));  
           }  
           int n = a.size();  
           int m = n / 2;  
           sort(a.begin(), a.end());  
           do {                 
                if ( (a[0] == 0 && m-1 > 0) || (a[m] == 0 && m < n-1) ) continue;  
                int num1 = 0;  
                for (int j = 0; j < m; j++) {  
                     num1 = 10 * num1 + a[j];  
                }  
                int num2 = 0;  
                for (int j = m; j < n; j++) {  
                     num2 = 10 * num2 + a[j];  
                }  
                ans = min(ans, abs(num1 - num2));  
           } while (next_permutation(a.begin(), a.end()));  
           cout << ans << endl;  
      }  
      return 0;  
 }  

POJ.3050 Hopscotch

Problem:
http://poj.org/problem?id=3050

Idea:
Using dfs for exhaustive search.

Source:

 #include<cstdio>  
 #include<queue>  
 #include<string>  
 #include<iostream>  
 #include<vector>  
 #include<set>  
 using namespace std;  
 char g[5][5];  
 set<string> ans;  
 int dx[5] = { 0,0,-1,1};  
 int dy[5] = { -1,1,0,0};  
 void dfs(int i, int j, string res, int cur)  
 {  
      if (cur == 6) {  
           ans.insert(res);  
           return;  
      }  
      for (int k = 0; k < 4; k++) {  
           int nx = i + dx[k];  
           int ny = j + dy[k];  
           if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 ) {  
                dfs(nx, ny, res + g[nx][ny], cur + 1);  
           }  
      }  
      return;  
 }  
 int main()  
 {  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                //scanf("%c", &g[i][j]);  
                cin >> g[i][j];  
           }  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                dfs(i, j, "", 0);  
           }  
      cout << ans.size() << endl;  
      return 0;  
 }  

POJ.3187 Backward Digit Sums

Problem Link:
http://poj.org/problem?id=3187

Idea:
Using binomial coeff

Source:

 int n, sum;  
 vector<int> a;  
 int c[10][10];  
 int main()  
 {  
      // calc binom coeff  
      c[0][0] = 1;  
      for (int i = 1; i < 10; i++) {  
           for (int j = 0; j < 10; j++) {  
                if (j == 0) c[i][j] = 1;  
                else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];  
           }  
      }  
      // take input  
      cin >> n >> sum;  
      for (int i = 1; i <= n; i++) {  
           a.push_back(i);  
      }  
      //store ans  
      vector<string> ans;  
      do {  
           int d = 0;  
           for (int i = 0; i < n; i++) {  
                d += c[n - 1][i] * a[i];  
           }  
           if (d == sum) {  
                string str = "";  
                for (int i = 0; i < n; i++) str += (char)(a[i] + 'a' - 1);  
                ans.push_back(str);  
           }  
      } while (next_permutation(a.begin(), a.end()));  
      sort(ans.begin(), ans.end());  
      for (int i = 0; i < n; i++)  
      {  
           cout << (ans[0][i] - 'a' + 1) << " ";  
      }  
      cout << endl;  
      return 0;  
 }