2014年10月6日

UVa 12467 - Secret Word

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int MAXLEN = 1111111;
const int MOD = 10007;
const int C1 = 17, C2 = 23;
 
int c1[MAXLEN] = {1}, c2[MAXLEN] = {1};
 
char s1[MAXLEN], s2[MAXLEN];
int len;
 
int h1[MAXLEN], h2[MAXLEN];
int h3[MAXLEN], h4[MAXLEN];
 
void rev(char * s) {
  char * f = s, * t = s;
  while (*t) {
    t++;
  }
  t--;
  while (s < t) {
    char temp = *s;
    *s++ = *t;
    *t-- = temp;
  }
}
 
int hash1(int * h, int a, int b) {
  int result = (h[b] - (h[a - 1] * c1[b - a + 1]) % MOD + MOD) % MOD;
  return result;
}
 
int hash2(int * h, int a, int b) {
  int result = (h[b] - (h[a - 1] * c2[b - a + 1]) % MOD + MOD) % MOD;
  return result;
}

int LCP(int l, int lRev) {
  int ans = 0;
  int minLCP = 0, maxLCP = min(len - l + 1, len - lRev + 1);
  while (minLCP <= maxLCP) {
    int midLCP = (minLCP + maxLCP) / 2;
    int left = l, right = l + midLCP - 1;
    int leftRev = lRev, rightRev = leftRev + midLCP - 1;
    if ((hash1(h1, left, right) == hash1(h2, lRev, rightRev)
        && hash2(h3, left, right) == hash2(h4, lRev, rightRev))) {
      ans = max(ans, midLCP);
      minLCP = midLCP + 1;
    } else {
      maxLCP = midLCP - 1;
    }
  }
  return ans;
}
 
int main() {
  for (int i = 1; i < MAXLEN; i++) {
    c1[i] = (c1[i - 1] * C1) % MOD;
    c2[i] = (c2[i - 1] * C2) % MOD;
  }
  gets(s1);
  int T;
  sscanf(s1, "%d", &T);
  while (T--) {
    gets(s1 + 1);
    sprintf(s2 + 1, "%s", s1 + 1);
    rev(s2 + 1);
    len = strlen(s1 + 1);
    h1[0] = h2[0] = 0;
    h3[0] = h4[0] = 0;
    for (int i = 1; s1[i]; i++) {
      h1[i] = (s1[i] + (h1[i - 1] * C1) % MOD) % MOD;
      h2[i] = (s2[i] + (h2[i - 1] * C1) % MOD) % MOD;
 
      h3[i] = (s1[i] + (h3[i - 1] * C2) % MOD) % MOD;
      h4[i] = (s2[i] + (h4[i - 1] * C2) % MOD) % MOD;
    }
    int maxLCP = 0;
    for (int i = 1; s1[i] && (len - i + 1) > maxLCP; ++i) {
      maxLCP = max(maxLCP, LCP(1, i));
    }
    s1[maxLCP + 1] = 0;
    rev(s1 + 1);
    puts(s1 + 1);
  }
  return 0;
}

2014年7月7日

UVa 12488 - Start Grid

#include <stdio.h>

int main() {
  int N;
  while (scanf("%d", &N) == 1) {
    int grid[2][99];
    int i, j, k;
    for (i = 0; i < N; i++) {
      scanf("%d", &grid[0][i]);
    }
    for (i = 0; i < N; i++) {
      scanf("%d", &grid[1][i]);
    }
    int count = 0;
    for (i = N - 1; i >= 0; i--) {
      for (j = 0; j < N; j++) {
        if (grid[0][j] == grid[1][i]) {
          for (k = j; k < i; k++) {
            int temp = grid[0][k + 1];
            grid[0][k + 1] = grid[0][k];
            grid[0][k] = temp;
            count++;
          }
          break;
        }
      }
    }
    printf("%d\n", count);
  }
  return 0;
}

2014年7月6日

UVa 677 - All Walks of length "n" from the first node

#include <cstdio>
#include <vector>

using std::vector;

int N, L;
bool solved;

vector<int> con[10], path;

void solve(int n, int len, bool * visited) {
  if (len == L) {
    solved = true;
    for (int i = 0; i < path.size(); i++) {
      printf("%s%d%s", (i == 0) ? "(" : "", path[i] + 1, (i == path.size() - 1) ? ")" : ",");
    }
    puts("");
    return;
  }
  for (int i = 0; i < con[n].size(); i++) {
    int j = con[n][i];
    if (!visited[j]) {
      visited[j] = true;
      path.push_back(j);
      solve(j, len + 1, visited);
      path.pop_back();
      visited[j] = false;
    }
  }
}

int main() {
  int temp = 0;
  do {
    if (temp) {
      puts("");
    }
    scanf("%d%d", &N, &L);
    for (int r = 0; r < N; r++) {
      con[r].clear();
      for (int c = 0; c < N; c++) {
        int ok;
        scanf("%d", &ok);
        if (ok) {
          con[r].push_back(c);
        }
      }
    }
    solved = false;
    path.clear();
    path.push_back(0);
    bool visited[10] = {true};
    solve(0, 0, visited);
    if (!solved) {
      printf("no walk of length %d\n", L);
    }
  } while (scanf("%d", &temp) == 1);
  return 0;
}

UVa 12700 - Banglawash

#include <stdio.h>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    char s[99];
    scanf("%s", s);
    int i, cnt[99] = {};
    for (i = 0; s[i]; i++) {
      cnt[s[i]]++;
    }
    printf("Case %d: ", C++);
    if (cnt['A'] == N) {
      puts("ABANDONED");
    } else if ((cnt['B'] + cnt['A']) == N) {
      puts("BANGLAWASH");
    } else if ((cnt['W'] + cnt['A']) == N) {
      puts("WHITEWASH");
    } else if (cnt['B'] == cnt['W']) {
      printf("DRAW %d %d\n", cnt['B'], cnt['T']);
    } else if (cnt['B'] > cnt['W']) {
      printf("BANGLADESH %d - %d\n", cnt['B'], cnt['W']);
    } else {
      printf("WWW %d - %d\n", cnt['W'], cnt['B']);
    }
  }
  return 0;
}

2014年2月1日

UVa 11341 - Term Strategy

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, M;
    scanf("%d%d", &N, &M);
    int dp[11][101] = {}, sum = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= M; j++) {
        int grade;
        scanf("%d", &grade);
        for (int w = M; grade >= 5 && w >= j; w--) {
          if ((i == 1 && w == j) || dp[i - 1][w - j]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - j] + grade);
            if (i == N && dp[i][w] > sum) {
              sum = dp[i][w];
            }
          }
        }
      }
    }
    if (sum) {
      printf("Maximal possible average mark - %.2lf.\n", sum / (double)N + 1e-9);
    } else {
      puts("Peter, you shouldn't have played billiard that much.");
    }
  }
  return 0;
}

UVa 11658 - Best Coalitions

#include <cstdio>

int main() {
  int n, x;
  while (scanf("%d%d", &n, &x) && n) {
    int num[101];
    bool dp[10001] = {true};
    for (int i = 1; i <= n; i++) {
      int n1, n2;
      scanf("%d.%d", &n1, &n2);
      num[i] = n1 * 100 + n2;
      if (i == x) {
        continue;
      }
      for (int w = 10000; w >= num[i]; w--) {
        dp[w] |= dp[w - num[i]];
      }
    }
    int sum = 0;
    for (int w = 10000; w >= num[x] && w > 5000; w--) {
      if (dp[w - num[x]]) {
        sum = w;
      }
    }
    printf("%.2lf\n", (num[x] / (double)sum) * 100.0);
  }
  return 0;
}

UVa 10337 - Flight Planner

#include <cstdio>
#include <algorithm>

using namespace std;

int dp[1001][10], w[1000][10];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int X;
    scanf("%d", &X);
    int n = X / 100;
    for (int h = 9; h >= 0; h--) {
      for (int i = 0; i < n; i++) {
        scanf("%d", &w[i][h]);
      }
    }
    for (int i = 0; i <= n; i++) {
      for (int h = 0; h <= 9; h++) {
        if (!i) {
          if (h) {
            dp[i][h] = 1e8;
          }
          continue;
        }
        dp[i][h] = dp[i - 1][h] + 30 - w[i - 1][h];
        if (h != 9) {
          dp[i][h] = min(dp[i][h], dp[i - 1][h + 1] + 20 - w[i - 1][h + 1]);
        }
        if (h != 0) {
          dp[i][h] = min(dp[i][h], dp[i - 1][h - 1] + 60 - w[i - 1][h - 1]);
        }
      }
    }
    printf("%d\n\n", dp[n][0]);
  }
  return 0;
}

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