POJ. 3691 DNA repair

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

2.Idea
Here

3.Source

 const int MAXK = 1000;  
 const int MAXLEN = 1010;  
 const string AGCT = "AGCT";  
 int nextState[MAXK][4];  
 bool ng[MAXK];  
 int dp[MAXLEN][MAXK];  
 int solve(const vector<string>& ngWords, const string& init) {  
      vector<string> pfx;  
      int n = ngWords.size();  
      // 状態の列挙  
      for (int i = 0; i < n; i++) {  
           string s = ngWords[i];  
           for (int j = 0; j <= (int)s.size(); j++) {  
                pfx.push_back(s.substr(0, j));  
           }  
      }  
      sort(pfx.begin(), pfx.end());  
      pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());  
      int K = pfx.size();  
      // 状態の遷移  
      for (int i = 0; i < K; i++) {  
           for (int j = 0; j < 4; j++) {  
                string s = pfx[i] + AGCT.substr(j, 1);  
                while (1) {  
                     int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();  
                     if (nk < K && pfx[nk] == s) {  
                          nextState[i][j] = nk;  
                          break;  
                     }  
                     s = s.substr(1);  
                }  
           }  
      }  
      // 状態がngかどうか  
      for (int i = 0; i < K; i++) {  
           ng[i] = false;  
           int sl = pfx[i].size();  
           for (int j = 0; j < n; j++) {  
                int wl = ngWords[j].size();  
                if (sl < wl) continue;  
                if (pfx[i].substr(sl - wl) == ngWords[j]) {  
                     ng[i] = true;  
                     break;  
                }  
           }  
      }  
      // dp  
      int length = init.size();  
      for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) {  
           dp[i][k] = INF;  
      }  
      dp[0][0] = 0;  
      for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) {  
           if (dp[l][k] == INF) continue;  
           if (ng[k]) continue;  
           for (int j = 0; j < 4; j++) {  
                int plus = (init[l] == AGCT[j]) ? 0 : 1;  
                int ns = nextState[k][j];  
                if (ng[ns]) continue;  
                dp[l + 1][ns] = min(dp[l][k] + plus, dp[l + 1][ns]);  
           }  
      }  
      int ans = INF;  
      for (int k = 0; k < K; k++) {  
           if (ng[k]) continue;  
           ans = min(ans, dp[length][k]);  
      }  
      if (ans == INF) ans = -1;  
      return ans;  
 }  
 int main() {  
      cin.tie(0);  
      ios::sync_with_stdio(false);  
      int T = 0;  
      int n;  
      while (cin >> n) {  
           if (n == 0) break;  
           T++;  
           vector<string> ngWords;  
           for (int i = 0; i < n; i++) {  
                string s;  
                cin >> s;  
                ngWords.push_back(s);  
           }  
           string init;  
           cin >> init;  
           printf("Case %d: %d\n", T, solve(ngWords, init));  
      }  
      return 0;  
 }  

POJ.3537 Crosses and Crosses

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

2.Idea
Calc grundy

3.Source

 int dp[2001];  
 int grundy(int n) {  
      if (n <= 0) return 0;  
      if (~dp[n]) return dp[n];  
      vector<int> vis(1 << 11);  
      for (int i = 1; i <= n; ++i) {  
           vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;  
      }  
      for (int i = 0; ; ++i) {  
           if (!vis[i]) return dp[n] = i;  
      }  
 }  
 void solve()  
 {  
      std::memset(dp, 0xff, sizeof(dp));  
      int n;  
      cin >> n;  
      cout << (grundy(n) ? 1 : 2) << endl;  
 }  

POJ.2975 Nim

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

2.Idea
Calculate Nim.

3.Source

 int n;  
 int a[1100];  
 void solve()  
 {  
      while (scanf("%d", &n)) {  
           if (n == 0) break;  
           int x = 0;  
           REP(i, n) {  
                scanf("%d", &a[i]);  
                x ^= a[i];  
           }  
           int ans = 0;  
           if (x > 0) {  
                REP(i, n) {  
                     int tmp = x ^ a[i];  
                     if (tmp <= a[i]) ans++;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.1704 Georgia and Bob

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

2.Idea
Using Nim

3.Source

 int n;  
 int p[N];  
 void solve()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           REP(i, n) cin >> p[i];  
           if (n % 2) p[n++] = 0;  
           sort(p, p + n);  
           int x = 0;  
           for (int i = 0; i + 1 < n; i += 2) {  
                x ^= (p[i + 1] - p[i] - 1);  
           }  
           if (x == 0) cout << "Bob will win" << endl;  
           else cout << "Georgia will win" << endl;  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2311 Cutting Game

 1.Problem

http://poj.org/problem?id=2311

2.Idea

Using Grundy number

3.Source

 int W, H;  
 int mem[220][220];  
 int grundy(int w, int h)  
 {  
      if (mem[w][h] != -1) return mem[w][h];  
      set<int> s;  
      for (int i = 2; w - i >= 2; i++) {  
           s.insert(grundy(i, h) ^ grundy(w - i, h));  
      }  
      for (int i = 2; h - i >= 2; i++) {  
           s.insert(grundy(w, i) ^ grundy(w, h - i));  
      }  
      int res = 0;  
      while (s.count(res)) res++;  
      return mem[w][h] = res;  
 }  
 void solve()  
 {  
      memset(mem, -1, sizeof mem);  
      while (scanf("%i%i", &W, &H) > 0) {  
           if (grundy(W, H) != 0) puts("WIN");  
           else puts("LOSE");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2348 Euclid's Game

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

2.Idea
Euclid's

3.Source

 void solve()  
 {  
      while (1) {  
           int a, b;  
           cin >> a >> b;  
           if (a == 0 && b == 0) break;  
           bool f = true;  
           while (1) {  
                if (a > b) swap(a, b);  
                if (b%a == 0) break;  
                if (b - a > a) break;  
                b -= a;  
                f = !f;  
           }  
           if (f) puts("Stan wins");  
           else puts("Ollie wins");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2409 Let it Bead

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

2.Idea
Polya's theorem.

3.Source

 int gcd(int a, int b)  
 {  
      return b == 0 ? a : gcd(b, a%b);  
 }  
 int power(int p, int n)  
 {  
      int ans = 1;  
      while (n)  
      {  
           if (n & 1)  
                ans *= p;  
           p *= p;  
           n /= 2;  
      }  
      return ans;  
 }  
 void solve()  
 {  
      while (1) {  
           int c, s, ans = 0;  
           cin >> c >> s;  
           if (c == 0 && s == 0) break;  
           for (int i = 1; i <= s; i++)  
                ans += power(c, gcd(s, i));  
           if (s & 1)   
                ans += s*power(c, s / 2 + 1);  
           else  
                ans += (power(c, s / 2 + 1) + power(c, s / 2))*(s / 2);  
           ans /= 2 * s;  
           cout << ans << endl;  
      }  
 }  

POJ.1286 Necklace of Beads

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

2.Idea
Polya's theorem.

3.Source

 Int p[110], ans, n;  
 Int gcd(Int a, Int b)  
 {  
      if (!(a%b)) return b;  
      return gcd(b, a%b);  
 }  
 void solve()  
 {  
      int i, j;  
      while (1) {  
           cin >> n;  
           if (n == 0) {  
                cout << 0 << endl;  
                continue;  
           }  
           if (n == -1) return;  
           p[0] = 1;  
           for (int i = 0; i < n; i++) p[i + 1] = p[i] * 3;  
           if (!(n % 2)) ans = (n / 2) * (p[n / 2 + 1] + p[n / 2]);  
           else ans = n * p[n / 2 + 1];  
           for (int i = 1; i <= n; i++) ans += p[gcd(i, n)];  
           ans /= 2 * n;  
           cout << ans << endl;  
      }  
 }  

POJ.2407 Relatives

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

2.Idea
Prime Factorization + Inclusion-exclusion principle

3.Source

 vector<int> a;  
 int n, m;  
 Int gcd(const Int a, const Int b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 void pFac(Int H)  
 {  
      for (Int i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                a.push_back(i);  
           }  
      }  
      if (H > 1) {  
           a.push_back(H);  
      }  
      m = a.size();  
 }  
 void solve()  
 {  
      while (1) {  
           scanf("%lld", &n);  
           if (n == 0) break;  
           a.clear();  
           pFac(n);  
           Int res = 0;  
           for (int i = 1; i < (1 << m); i++) {  
                int num = 0;  
                for (int j = i; j != 0; j >>= 1) {  
                     num += j & 1;  
                }  
                Int lcm = 1;  
                for (int j = 0; j < m; j++) {  
                     if (i >> j & 1) {  
                          lcm = lcm / gcd(lcm, a[j]) * a[j];  
                          if (lcm > n) break;  
                     }  
                }  
                if (num % 2 == 0) res -= n / lcm;  
                else res += n / lcm;  
           }  
           printf("%d\n", n - res);  
      }  
 }  

POJ.3532 Resistance

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

2.Idea
See this blog.

3.Source

 typedef vector<double> vec;  
 typedef vector<vec> mat;  
 double resistor[MAX_N][MAX_N];    
 int N, M;  
 vec gauss(const mat&A, const vec&b) {  
   int n = A.size();//!!!!  
   mat B(n, vec(n + 1));  
   for (int i = 0; i < n; i++)  
     for (int j = 0; j < n; j++)B[i][j] = A[i][j];  
   for (int i = 0; i < n; i++)B[i][n] = b[i];  
   for (int i = 0; i < n; i++) {  
     int pivot = i;  
     for (int j = i; j < n; j++) {  
       if (abs(B[j][i]) > abs(B[pivot][i])) {//!!!  
         pivot = j;  
       }  
     }  
     swap(B[i], B[pivot]);  
     if (abs(B[i][i]) < EPS)return vec(); 
     for (int j = i + 1; j <= n; j++) {  
       B[i][j] /= B[i][i];  
     }  
     for (int j = 0; j < n; j++) {  
       if (i != j) {  
         for (int k = i + 1; k <= n; k++) {  
           B[j][k] -= B[j][i] * B[i][k];  
         }  
       }  
     }  
   }  
   vec x(n);  
   for (int i = 0; i < n; i++) {  
     x[i] = B[i][n];  
   }  
   return x;  
 }  
 int main() {  
   while (scanf("%d%d", &N, &M) != EOF) {  
     memset(resistor, 0, sizeof(resistor));  
     for (int i = 0; i < M; i++) {  
       int from, to;  
       double R;  
       scanf("%d%d%lf", &from, &to, &R);  
       if (R == 0)continue;  
       from--, to--;  
       resistor[from][to] += 1 / R;  
       resistor[to][from] += 1 / R;  
     }  
     for (int i = 0; i < N; i++) {  
       for (int j = 0; j < N; j++) {  
         resistor[i][j] = 1.0 / resistor[i][j];  
       }  
     }  
     mat A(N, vec(N, 0));  
     vec b(N, 0);  
     b[0] = 1.0;  
     b[N - 1] = 0.0;  
     A[0][0] = 1, A[N - 1][N - 1] = 1;  
     for (int i = 1; i < N - 1; i++) {  
       for (int j = 0; j < N; j++) {  
         if (resistor[i][j] > 0) {  
           double I = 1.0 / resistor[i][j];  
           A[i][i] -= I;  
           A[i][j] += I;  
         }  
       }  
     }  
     vec voltage = gauss(A, b);  
     double current = 0;  
     for (int i = 0; i < N; i++) {  
       if (resistor[0][i] > 0) {  
         current += (voltage[0] - voltage[i]) / resistor[0][i];  
       }  
     }  
     printf("%.2f\n", 1.0 / current);  
   }  
   return 0;  
 }