chuka231's blog: July 2020

Sunday, July 12, 2020

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

Friday, July 10, 2020

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

Tuesday, July 7, 2020

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

Monday, July 6, 2020

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

Sunday, July 5, 2020

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

POJ.2345 Central heating

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

2.Idea
Solve the linear equation by Gaussian method.

3.Source

typedef vector vec;
typedef vector mat;
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 (B[j][i] > B[pivot][i]) {//!!!  
                     pivot = j;  
                }  
           }  
           swap(B[i], B[pivot]);  
           if (B[i][i] < EPS)return vec();  
           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 n;  
 void solve()  
 {  
      while (scanf("%d", &n) != EOF) {  
           vec b(n);  
           mat A(n, vec(n));  
           for (int i = 0; i < n; i++) {  
                b[i] = 1;  
           }  
           for (int i = 0; i < n; i++) {  
                while (1) {  
                     int a;  
                     scanf("%d", &a);  
                     if (a == -1) break;  
                     a--;  
                     A[a][i] = 1;  
                }  
           }  
           vec x = gauss(A, b);  
           bool flag = 0;  
           for (int i = 0; i < x.size(); i++) {  
                if (x[i]) {  
                     if (!flag) {  
                          flag = 1;  
                          printf("%d", i + 1);  
                     }  
                     else {  
                          printf(" %d", i + 1);  
                     }  
                }  
           }  
           puts("");  
      }  
 }