2014年1月31日

UVa 10212 - The Last Non-zero Digit.

#include <cstdio>
 
const long long MOD = 1e9;

int main() {
  long long N, M;
  while (scanf("%lld%lld", &N, &M) == 2) {
    long long ans = 1;
    for (long long i = 0; i < M; i++) {
      ans = ans * (N - i);
      while (!(ans % 10)) {
        ans /= 10;
      }
      ans %= MOD;
    }
    printf("%lld\n", ans % 10);
  }
  return 0;
}

UVa 10721 - Bar Codes

#include <cstdio>
 
long long dp[51][51][51];

int main() {
  dp[0][0][0] = 1;
  int N, K, M;
  while (scanf("%d%d%d", &N, &K, &M) == 3) {
    long long ans = 0;
    for (int n = 1; n <= N; n++) {
      for (int k = 1; k <= K; k++) {
        for (int last = 1; last <= M; last++) {
          dp[n][k][last] = dp[n - 1][k][last - 1];
          if (last == 1) {
            for (int preLast = 0; preLast <= M; preLast++) {
              dp[n][k][last] += dp[n - 1][k - 1][preLast];
            }
          }
          if (n == N && k == K) {
            ans += dp[n][k][last];
          }
        }
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

UVa 10086 - Test the Rods

#include <cstdio>
 
int main() {
  int T1 ,T2;
  while (scanf("%d%d", &T1, &T2) && (T1 + T2)) {
    int n;
    scanf("%d", &n);
    int num[31], cost[2][31][21];
    for (int i = 1; i <= n; i++) {
      scanf("%d", num + i);
      cost[0][i][0] = cost[1][i][0] = 0;
      for (int j = 1; j <= num[i]; j++) {
        scanf("%d", &cost[0][i][j]);
      }
      for (int j = 1; j <= num[i]; j++) {
        scanf("%d", &cost[1][i][j]);
      }
    }
    int sum = 0, dp[31][301], pick[31][301];
    for (int i = 0; i <= n; i++) {
      for (int t1 = 0; t1 <= T1; t1++) {
        dp[i][t1] = 1e8;
      }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      sum += num[i];
      for (int use = num[i]; use >= 0; use--) {
        for (int t1 = sum < T1 ? sum : T1; t1 >= use; t1--) {
          int value = dp[i - 1][t1 - use] + cost[0][i][use] + cost[1][i][num[i] - use];
          if (value < dp[i][t1]) {
            dp[i][t1] = value;
            pick[i][t1] = use;
          }
        }
      }
    }
    printf("%d\n", dp[n][T1]);
    int i = n, t1 = T1, ans[31];
    while (i) {
      ans[i] = pick[i][t1];
      t1 -= ans[i];
      i--;
    }
    for (int i = 1; i <= n; i++) {
      printf("%d%s", ans[i], i == n ? "\n\n" : " ");
    }
  }
  return 0;
}

UVa 11552 - Fewest Flops

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int price[1111][26][26];
int dp[1111][26];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int K;
    char S[1111];
    scanf("%d%s", &K, S);
    int N = strlen(S) / K;
    vector<int> ch[1111];
    for (int i = 1; i <= N; i++) {
      int rec[26] = {};
      for (int j = (i - 1) * K; j < i * K; j++) {
        rec[S[j] - 'a']++;
      }
      for (int j = 0; j < 26; j++) {
        if (rec[j]) {
          ch[i].push_back(j);
        }
      }
      int type = ch[i].size();
      for (int j = 0; j < type; j++) {
        for (int k = 0; k < type; k++) {
          int h = ch[i][j], t = ch[i][k];
          if (h == t) {
            if (type == 1) {
              price[i][h][t] = 1;
            } else {
              if (rec[h] > 1) {
                price[i][h][t] = type + 1;
              } else {
                price[i][h][t] = 1e8;
              }
            }
          } else {
            price[i][h][t] = type;
          }
        }
      }
    }
    int ans = 1e8;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < ch[i].size(); j++) {
        int t = ch[i][j];
        dp[i][t] = 1e8;
        for (int k = 0; k < ch[i].size(); k++) {
          int h = ch[i][k];
          if (i == 1) {
            dp[i][t] = min(dp[i][t], price[i][h][t]);
          } else {
            for (int l = 0; l < ch[i - 1].size(); l++) {
              int prevT = ch[i - 1][l];
              dp[i][t] = min(dp[i][t], dp[i - 1][prevT] + price[i][h][t] - (prevT == h));
            }
          }
        }
        if (i == N) {
          ans = min(ans, dp[i][t]);
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 11626 - Convex Hull

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct P {

  P (long long x, long long y) : x(x), y(y) {
  }

  bool operator < (const P & other) const {
    return x != other.x ? x < other.x : y < other.y;
  }

  P operator - (const P & other) const {
    return P(x - other.x, y - other.y);  
  }

  long long operator ^ (const P & other) const {
    return x * other.y - y * other.x;
  }

  long long x, y;
};

int orient(P & p1, P & p2, P & p3) {
  long long area = (p2 - p1) ^ (p3 - p1);
  return area == 0 ? 0 : area > 0 ? 1 : -1;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    vector<P> points;
    while (N--) {
      long long x, y;
      char temp[99];
      scanf("%lld%lld%s", &x, &y, temp);
      points.push_back(P(x, y));
    }
    sort(points.begin(), points.end());
    vector<P> ch[2];
    ch[0].push_back(points[0]);
    ch[0].push_back(points[1]);
    for (int i = 2; i < points.size(); i++) {
      ch[0].push_back(points[i]);
      while (ch[0].size() >= 3 && orient(points[i], ch[0][ch[0].size() - 2], ch[0][ch[0].size() - 3]) > 0) {
        ch[0].pop_back();
        ch[0].pop_back();
        ch[0].push_back(points[i]);
      }
    }
    ch[1].push_back(points[points.size() - 1]);
    ch[1].push_back(points[points.size() - 2]);
    for (int i = points.size() - 3; i >= 0; i--) {
      ch[1].push_back(points[i]);
      while (ch[1].size() >= 3 && orient(points[i], ch[1][ch[1].size() - 2], ch[1][ch[1].size() - 3]) > 0) {
        ch[1].pop_back();
        ch[1].pop_back();
        ch[1].push_back(points[i]);
      }
    }
    vector<P> ans;
    for (int i = 0; i < ch[0].size(); i++) {
      ans.push_back(ch[0][i]);
    }
    for (int i = 1; i < ch[1].size() - 1; i++) {
      ans.push_back(ch[1][i]);
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
      printf("%lld %lld\n", ans[i].x, ans[i].y);
    }
  }
  return 0;
}