2013年3月28日

UVa 531 - Compromise


#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int prev[101][101], first;
vector<string> v1, v2;

void print(int i, int j) {
  if (prev[i][j] == 1) print(i - 1, j - 1);
  else if (prev[i][j] == 2) print(i - 1, j);
  else if (prev[i][j] == 3) print(i, j - 1);
  if (prev[i][j] == 1) printf("%s%s", first ? "" : " ", v1[i].c_str()), first = 0;
}
int main() {
  char voc[99];
  while (scanf("%s", voc) == 1) {
    v1.clear();
    v2.clear();
    v1.push_back("");
    v2.push_back("");
    do {
      v1.push_back(voc);
    } while (scanf("%s", voc) && voc[0] != '#');
    while (scanf("%s", voc) && voc[0] != '#') v2.push_back(voc);
    int dp[101][101] = {};
    memset(prev, 0, sizeof(prev));
    for (int i = 1; i < v1.size(); i++)
      for (int j = 1; j < v2.size(); j++)
        if (v1[i] == v2[j]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
          prev[i][j] = 1;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
          dp[i][j] = dp[i - 1][j];
          prev[i][j] = 2;
        } else {
          dp[i][j] = dp[i][j - 1];
          prev[i][j] = 3;
        }
    first = 1;
    print(v1.size() - 1, v2.size() - 1);
    puts("");
  }
  return 0;
}

UVa 280 - Vertex


#include <stdio.h>
#include <string.h>

int n, d[101][101], v[101];

void find(int now) {
  int i;
  for (i = 1; i <= n; i++)
    if (d[now][i] && !v[i]) {
      v[i] = 1;
      find(i);
    }
}
int main() {
  while (scanf("%d", &n) && n) {
    int i, j;
    memset(d, 0, sizeof(d));
    while (scanf("%d", &i) && i)
      while (scanf("%d", &j) && j)
        d[i][j] = 1;
    scanf("%d", &i);
    while (i--) {
      scanf("%d", &j);
      memset(v, 0, sizeof(v));
      find(j);
      int cnt = 0;
      for (j = 1; j <= n; j++)
        cnt += !v[j];
      printf("%d", cnt);
      for (j = 1; j <= n; j++)
        if (!v[j]) printf(" %d", j);
      puts("");
    }
  }
  return 0;
}

2013年3月24日

UVa 10100 - Longest Match


#include <stdio.h>
#include <string.h>

int max(int a, int b) {
  return a > b ? a : b;
}

int isch(char c) {
  if (c >= '0' && c <= '9') return 1;
  if (c >= 'a' && c <= 'z') return 1;
  if (c >= 'A' && c <= 'Z') return 1;
  return 0;
}

int chk(char * s) {
  int i;
  for (i = 0; s[i]; i++)
    if (!isch(s[i])) return 0;
  return i;
}

char v1[999][999], v2[999][999];

int main() {
  int T = 1;
  char s1[1005], s2[1005];
  while (gets(s1)) {
    gets(s2);
    memset(v1, 0, sizeof(v1));
    memset(v2, 0, sizeof(v2));
    int i, j, n1 = 1, n2 = 1, l = 0;
    for (i = 0; ; i++)
      if (isch(s1[i])) {
        v1[n1][l++] = s1[i];
      } else {
        v1[n1][l] = 0;
        if (chk(v1[n1])) n1++;
        else v1[n1][0] = 0;
        l = 0;
        if (!s1[i]) break;
      }
    for (i = 0; ; i++)
      if (isch(s2[i])) {
        v2[n2][l++] = s2[i];
      } else {
        v2[n2][l] = 0;
        if (chk(v2[n2])) n2++;
        else v2[n2][0] = 0;
        l = 0;
        if (!s2[i]) break;
      }
    int dp[300][300] = {};
    for (i = 1; i <= n1; i++)
      for (j = 1; j <= n2; j++)
        if (!strcmp(v1[i], v2[j]) && chk(v1[i])) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    if (s1[0] && s2[0]) printf("%2d. Length of longest match: %d\n", T++, dp[n1][n2]);
    else printf("%2d. Blank!\n", T++);
  }
  return 0;
}

2013年3月22日

UVa 12049 - Just Prune The List


#include <cstdio>
#include <vector>
#include <algorithm>
using std::vector;
using std::sort;

const int H = 33331;

struct N {
  N (int num, int cnt) : num(num), cnt(cnt) {}
  int num, cnt;
};

void push(int n, vector<N>* v) {
  int i, x = n % H;
  for (i = 0; i < v[x].size(); i++)
    if (v[x][i].num == n) {
      v[x][i].cnt++;
      return;
    }
  v[x].push_back(N(n, 1));
}

int find(int n, vector<N>* v) {
  int i, x = n % H;
  for (i = 0; i < v[x].size(); i++)
    if (v[x][i].num == n) return v[x][i].cnt;
  return 0;
}

int main() {
  int T = 1;
  scanf("%d", &T);
  while (T--) {
    int i, n, m, a[10000], b[10000];
    vector<N> h1[H], h2[H];
    vector<int> all;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
      scanf("%d", a + i);
      push(a[i], h1);
      all.push_back(a[i]);
    }
    for (i = 0; i < m; i++) {
      scanf("%d", b + i);
      push(b[i], h2);
      all.push_back(b[i]);
    }
    sort(all.begin(), all.end());
    int ans = 0;
    for (i = 0; i < all.size(); i++) {
      if (i && all[i] == all[i - 1]) continue;
      int n1 = find(all[i], h1), n2 = find(all[i], h2);
      ans += n1 > n2 ? n1 - n2 : n2 - n1;
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 347 - Run


#include <stdio.h>
#define S 10000005

int num[S];

int rep(int n) {
  int v[10] = {};
  while (n) {
    if (v[n % 10]) return 1;
    if (!(n % 10)) return 1;
    v[n % 10] = 1;
    n /= 10;
  }
  return 0;
}

int chk(int n) {
  if (rep(n)) return 0;
  char s[20];
  sprintf(s, "%d", n);
  int i, l;
  for (l = 0; s[l]; l++);
  int now = 0, cnt = s[0] - '0', v[20] = {};
  for (i = 0; i < l; i++) {
    now = (now + cnt) % l;
    if (v[now]) return 0;
    v[now] = 1;
    cnt = s[now] - '0';
  }
  return 1;
}

int main() {
  int n, C = 1;
  for (n = 9999999; n > 9; n--)
    if (chk(n)) num[n] = n;
    else num[n] = num[n + 1];
  while (scanf("%d", &n) && n)
    printf("Case %d: %d\n", C++, num[n]);
  return 0;
}

2013年3月21日

UVa 166 - Making Change


#include <stdio.h>

int v[6] = {5, 10, 20, 50, 100, 200}, num[6], cost, min;

int need(int n) {
  int i, used = 0;
  for (i = 5; i >= 0; i--)
    if (n >= v[i]) {
      used += n / v[i];
      n = n % v[i];
    }
  return used;
}

void solve(int now, int sum, int used) {
  if (now == 6) {
    if (sum >= cost) {
      used += need(sum - cost);
      if (used < min) min = used;
    }
    return;
  }
  int i;
  for (i = 0; i <= num[now]; i++)
    solve(now + 1, sum + i * v[now], used + i);
}

int main() {
  while (scanf("%d%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4], &num[5]) && (num[0] + num[1] + num[2] + num[3] + num[4] + num[5])) {
    double tmp;
    scanf("%lf", &tmp);
    cost = tmp * 100;
    min = 2e9;
    solve(0, 0, 0);
    printf("%3d\n", min);
  }
  return 0;
}

2013年3月20日

UVa 222 - Budget Travel


#include <stdio.h>

int n;
double target, size, mp, pos[99], price[99], min;

void run(double cost, double loc, double left, double now) {
  if (now == n - 1) {
    left -= (target - loc) / mp;
    if (left >= 0 && cost < min) min = cost;
    return;
  }
  int i;
  for (i = now + 1; i < n; i++)
    if (left * mp >= (pos[i] - loc)) {
      double newLeft = left - (pos[i] - loc) / mp;
      run(cost, pos[i], newLeft, i);
      run(cost + (size - newLeft) * price[i] * 0.01 + 2, pos[i], size, i);
    }
}

int main() {
  int T = 1;
  while (scanf("%lf", &target) && target >= 0) {
    double cost;
    scanf("%lf%lf%lf%d", &size, &mp, &cost, &n);
    int i;
    for (i = 0; i < n; i++)
      scanf("%lf%lf", &pos[i], &price[i]);
    min = 2e9;
    run(cost, 0, size, -1);
    printf("Data Set #%d\nminimum cost = $%.2lf\n", T++, min);
  }
  return 0;
}

2013年3月19日

UVa 10940 - Throwing cards away II


#include <stdio.h>

int main() {
  int n, ans[500005] = {0, 1, 2, 2};
  for (n = 4; n <= 500000; n++) {
    ans[n] = ans[n - 1] + 2;
    if (ans[n] == n) ans[n + 1] = 2, n++;
  }
  while (scanf("%d", &n) && n)
    printf("%d\n", ans[n]);
  return 0;
}

2013年3月18日

UVa 10015 - Joseph's Cousin


#include <cstdio>
#include <vector>

int prime[50000], p[9999], N, ans[9999];

int main() {
  prime[0] = prime[1] = 1;
  for (int i = 0; i < 50000; i++)
    if (!prime[i]) {
      p[N++] = i;
      for (int j = i + i; j < 50000; j += i)
        prime[j] = 1;
    }
  int n;
  for (n = 1; n <= 3501; n++) {
    std::vector<int> v;
    for (int i = 1; i <= n; i++)
      v.push_back(i);
    int now = 0, pos = 0;
    while (v.size() > 1) {
      pos = (pos + p[now++] - 1) % v.size();
      v.erase(v.begin() + pos);
    }
    ans[n] = v[0];
  }
  while (scanf("%d", &n) && n)
    printf("%d\n", ans[n]);
  return 0;
}

2013年3月12日

UVa 341 - Non-Stop Travel


#include <stdio.h>
#include <string.h>

void path(int* prev, int now) {
  if (prev[now] != now) path(prev, prev[now]);
  printf(" %d", now);
}

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    int i, j, k, d, len[100][100];
    memset(len, -1, sizeof(len));
    for (i = 1; i <= n; i++) {
      scanf("%d", &k);
      while (k--) {
        scanf("%d%d", &j, &d);
        len[i][j] = d;
      }
    }
    int start, end;
    scanf("%d%d", &start, &end);
    int dis[100], prev[100], v[100] = {};
    memset(prev, -1, sizeof(prev));
    for (i = 1; i <= n; i++)
      dis[i] = 2e9;
    dis[start] = 0;
    prev[start] = start;
    while (1) {
      int now = -1, min = 2e9;
      for (i = 1; i <= n; i++)
        if (!v[i] && dis[i] < min) min = dis[i], now = i;
      if (now == -1) break;
      v[now] = 1;
      for (i = 1; i <= n; i++)
        if (!v[i] && len[now][i] != -1 && dis[now] + len[now][i] < dis[i]) dis[i] = dis[now] + len[now][i], prev[i] = now;
    }
    printf("Case %d: Path =", C++);
    path(prev, end);
    printf("; %d second delay\n", dis[end]);
  }
  return 0;
}

2013年3月11日

UVa 10044 - Erdos Numbers


#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

void BFS(map<string, int>& d, vector<vector<string> >& v) {
  int i, j, k;
  map<string, set<string> > con;
  for (i = 0; i < v.size(); i++)
    for (j = 0; j < v[i].size(); j++)
      for (k = j + 1; k < v[i].size(); k++) {
        con[v[i][j]].insert(v[i][k]);
        con[v[i][k]].insert(v[i][j]);
      }
  queue<string> q;
  q.push("Erdos,P.");
  d["Erdos,P."] = 0;
  bool find = 0;
  while (!q.empty()) {
    string now = q.front();
    q.pop();
    int dis = d[now];
    for (set<string>::iterator it = con[now].begin(); it != con[now].end(); it++)
      if (!d.count(*it)) {
        q.push(*it);
        d[*it] = dis + 1;
      }
  }
}

int main() {
  int T, C = 1;
  scanf("%d\n", &T);
  while (T--) {
    int p, n, i, j, k;
    scanf("%d %d\n", &p, &n);
    vector<vector<string> > v;
    string s, name;
    while (p--) {
      getline(cin, s);
      for (i = 0; s[i]; i++)
        if (s[i] == ' ') s.erase(s.begin() + i--);
      vector<string> vs;
      for (i = 0, j = 0; ; i++) {
        if (s[i] == ',' || s[i] == ':') {
          j++;
          if (j == 2) {
            vs.push_back(name);
            j = 0;
            name.clear();
            if (s[i] == ':') break;
            continue;
          }
        }
        name.insert(name.end(), s[i]);
      }
      v.push_back(vs);
    }
    map<string, int> d;
    BFS(d, v);
    printf("Scenario %d\n", C++);
    while (n--) {
      getline(cin, s);
      name = s;
      for (i = 0; s[i]; i++)
        if (s[i] == ' ') s.erase(s.begin() + i--);
      if (d.count(s)) printf("%s %d\n", name.c_str(), d[s]);
      else printf("%s infinity\n", name.c_str());
    }
  }
  return 0;
}

2013年3月10日

UVa 10365 - Blocks


#include <stdio.h>

int main() {
  int n, ans[1001];
  for (n = 1; n <= 1000; n++) {
    ans[n] = 2e9;
    int l, w, h;
    for (l = 1; l <= n; l++)
      if (!(n % l)) {
        int temp = n / l;
        for (w = 1; w <= temp; w++)
          if (!(temp % w)) {
            h = temp / w;
            int area = n * 6 - (l - 1) * w * h * 2 - (w - 1) * l * h * 2 - (h - 1) * l * w * 2;
            ans[n] = area < ans[n] ? area : ans[n];
          }
      }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    printf("%d\n", ans[n]);
  }
  return 0;
}

UVa 10677 - Base Equality


#include <cstdio>
#include <string>
using std::string;

int find;

string turn(int n, int b) {
  char s[2];
  s[0] = n % b + '0';
  s[1] = 0;
  if (n) return turn(n / b, b) + s;
  return string(s);
}

void check(int b1, int b2, int n) {
  int i, s1 = 0, s2 = 0;
  string s = turn(n, b1);
  for (i = 0; s[i]; i++) {
    s1 = s1 * b1 + (s[i] - '0');
    s2 = s2 * b2 + (s[i] - '0');
  }
  if ((s2 / s1) * s1 == s2) {
    printf("%d\n", n);
    find = 1;
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int b1, b2, r1, r2;
    scanf("%d%d%d%d", &b1, &b2, &r1, &r2);
    find = 0;
    while (r2 >= r1 && !find)
      check(b1, b2, r2--);
    if (!find) puts("Non-existent.");
  }
  return 0;
}