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;  
 }
Posted by at No comments:
Labels: , ,

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;  
      }  
 }
Posted by at No comments:
Labels: ,

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;  
      }  
 }
Posted by at No comments:
Labels: ,

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);  
      }  
 }
Posted by at No comments:
Labels: ,

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;  
 }
Posted by at No comments:
Labels: ,

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("");  
      }  
 }
Posted by at No comments:
Labels: ,

Friday, July 3, 2020

Dynamic Problems list in AtCoder:

1.Linear DP / １次元状態DP
https://atcoder.jp/contests/abc004/tasks/abc004_4
https://atcoder.jp/contests/abc104/tasks/abc104_d
https://atcoder.jp/contests/abc162/tasks/abc162_f


3.Multi-dimension / DP多次元状態DP
https://atcoder.jp/contests/abc145/tasks/abc145_f
https://atcoder.jp/contests/arc067/tasks/arc067_c
https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d
C - ビーム (atcoder.jp) (Manhattan Distance)


Problem - E - Codeforces (Merge technique)



10.Probability DP / 確率DP

11.Expectation DP / 期待値DP
https://atcoder.jp/contests/dp/tasks/dp_j

  -LCS:最長共通部分列

  -Cadane's Algorithm (Consecutive SubArray):部分和


  -Hashmap (Consecutive SubArray):部分和

  -Brackets Editing: 括弧対応


 -2D Grid Traversal / グリッド探索

 - Cumulative Sum / 累積和

B - Numbers on Papers (atcoder.jp) (PrefixSum, Lower_Bound)


17.Graph DP / グラフ関連

18.Combinatorics / 数え上げ
https://atcoder.jp/contests/dp/tasks/dp_y
C - Kill/Death (atcoder.jp) (Partition Number)

19.Inline DP / インラインDP

20.Memoization / メモ化再帰

21. Binary Lifting / ダブリング

22. Math / 数学

23. Monge-DP

24. Alien-DP

25. Game Theory



Posted by at No comments:
Labels: , ,

Sunday, June 21, 2020

POJ.2115 C Looooops

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

2.Idea
ext gcd

3.Source
 Int a, b, c, k;  
 Int m;  
 // a x + b y = gcd(a, b)  
 Int extgcd(Int a, Int b, Int &x, Int &y) {  
      Int g = a; x = 1; y = 0;  
      if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;  
      return g;  
 }  
 void solve()  
 {  
      while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k) > 0) {  
           if (a == 0 && b == 0 && c == 0 && k == 0) {  
                break;  
           }  
           Int m = (Int)1 << k, x, y;  
           Int g = extgcd(c, m, x, y);  
           if ((b - a) % g) {  
                printf("FOREVER\n");  
           }  
           else {  
                x = (x*((b - a) / g) % (m / g) + (m / g)) % (m / g);  
                printf("%lld\n", x);  
           }  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }
Posted by at No comments:
Labels: ,

Saturday, June 20, 2020

LeetCode.1488 Avoid Flood in The City

1.Problem
https://leetcode.com/contest/weekly-contest-194/problems/avoid-flood-in-the-city/

2.Idea
set lower bound

3.Source
 class Solution {  
 public:  
      vector<int> avoidFlood(vector<int>& rains) {  
           int n = rains.size();  
           vector<int> emt, ans;  
           if (n == 0) return emt;  
           set<int> st;  
           map<int, int> mp;  
           ans.resize(n, -1);  
           for (int i = 0; i < n; i++) {  
                if (rains[i] == 0) {  
                     st.insert(i);  
                }  
                else {  
                     int cur = rains[i];  
                     if (mp.find(cur) == mp.end()) {  
                          mp[cur] = i;  
                     }  
                     else {  
                          if (st.size() == 0) return emt;  
                          set<int>::iterator it = st.lower_bound(mp[cur]);  
                          if (it == st.end()) return emt;  
                          else {  
                               ans[*it] = cur;  
                               st.erase(*it);  
                               mp[cur] = i;  
                          }  
                     }  
                }  
           }  
           for (int i = 0; i < n; i++) {  
                if (rains[i] > 0) ans[i] = -1;  
                else if (ans[i] == -1) ans[i] = 1;  
           }  
           return ans;  
      }  
 };
Posted by at No comments:
Labels: ,

POJ.1284 Primitive Roots

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

2.Idea
Primitive roots, Euler function

3.Source
 int euler[N];  
 void solve()  
 {  
      for (int i = 0; i < N; i++) euler[i] = i;  
      for (int i = 2; i < N; i++) {  
           if (euler[i] == i) {  
                for (int j = i; j < N; j += i) {  
                     euler[j] = euler[j] / i * (i - 1);  
                }  
           }  
      }  
      int p;  
      while (scanf("%d", &p)>0) {  
           printf("%d\n", euler[p - 1]);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }
Posted by at No comments:
Labels: ,
Subscribe to: Posts (Atom)