2013年8月31日

UVa 1213 - Sum of Different Primes

#include <cstdio>

const int SIZE = 1121;
bool notP[SIZE];
int p[SIZE], N;

int main() {
  notP[0] = notP[1] = true;
  for (int i = 2; i < SIZE; i++) {
    if (!notP[i]) {
      p[N++] = i;
      for (int j = i + i; j < SIZE; j += i) {
        notP[j] = true;
      }
    }
  }
  int dp[SIZE][15] = {1};
  for (int i = 0; i < N; i++) {
    for (int k = 14; k; k--) {
      for (int j = p[i]; j < SIZE; j++) {
        dp[j][k] += dp[j - p[i]][k - 1];
      }
    }
  }
  int n, k;
  while (scanf("%d%d", &n, &k) && n) {
    printf("%d\n", dp[n][k]);
  }
  return 0;
}

UVa 11856 - Ferry Loading V

Don't assume all of the real number in this problem are bigger than 0.01.
WA + TLE 20times, almost 3 hours...
#include <cstdio>

const int SIZE = 10000;
int index[SIZE], prev[SIZE];

void show(int sum, bool first) {
  if (!sum) {
    return;
  }
  show(prev[sum], false);
  printf("%d%s", index[sum], first ? "\n" : " ");
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    double sum = 0, temp[101];
    for (int i = 1; i <= n; i++) {
      scanf("%lf", &temp[i]);
      sum += temp[i];
    }
    int w[101];
    for (int i = 0; i <= n; i++) {
      w[i] = temp[i] * SIZE / sum;
      prev[i] = 0;
    }
    int limit = SIZE / 2, last = 0;
    bool dp[SIZE / 2] = {true};
    for (int i = 1; i <= n; i++) {
      for (int j = limit; j >= w[i]; j--) {
        if (!dp[j] && dp[j - w[i]]) {
          dp[j] = true;
          prev[j] = j - w[i];
          index[j] = i;
          last = j > last ? j : last;
        }
      }
    }
    show(last, true);
  }
  return 0;
}

UVa 11034 - Ferry Loading IV

#include <cstdio>
#include <queue>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int size, m;
    scanf("%d%d", &size, &m);
    size *= 100;
    queue<int> left, right;
    for (int i = 0; i < m; i++) {
      int len;
      char side[9];
      scanf("%d%s", &len, side);
      if (side[0] == 'l') {
        left.push(len);
      } else {
        right.push(len);
      }
    }
    left.push(1e9);
    right.push(1e9);
    int trip = 0;
    bool l = true;
    while (left.size() + right.size() > 2) {
      int now = 0;
      if (l) {
        while (now + left.front() <= size) {
          now += left.front();
          left.pop();
        }
      } else {
        while (now + right.front() <= size) {
          now += right.front();
          right.pop();
        }
      }
      trip++;
      l = !l;
    }
    printf("%d\n", trip);
  }
  return 0;
}

UVa 10901 - Ferry Loading III

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Car {
  bool operator<(const Car & other) const {
    return id < other.id;
  }
  int id, time;
};

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, t, m;
    scanf("%d%d%d", &n, &t, &m);
    queue<Car> left, right;
    for (int i = 0; i < m; i++) {
      int time;
      char side[9];
      scanf("%d%s", &time, side);
      if (side[0] == 'l') {
        left.push((Car){i, time});
      } else {
        right.push((Car){i, time});
      }
    }
    left.push((Car){m + 1, 2e9});
    right.push((Car){m + 2, 2e9});
    int time = 0;
    bool l = true;
    vector<Car> ans;
    while (left.size() + right.size() > 2) {
      int carry = 0;
      while (l) {
        if (left.front().time > time) {
          if (right.front().time < left.front().time) {
            time = max(time, right.front().time);
            break;
          }
          time = left.front().time;
        }
        while (left.front().time <= time && carry < n) {
          ans.PB((Car){left.front().id, time + t});
          left.pop();
          carry++;
        }
        break;
      }
      while (!l) {
        if (right.front().time > time) {
          if (left.front().time < right.front().time) {
            time = max(time, left.front().time);
            break;
          }
          time = right.front().time;
        }
        while (right.front().time <= time && carry < n) {
          ans.PB((Car){right.front().id, time + t});
          right.pop();
          carry++;
        }
        break;
      }
      time += t;
      l = !l;
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
      printf("%d\n", ans[i].time);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 10440 - Ferry Loading II

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, t, m;
    scanf("%d%d%d", &n, &t, &m);
    int times[1999];
    for (int i = 0; i < m; i++) {
      scanf("%d", &times[i]);
    }
    sort(times, times + m);
    bool first = m % n;
    int carry = 0, time = 0, trip = 0;
    for (int i = 0; i < m; i++) {
      if (time <= times[i]) {
        time = times[i];
      }
      carry++;
      if (!first) {
        if (carry == n) {
          carry = 0;
          time += t + t;
          trip++;
        }
      } else if (carry == (m % n)) {
        first = false;
        carry = 0;
        time += t + t;
        trip++;
      }
    }
    printf("%d %d\n", time - t, trip);
  }
  return 0;
}

UVa 10261 - Ferry Loading

#include <cstdio>
#include <cstring>

bool left[2001][10001];
int l[2001], prev[2001][10001];

void show(int now, int len) {
  if (!now) {
    return;
  }
  show(now - 1, prev[now][len]);
  puts(prev[now][len] == len ? "starboard" : "port");
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    n *= 100;
    memset(left, false, sizeof(left));
    left[0][0] = true;
    int now = 1, sum = 0, last = 0, len;
    while (scanf("%d", &l[now]) && l[now]) {
      sum += l[now];
      for (int i = 0; i <= n; i++) {
        if (sum - i <= n && left[now - 1][i]) {
          left[now][i] = true;
          prev[now][i] = i;
          last = now;
          len = i;
        } else if (i >= l[now] && left[now - 1][i - l[now]]) {
          left[now][i] = true;;
          prev[now][i] = i - l[now];
          last = now;
          len = i;
        }
      }
      now++;
    }
    printf("%d\n", last);
    show(last, len);
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 12563 - Jin Ge Jin Qu hao

#include <cstdio>
#include <map>
using namespace std;

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int n, t;
    scanf("%d%d", &n, &t);
    map<int, int> dp;
    dp[0] = 0;
    int maxTime = 0, maxLen = 0;
    for (int i = 0; i < n; i++) {
      int l;
      scanf("%d", &l);
      map<int, int> next = dp;
      for (map<int, int>::iterator it = dp.begin(); it != dp.end(); it++) {
        int len = it->first, times = it->second;
        if (l + len < t) {
          next[l + len] = max(next[l + len], times + 1);
          if ((times + 1) > maxTime || ((times + 1) == maxTime && (l + len) > maxLen)) {
            maxTime = times + 1;
            maxLen = l + len;
          }
        }
      }
      dp = next;
    }
    printf("Case %d: %d %d\n", C++, maxTime + 1, maxLen + 678);
  }
  return 0;
}

UVa 12619 - Just Make A Wish

Referecne : http://mypaper.pchome.com.tw/zerojudge/post/1324552689
#include <cstdio>

typedef unsigned long long ULL;
const ULL MOD = 1000000007;
const int SIZE = 1000000 + 1;

bool notP[SIZE];
int indexOfP[SIZE], p[SIZE / 10], N;

ULL power(ULL n, ULL e) {
  if (!e) {
    return 1;
  }
  return (((e & 1) ? n : 1) * (power((n * n) % MOD, e >> 1))) % MOD;
}

int main() {
  notP[0] = notP[1] = true;
  for (int i = 2; i < SIZE; i++) {
    if (!notP[i]) {
      p[N] = i;
      indexOfP[i] = N++;
      for (int j = i + i; j < SIZE; j += i) {
        notP[j] = true;
      }
    }
  }
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int D;
    scanf("%d", &D);
    ULL times[SIZE / 10] = {}, ans = 0, sum = 1;
    while (D--) {
      int G;
      bool minus = false;
      scanf("%d", &G);
      if (G < 0) {
        G = -G;
        minus = true;
      }
      for (int j = 0; j < N && notP[G] && G >= p[j]; j++) {
        ULL time = 0;
        while (!(G % p[j])) {
          G /= p[j];
          time++;
        }
        if (time) {
          sum = (sum * power(times[j] + 1, MOD - 2)) % MOD;
          times[j] += time * (minus ? -1 : 1);
          sum = (sum * (times[j] + 1)) % MOD;
        }
      }
      if (!notP[G]) {
        int j = indexOfP[G];
        ULL temp = times[j];
        sum = (sum * power(times[j] + 1, MOD - 2)) % MOD;
        times[j] += minus ? -1 : 1;
        sum = (sum * (times[j] + 1)) % MOD;

      }
      ans = (ans + sum) % MOD;
    }
    printf("Case %d: %llu\n", C++, ans);
  }

  return 0;
}

UVa 10306 - e-Coins

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int m, s;
    scanf("%d%d", &m, &s);
    int dp[301][301];
    for (int j = 0; j <= s; j++) {
      for (int k = 0; k <= s; k++) {
        dp[j][k] = 1e7;
      }
    }
    dp[0][0] = 0;
    while (m--) {
      int x, y;
      scanf("%d%d", &x, &y);
      for (int j = x; j <= s; j++) {
        for (int k = y; k <= s; k++) {
          dp[j][k] = min(dp[j][k], dp[j - x][k - y] + 1);
        }
      }
    }
    int ans = 1e7;
    for (int j = 0; j <= s; j++) {
      for (int k = 0; k <= s; k++) {
        if (j * j + k * k == s * s) {
          ans = min(ans, dp[j][k]);
        }
      }
    }
    if (ans >= 1e7) {
      puts("not possible");
    } else {
      printf("%d\n", ans);
    }
  }
  return 0;
}

UVa 10637 - Coprimes

#include <cstdio>

int gcd(int a, int b) {
  while ((a %= b) && (b %= a));
  return a + b;
}

void solve(int s, int t, int last, int now, int * ans) {
  if (!s && now == t) {
    for (int i = 0; i < t; i++) {
      printf("%d%s", ans[i], i == t - 1 ? "\n" : " ");
    }
    return;
  }
  if (!s || now == t) {
    return;
  }
  for (int i = last; i <= s; i++) {
    bool ok = true;
    for (int j = 0; j < now && ok; j++) {
      ok = (gcd(i, ans[j]) == 1);
    }
    if (ok) {
      ans[now] = i;
      solve(s - i, t, i, now + 1, ans);
    }
  }
}

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    printf("Case %d:\n", C++);
    int s, t, ans[99];
    scanf("%d%d", &s, &t);
    solve(s, t, 1, 0, ans);
  }
  return 0;
}

2013年8月30日

UVa 10128 - Queue

#include <cstdio>

int main() {
  int dp[19][19][19] = {};
  dp[1][1][1] = 1;
  for (int n = 2; n <= 13; n++) {
    for (int l = 1; l <= 13; l++) {
      for (int r = 1; r <= 13; r++) {
        dp[n][l][r] = dp[n - 1][l][r] * (n - 2) + dp[n - 1][l - 1][r] + dp[n - 1][l][r - 1];
      }
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, l, r;
    scanf("%d%d%d", &n, &l, &r);
    printf("%d\n", dp[n][l][r]);
  }
  return 0;
}

UVa 227 - Puzzle

WA + RE for almost 20 times on this easy problem, only beacuse of this code.
while (gets(puzzle[0]) && puzzle[0][1]) {
  if (!first) {
    puts("");
  }
  first = false;
  int sr = -1, sc;
  for (int r = 1; r < 5; r++) {
    gets(puzzle[r]);
    for (int c = 0; c < 5; c++) {
      if (puzzle[r][c] == ' ') {
        sr = r;
        sc = c;
      }
    }
I forgot to check the space in row 0 Orz.
#include <cstdio>
#include <cstring>

inline bool check(int r, int c) {
  return (r >= 0) && (r < 5) && (c >= 0) && (c < 5);
}

int main() {
  int dr[128], dc[128];
  dr['A'] = -1, dc['A'] = 0;
  dr['B'] = 1, dc['B'] = 0;
  dr['L'] = 0, dc['L'] = -1;
  dr['R'] = 0, dc['R'] = 1;
  char puzzle[9][9];
  int C = 1;
  while (gets(puzzle[0]) && puzzle[0][1]) {
    if (C > 1) {
      puts("");
    }
    int sr = -1, sc;
    for (int r = 1; r < 5; r++) {
      gets(puzzle[r]);
    }
    for (int r = 0; r < 5; r++) {
      for (int c = 0; c < 5; c++) {
        if (puzzle[r][c] == ' ') {
          sr = r;
          sc = c;
        }
      }
    }
    bool legal = true;
    char ch;
    while (ch = getchar()) {
      if (ch == ' ' || ch == '\n') {
        continue;
      } else if (ch == '0') {
        getchar();
        break;
      } else if (ch != 'A' && ch != 'B' && ch != 'L' && ch != 'R') {
        legal = false;
      } else if (legal) {
        int nr = sr + dr[ch], nc = sc + dc[ch];
        if (check(nr, nc)) {
          puzzle[sr][sc] = puzzle[nr][nc];
          puzzle[nr][nc] = ' ';
          sr = nr;
          sc = nc;
        } else {
          legal = false;
        }
      }
    }
    printf("Puzzle #%d:\n", C++);
    if (legal) {
      for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
          printf("%c%s", puzzle[r][c], c == 4 ? "\n" : " ");
        }
      }
    } else {
      puts("This puzzle has no final configuration.");
    }
  }
  return 0;
}

UVa 109 - SCUD Busters

Reference : http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html#6
#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

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

typedef vector<P> Kingdom;

int cross(P o, P a, P b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

Kingdom convexHull(Kingdom & k) {
  sort(k.begin(), k.end());
  P CH[100];
  int m = 0;
  for (int i = 0; i < k.size(); i++) {
    while (m >= 2 && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
      m--;
    }
    CH[m++] = k[i];
  }
  for (int i = k.size() - 2, t = m + 1; i >= 0; i--) {
    while (m >= t && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
      m--;
    }
    CH[m++] = k[i];
  }
  return Kingdom(CH, CH + m);
}

int area(Kingdom & k) {
  int sum = 0;
  for(int i = 1; i < k.size(); i++) {
    sum += (k[i - 1].x * k[i].y) - (k[i].x * k[i - 1].y);
  }
  return sum;
}

bool in(P p, Kingdom & k) {
  int sum = area(k);
  for (int i = 1; i < k.size() && sum >= 0; i++) {
    Kingdom temp;
    temp.PB(p);
    temp.PB(k[i - 1]);
    temp.PB(k[i]);
    temp.PB(p);
    int tempSum = area(temp);
    if (tempSum < 0) {
      return false;
    }
    sum -= tempSum;
  }
  return sum == 0;
}

int main() {
  vector<Kingdom> v;
  int n, x, y;
  while (scanf("%d", &n) && n != -1) {
    Kingdom k;
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &x, &y);
      k.PB((P){x, y});
    }
    v.PB(convexHull(k));
  }
  vector<bool> over(v.size(), false);
  while (scanf("%d%d", &x, &y) == 2) {
    for (int i = 0; i < v.size(); i++) {
      if (!over[i]) {
        over[i] = in((P){x, y}, v[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < v.size(); i++) {
    if (over[i]) {
      ans += area(v[i]);
    }
  }
  printf("%.2lf\n", ans * 0.5);
  return 0;
}

UVa 707 - Robbery

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> PP;

const int dr[5] = {1, 0, -1, 0, 0};
const int dc[5] = {0, 1, 0, -1, 0};

int R, C, T, Case = 1;

bool block[111][111][111];
int times[111][111][111];
bool vis[111][111][111];

inline bool check(int r, int c) {
  return (r >= 1) && (r <= R) && (c >= 1) && (c <= C);
}

void solve(PP & init) {
  memset(vis, false, sizeof(vis));
  vector<P> possible[111];
  queue<PP> q;
  q.push(init);
  while (!q.empty()) {
    int t = q.front().first;
    P now = q.front().second;
    q.pop();
    possible[t].PB(now);
    if (t == 1) {
      continue;
    }
    for (int d = 0; d < 5; d++) {
      int nr = now.first + dr[d], nc = now.second + dc[d];
      if (check(nr, nc) && times[t - 1][nr][nc]) {
        if (!vis[t - 1][nr][nc]) {
          q.push(MP(t - 1, MP(nr, nc)));
          vis[t - 1][nr][nc] = true;
        }
      }
    }
  }
  for (int t = 1; t <= T; t++) {
    if (possible[t].size() == 1) {
      P & now = possible[t][0];
      printf("Time step %d: The robber has been at %d,%d.\n", t, now.second, now.first);
    }
  }
}

int main() {
  while (scanf("%d%d%d", &C, &R, &T) && R) {
    memset(block, false, sizeof(block));
    printf("Robbery #%d:\n", Case++);
    int n;
    scanf("%d", &n);
    while (n--) {
      int t, c1, r1, c2, r2;
      scanf("%d%d%d%d%d", &t, &c1, &r1, &c2, &r2);
      for (int r = r1; r <= r2; r++) {
        for (int c = c1; c <= c2; c++) {
          block[t][r][c] = true;
        }
      }
    }
    memset(times, 0, sizeof(times));
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        if (!block[1][r][c]) {
          times[1][r][c] = 1;
        }
      }
    }
    for (int t = 2; t <= T; t++) {
      for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
          if (!block[t][r][c]) {
            for (int d = 0; d < 5; d++) {
              int nr = r + dr[d], nc = c + dc[d];
              if (check(nr, nc)) {
                times[t][r][c] += times[t - 1][nr][nc];
              }
            }
          }
        }
      }
    }
    bool found = false;
    for (int t = T; t >= 1 && !found; t--) {
      int cnt = 0;
      PP last;
      for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
          if (times[t][r][c]) {
            cnt++;
            last = MP(t, MP(r, c));
          }
        }
      }
      if (cnt == 1) {
        found = true;
        solve(last);
      } else if (!cnt) {
        found = true;
        puts("The robber has escaped.");
      }
    }
    if (!found) {
      puts("Nothing known.");
    }
    puts("");
  }
  return 0;
}

2013年8月29日

UVa 10891 - Game of Sum

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int num[101], sum[101] = {}, dp[101][101];
    for (int i = 1; i <= n; i++) {
      scanf("%d", &num[i]);
      sum[i] = sum[i - 1] + num[i];
      dp[i][i] = num[i];
    }
    for (int l = 2; l <= n; l++) {
      for (int i = 1; i + l - 1 <= n; i++) {
        int j = i + l - 1;
        int s = sum[j] - sum[i - 1];
        dp[i][j] = s;
        for (int k = i; k < j; k++) {
          dp[i][j] = max(dp[i][j], s - min(dp[i][k], dp[k + 1][j]));
        }
      }
    }
    printf("%d\n", dp[1][n] - (sum[n] - dp[1][n]));
  }
  return 0;
}

UVa 12135 - Switch Bulbs

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    int mask[40] = {};
    for (int i = 0; i < m; i++) {
      int k;
      scanf("%d", &k);
      while (k--) {
        int id;
        scanf("%d", &id);
        mask[i] |= (1 << id);
      }
    }
    int dis[1 << 15];
    memset(dis, -1, sizeof(dis));
    dis[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int now = q.front();
      q.pop();
      for (int i = 0; i < m; i++) {
        int next = now ^ mask[i];
        if (dis[next] == -1) {
          dis[next] = dis[now] + 1;
          q.push(next);
        }
      }
    }
    printf("Case %d:\n", C++);
    int ask;
    scanf("%d", &ask);
    while (ask--) {
      char s[99];
      scanf("%s", s);
      int state = 0;
      for (int i = 0; s[i]; i++) {
        state = (state << 1) + s[i] - '0';
      }
      printf("%d\n", dis[state]);
    }
    puts("");
  }
  return 0;
}

UVa 321 - The New Villa

#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

int main() {
  int r, d, s, C = 1;
  while (scanf("%d%d%d", &r, &d, &s) && r) {
    vector<int> con[11];
    while (d--) {
      int a, b;
      scanf("%d%d", &a, &b);
      con[a].PB(b);
      con[b].PB(a);
    }
    vector<int> sw[11];
    while (s--) {
      int a, b;
      scanf("%d%d", &a, &b);
      sw[a].PB(b);
    }
    printf("Villa #%d\n", C++);
    queue<P> q;
    vector<string> path[11][1024];
    q.push(MP(1, 1));
    bool solved = false;
    while (!q.empty()) {
      P now = q.front();
      q.pop();
      int a = now.first, state = now.second;
      vector<string> & p = path[a][state];
      if (a == r && state == (1 << (r - 1))) {
        printf("The problem can be solved in %d steps:\n", p.size());
        for (int i = 0; i < p.size(); i++) {
          printf("%s\n", p[i].c_str());
        }
        solved = true;
        break;
      }
      for (int i = 0; i < con[a].size(); i++) {
        int b = con[a][i];
        if ((state & (1 << (b - 1))) && !path[b][state].size()) {
          char temp[99];
          sprintf(temp, "- Move to room %d.", b);
          path[b][state] = p;
          path[b][state].PB(temp);
          q.push(MP(b, state));
        }
      }
      for (int i = 0; i < sw[a].size(); i++) {
        int b = sw[a][i];
        if (a == b) {
          continue;
        }
        int newState = state ^ (1 << (b - 1));
        if (!path[a][newState].size()) {
          char temp[99];
          sprintf(temp, "- Switch %s light in room %d.", (state & (1 << (b - 1))) ? "off" : "on", b);
          path[a][newState] = p;
          path[a][newState].PB(temp);
          q.push(MP(a, newState));
        }
      }
    }
    if (!solved) {
      puts("The problem cannot be solved.");
    }
    puts("");
  }
  return 0;
}

UVa 589 - Pushing Boxes

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

struct State {
  State(P box, P now, int push, string path) : box(box), now(now), push(push), path(path) {}
  bool operator<(const State & other) const {
    if (push != other.push) {
      return push > other.push;
    }
    return path.length() > other.path.length();
  }
  P box, now;
  int push;
  string path;
};

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};
const string d1[4] = {"s", "e", "n", "w"};
const string d2[4] = {"S", "E", "N", "W"};

int R, C;
char maze[22][22];

inline bool check(int r, int c) {
  return (r >= 0) && (r < R) && (c >= 0) && (c < C) && (maze[r][c] == '.');
}

bool vis[22][22][22][22][100];

void BFS(const State & init, const P & target) {
  memset(vis, false, sizeof(vis));
  vis[init.box.first][init.box.second][init.now.first][init.now.second][0] = true;

  priority_queue<State> q;
  q.push(init);

  int minPush = 1e9;
  string ans;
  while (!q.empty()) {
    State state = q.top();
    P box = state.box, now = state.now;
    int push = state.push;
    string path = state.path;
    q.pop();
    if (box == target) {
      if (push < minPush) {
        minPush = push;
        ans = path;
      } else if (push == minPush) {
        if (path.length() < ans.length()) {
          ans = path;
        }
      } else {
        break;
      }
      continue;
    }
    int br = box.first, bc = box.second;
    int r = now.first, c = now.second;
    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d], nc = c + dc[d];
      if (!check(nr, nc)) {
        continue;
      }
      if (nr == br && nc == bc) {
        int nbr = br + dr[d], nbc = bc + dc[d];
        if (check(nbr, nbc)) {
          if (!vis[nbr][nbc][nr][nc][ans.length() + 1]) {
            vis[nbr][nbc][nr][nc][ans.length() + 1] = true;
            q.push(State(MP(nbr, nbc), MP(nr, nc), push + 1, path + d2[d]));
          }
        }
      } else {
        if (!vis[br][bc][nr][nc][ans.length() + 1]) {
          vis[br][bc][nr][nc][ans.length() + 1] = true;
          q.push(State(box, MP(nr, nc), push, path + d1[d]));
        }
      }
    }
  }
  puts(ans.length() ? ans.c_str() : "Impossible.");
}

int main() {
  int Case = 1;
  while (scanf("%d%d", &R, &C) && R) {
    P b, s, t;
    for (int r = 0; r < R; r++) {
      scanf("%s", maze[r]);
      for (int c = 0; maze[r][c]; c++) {
        if (maze[r][c] == 'B') {
          maze[r][c] = '.';
          b = MP(r, c);
        } else if (maze[r][c] == 'S') {
          maze[r][c] = '.';
          s = MP(r, c);
        } else if (maze[r][c] == 'T') {
          maze[r][c] = '.';
          t = MP(r, c);
        }
      }
    }
    printf("Maze #%d\n", Case++);
    BFS(State(b, s, 0, ""), t);
    puts("");
  }
  return 0;
}

2013年8月28日

UVa 1437 - String painter

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
  char s1[111], s2[111];
  while (gets(s1)) {
    gets(s2);
    int dp[111][111] = {};
    for (int j = 0; s1[j]; j++) {
      for (int i = j; i >= 0; i--) {
        dp[i][j] = dp[i + 1][j] + 1;
        for (int k = i + 1; k <= j; k++) {
          if (s2[i] == s2[k]) {
            dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);
          }
        }
      }
    }
    int need[111];
    for (int i = 0; s1[i]; i++) {
      if (s1[i] == s2[i]) {
        need[i] = i ? need[i - 1] : 0;
        continue;
      }
      need[i] = dp[0][i];
      for (int j = 0; j < i; j++) {
        need[i] = min(need[i], need[j] + dp[j + 1][i]);
      }
    }
    printf("%d\n", need[strlen(s1) - 1]);
  }
  return 0;
}

UVa 926 - Walking Around Wisely

#include <cstdio>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int sr, sc, er, ec;
    scanf("%d%d%d%d", &sc, &sr, &ec, &er);
    int W;
    scanf("%d", &W);
    bool block[33][33][2] = {};
    while (W--) {
      int r, c;
      char d[9];
      scanf("%d%d%s", &c, &r, d);
      switch (*d) {
        case 'N':
          block[r][c][0] = true;
          break;
        case 'E':
          block[r][c][1] = true;
          break;
        case 'S':
          block[r - 1][c][0] = true;
          break;
        case 'W':
          block[r][c - 1][1] = true;
          break;
      }
    }
    long long dp[33][33] = {}; // key : long long
    dp[sr][sc] = 1;
    for (int r = sr; r <= er; r++) {
      for (int c = sc; c <= ec; c++) {
        if (!block[r - 1][c][0]) {
          dp[r][c] += dp[r - 1][c];
        }
        if (!block[r][c - 1][1]) {
          dp[r][c] += dp[r][c - 1];
        }
      }
    }
    printf("%lld\n", dp[er][ec]);
  }
  return 0;
}

UVa 825 - Walking on the Safe Side

#include <cstdio>
#include <sstream>
using namespace std;

int main() {
  char s[999];
  gets(s);
  int T;
  sscanf(s, "%d", &T);
  gets(s);
  while (T--) {
    gets(s);
    int R, C;
    sscanf(s, "%d%d", &R, &C);
    int dp[101][101] = {};
    while (gets(s) && s[0]) {
      istringstream ss(s);
      int r, c;
      ss >> r;
      while (ss >> c) {
        dp[r][c] = -1;
      }
    }
    dp[1][1] = 1;
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        if (r && dp[r][c] != -1 && dp[r - 1][c] != -1) {
          dp[r][c] += dp[r - 1][c];
        }
        if (c && dp[r][c] != -1 && dp[r][c - 1] != -1) {
          dp[r][c] += dp[r][c - 1];
        }
      }
    }
    printf("%d\n", dp[R][C]);
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 11067 - Little Red Riding Hood

#include <cstdio>

int main() {
  int R, C;
  while (scanf("%d%d", &C, &R) && R) {
    int n, dp[101][101] = {1};
    scanf("%d", &n);
    while (n--) {
      int r, c;
      scanf("%d%d", &c, &r);
      dp[r][c] = -1;
    }
    for (int r = 0; r <= R; r++) {
      for (int c = 0; c <= C; c++) {
        if (r && dp[r][c] != -1 && dp[r - 1][c] != -1) {
          dp[r][c] += dp[r - 1][c];
        }
        if (c && dp[r][c] != -1 && dp[r][c - 1] != -1) {
          dp[r][c] += dp[r][c - 1];
        }
      }
    }
    if (dp[R][C] <= 0) {
      puts("There is no path.");
    } else if (dp[R][C] == 1) {
      puts("There is one path from Little Red Riding Hood's house to her grandmother's house.");
    } else {
      printf("There are %d paths from Little Red Riding Hood's house to her grandmother's house.\n", dp[R][C]);
    }
  }
  return 0;
}

UVa 843 - Crypt Kicker

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>
#define PB push_back
using namespace std;

vector<string> dic[17];
bool found;

void solve(int now, vector<string> & words, int * encode, bool * done) {
  if (found) {
    return;
  }
  if (now == words.size()) {
    found = true;
    for (int i = 0; i < words.size(); i++) {
      for (int j = 0; words[i][j]; j++) {
        putchar(encode[words[i][j] - 'a'] + 'a');
      }
      putchar(i == words.size() - 1 ? '\n' : ' ');
    }
    return;
  }
  int len = words[now].length();
  for (int i = 0; i < dic[len].size(); i++) {
    bool ok = true;
    vector<int> before, after;
    for (int j = 0; words[now][j] && ok; j++) {
      char c1 = words[now][j] - 'a', c2 = dic[len][i][j] - 'a';
      if (done[c2]) {
        ok = (encode[c1] == c2);
      } else {
        ok = (encode[c1] == -1);
        before.PB(c1);
        after.PB(c2);
      }
    }
    for (int j = 0; j < before.size() && ok; j++) {
      for (int k = j + 1; k < before.size() && ok; k++) {
        if (before[j] == before[k]) {
          ok = (after[j] == after[k]);
        } else {
          ok = (after[j] != after[k]);
        }
        if (after[j] == after[k]) {
          ok = (before[j] == before[k]);
        } else {
          ok = (before[j] != before[k]);
        }
      }
    }
    if (!ok) {
      continue;
    }
    for (int j = 0; j < before.size(); j++) {
      encode[before[j]] = after[j];
      done[after[j]] = true;
    }
    solve(now + 1, words, encode, done);
    for (int j = 0; j < before.size(); j++) {
      encode[before[j]] = -1;
      done[after[j]] = false;
    }
  }
}

int main() {
  char s[1111];
  gets(s);
  int n;
  sscanf(s, "%d", &n);
  while (n--) {
    gets(s);
    dic[strlen(s)].PB(s);
  }
  while (gets(s)) {
    istringstream ss(s);
    string voc;
    vector<string> words;
    while (ss >> voc) {
      words.PB(voc);
    }
    int encode[26];
    memset(encode, -1, sizeof(encode));
    bool done[26] = {};
    found = false;
    solve(0, words, encode, done);
    if (!found) {
      for (int i = 0; s[i]; i++) {
        putchar(s[i] == ' ' ? ' ' : '*');
      }
      puts("");
    }
  }
  return 0;
}

UVa 696 - How Many Knights

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int R, C;
  while (scanf("%d%d", &R, &C) && R) {
    int r = min(R, C), c = max(R, C), ans;
    if (r == 1) {
      ans = c;
    } else if (r == 2) {
      ans = (c / 4) * 4;
      int remain = (c % 4) > 2 ? 2 : (c % 4);
      ans += remain * 2;
    } else {
      ans = (r / 2) * c + (r & 1) * (c / 2 + (c & 1));
    }
    printf("%d knights may be placed on a %d row %d column board.\n", ans, R, C);
  }
  return 0;
}

UVa 10205 - Stack 'em Up

#include <cstdio>
#include <cstring>
#include <sstream>
using namespace std;

char value[13][9] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
char suit[4][9] = {"Clubs", "Diamonds", "Hearts", "Spades"};

int main() {
  char s[999];
  gets(s);
  int T;
  sscanf(s, "%d", &T);
  gets(s);
  while (T--) {
    gets(s);
    int n, shuffle[100][52];
    sscanf(s, "%d", &n);
    for (int i = 0; i < n; i++) {
      int index = 0;
      while (index < 52) {
        gets(s);
        istringstream ss(s);
        while (ss >> shuffle[i][index]) {
          index++;
        }
      }
    }
    int now[52];
    for (int i = 0; i < 52; i++) {
      now[i] = i;
    }
    while (gets(s) && s[0]) {
      int type;
      sscanf(s, "%d", &type);
      int next[52];
      for (int i = 0; i < 52; i++) {
        next[i] = now[shuffle[type - 1][i] - 1];
      }
      memcpy(now, next, sizeof(next));
    }
    for (int i = 0; i < 52; i++) {
      printf("%s of %s\n", value[now[i] % 13], suit[now[i] / 13]);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

2013年8月27日

UVa 11463 - Commandos

#include <cstdio>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int N, R;
    scanf("%d%d", &N, &R);
    int dis[100][100];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        dis[i][j] = (i == j) ? 0 : 1e7;
      }
    }
    while (R--) {
      int u, v;
      scanf("%d%d", &u, &v);
      dis[u][v] = dis[v][u] = 1;
    }
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (dis[i][j] > dis[i][k] + dis[k][j]) {
            dis[i][j] = dis[i][k] + dis[k][j];
          }
        }
      }
    }
    int s, d;
    scanf("%d%d", &s, &d);
    int ans = 0;
    for (int i = 0; i < N; i++) {
      if (dis[s][i] + dis[i][d] > ans) {
        ans = dis[s][i] + dis[i][d];
      }
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

UVa 12101 - Prime Path

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define PB push_back
using namespace std;

bool np[10000];
vector<int> con[10000];

int main() {
  np[0] = np[1] = true;
  for (int i = 2; i < 10000; i++) {
    if (!np[i]) {
      for (int j = i + i; j < 10000; j += i) {
        np[j] = true;
      }
    }
  }
  for (int i = 1000; i < 10000; i++) {
    if (!np[i]) {
      for (int j = 0; j < 4; j++) {
        for (int d = !i; d < 10; d++) {
          char temp[9];
          sprintf(temp, "%d", i);
          if (temp[j] - '0' != d) {
            temp[j] = d + '0';
            int next = atoi(temp);
            if (!np[next]) {
              con[i].PB(next);
            }
          }
        }
      }
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b;
    scanf("%d%d", &a, &b);
    queue<int> q;
    q.push(a);
    bool found = false;
    int dis[10000] = {};
    while (!q.empty()) {
      a = q.front();
      int d = dis[a];
      q.pop();
      if (a == b) {
        printf("%d\n", d);
        found = true;
        break;
      }
      for (int i = 0; i < con[a].size(); i++) {
        if (!dis[con[a][i]]) {
          dis[con[a][i]] = d + 1;
          q.push(con[a][i]);
        }
      }
    }
    if (!found) {
      puts("Impossible");
    }
  }
  return 0;
}

UVa 10165 - Stone Game

#include <cstdio>

int main() {
  int N;
  while (scanf("%d", &N) && N) {
    int b = 0;
    while (N--) {
      int v;
      scanf("%d", &v);
      b ^= v;
    }
    puts(b ? "Yes" : "No");
  }
  return 0;
}

UVa 10264 - The Most Potent Corner

#include <cstdio>

int main() {
  int n, num[16666], sum[16666];
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < (1 << n); i++) {
      scanf("%d", &num[i]);
    }
    for (int i = 0; i < (1 << n); i++) {
      sum[i] = 0;
      for (int j = 0; j < n; j++) {
        sum[i] += num[i ^ (1 << j)];
      }
    }
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < n; j++) {
        ans = sum[i] + sum[i ^ (1 << j)] > ans ? sum[i] + sum[i ^ (1 << j)] : ans;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

2013年8月26日

UVa 1008 - A Vexing Problem

time limit: 54.000 seconds run : 52.472
lol
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#define MP make_pair
#define PB push_back
using namespace std;

typedef pair<int, int> P;
typedef vector<P> VP;
typedef vector<string> VS;

struct State {
  VS puzzle, path;
  VP remain;
};

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};
int R, C;
char name[99];

bool fall(VS & puzzle, VP & remain) {
  bool moved = false;
  for (int i = remain.size() - 1; i >= 0; i--) {
    int r = remain[i].first, c = remain[i].second;
    while (puzzle[r + 1][c] == '-') {
      moved = true;
      puzzle[r + 1][c] = puzzle[r][c];
      puzzle[r++][c] = '-';
      remain[i].first++;
    }
  }
  return moved;
}

void remove(VS & puzzle, VP & remain) {
  bool removed[100] = {};
  for (int i = 0; i < remain.size(); i++) {
    for (int j = i + 1; j < remain.size(); j++) {
      int r1 = remain[i].first, c1 = remain[i].second;
      int r2 = remain[j].first, c2 = remain[j].second;
      if (puzzle[r1][c1] == puzzle[r2][c2]) {
        for (int d = 0; d < 4; d++) {
          if (r1 + dr[d] == r2 && c1 + dc[d] == c2) {
            removed[i] = removed[j] = true;
          }
        }
      }
    }
  }
  VP newRemain;
  for (int i = 0; i < remain.size(); i++) {
    if (removed[i]) {
      int r = remain[i].first, c = remain[i].second;
      puzzle[r][c] = '-';
    } else {
      newRemain.PB(remain[i]);
    }
  }
  remain = newRemain;
}

void solve(VS & puzzle, VP & remain) {
  fall(puzzle, remain);
  remove(puzzle, remain);
  while (fall(puzzle, remain)) {
    remove(puzzle, remain);
  }
}

void showPath(VS & path) {
  printf("%s: Minimum solution length = %d\n", name, path.size());
  for (int i = 0; i < path.size(); i++) {
    printf("%s%s", path[i].c_str(), (i < path.size() - 1) ? ((i % 4 == 3) ? "\n" : " ") : "\n");
  }
}

void BFS(const VS & initPuzzle, const VP & initRemain) {
  VS puzzle = initPuzzle, path;
  VP remain = initRemain;
  map<VS, int> dis[100];
  dis[remain.size()][puzzle] = 0;
  queue<State> q;
  q.push((State){puzzle, path, remain});
  while (!q.empty()) {
    puzzle = q.front().puzzle;
    path = q.front().path;
    remain = q.front().remain;
    int d = dis[remain.size()][puzzle];
    q.pop();
    if (!remain.size()) {
      showPath(path);
      return;
    }
    for (int i = 0; i < remain.size(); i++) {
      int r = remain[i].first, c = remain[i].second;
      for (int dc = -1; dc <= 1; dc += 2) {
        if (puzzle[r][c + dc] == '-') {
          VS newPuzzle = puzzle;
          newPuzzle[r][c + dc] = newPuzzle[r][c];
          newPuzzle[r][c] = '-';
          VP newRemain = remain;
          newRemain[i].second += dc;
          solve(newPuzzle, newRemain);
          if (dis[newRemain.size()].find(newPuzzle) == dis[newRemain.size()].end()) {
            dis[newRemain.size()][newPuzzle] = d + 1;
            VS newPath = path;
            newPath.PB("(" + string(1, puzzle[r][c]) + "," + string(1, r + '0') + "," + string(1, c + '0') + "," + (dc == -1 ? "L" : "R") + ")");
            if (!newRemain.size()) {
              showPath(newPath);
              return;
            }
            q.push((State){newPuzzle, newPath, newRemain});
          }
        }
      }
    }
  }
}

int main() {
  while (scanf("%d%d%s", &R, &C, name) && R) {
    VS puzzle;
    char s[99];
    for (int r = 0; r < R; r++) {
      scanf("%s", s);
      puzzle.PB(s);
    }
    VP remain;
    for (int r = 0; r < puzzle.size() - 1; r++) {
      for (int c = 1; puzzle[r][c + 1]; c++) {
        if (puzzle[r][c] != '#' && puzzle[r][c] != '-') {
          remain.PB(MP(r, c));
        }
      }
    }
    BFS(puzzle, remain);
  }
  return 0;
}

UVa 10081 - Tight Words

#include <cstdio>

int main() {
  int n, k;
  while (scanf("%d%d", &k, &n) == 2) {
    double dp[10][101] = {}, div = 1 + k;
    for (int i = 0; i <= k; i++) {
      dp[i][1] = 1 / div;
    }
    for (int i = 2; i <= n; i++) {
      for (int last = 0; last <= k; last++) {
        for (int diff = -1; diff <= 1; diff++) {
          int digit = last + diff;
          if (0 <= digit && digit <= k) {
            dp[last][i] += dp[digit][i - 1] / div;
          }
        }
      }
    }
    double ans = 0;
    for (int i = 0; i <= k; i++) {
      ans += dp[i][n];
    }
    printf("%.5lf\n", 100 * ans);
  }
  return 0;
}

UVa 10102 - The path in the colored field

#include <cstdio>
#include <queue>
#include <algorithm>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    char map[111][111];
    for (int r = 0; r < n; r++) {
      scanf("%s", map[r]);
    }
    int ans = 0;
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < n; c++) {
        if (map[r][c] == '1') {
          queue<P> q;
          int dis[111][111] = {};
          q.push(MP(r, c));
          while (!q.empty()) {
            P now = q.front();
            int d = dis[now.first][now.second];
            q.pop();
            if (map[now.first][now.second] == '3') {
              ans = max(ans, d);
              break;
            }
            for (int i = 0; i < 4; i++) {
              int nr = now.first + dr[i], nc = now.second + dc[i];
              if (0 <= nr && nr < n && 0 <= nc && nc < n && !dis[nr][nc]) {
                dis[nr][nc] = d + 1;
                q.push(MP(nr, nc));
              }
            }
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 144 - Student Grants

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct Student {
  int id, need;
};

int main() {
  int n, k;
  while (scanf("%d%d", &n, &k) && n) {
    queue<Student> q;
    for (int i = 1; i <= n; i++) {
      q.push((Student){i, 40});
    }
    while (!q.empty()) {
      for (int i = 1; i <= k; i++) {
        int remain = i;
        while (remain && !q.empty()) {
          Student now = q.front();
          q.pop();
          if (now.need > remain) {
            now.need -= remain;
            remain = 0;
            q.push(now);
          } else {
            remain -= now.need;
            printf("%3d", now.id);
          }
        }
      }
    }
    puts("");
  }
  return 0;
}

UVa 11997 - K Smallest Sums

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct Sum {
  bool operator<(const Sum & other) const {
    return s > other.s;
  }
  int index, s;
};

int main() {
  int k;
  while (scanf("%d", &k) == 1) {
    int ans[999];
    for (int i = 0; i < k; i++) {
      scanf("%d", &ans[i]);
    }
    sort(ans, ans + k);
    for (int i = 1; i < k; i++) {
      int b[999];
      for (int j = 0; j < k; j++) {
        scanf("%d", &b[j]);
      }
      sort(b, b + k);
      priority_queue<Sum> pq;
      for (int j = 0; j < k; j++) {
        pq.push((Sum){0, ans[j] + b[0]});
      }
      for (int j = 0; j < k; j++) {
        Sum sum = pq.top();
        pq.pop();
        int s = sum.s, index = sum.index;
        ans[j] = s;
        if (index + 1 < k) {
          pq.push((Sum){index + 1, s - b[index] + b[index + 1]});
        }
      }
    }
    for (int i = 0; i < k; i++) {
      printf("%d%s", ans[i], i == k - 1 ? "\n" : " ");
    }
  }
  return 0;
}

UVa 10980 - Lowest Price in Town

#include <cstdio>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
  char s[99];
  int C = 1;
  while (gets(s)) {
    double price[201] = {};
    for (int i = 2; i <= 200; i++) {
      price[i] = 2e9;
    }
    int m;
    sscanf(s, "%lf%d", &price[1], &m);
    while (m--) {
      gets(s);
      int num;
      double p;
      sscanf(s, "%d%lf", &num, &p);
      price[num] = min(price[num], p);
    }
    for (int i = 1; i <= 200; i++) {
      for (int j = 0; j < i; j++) {
        price[i] = min(price[i], price[i - j] + price[j]);
      }
    }
    for (int i = 199; i; i--) {
      price[i] = min(price[i], price[i + 1]);
    }
    printf("Case %d:\n", C++);
    gets(s);
    istringstream ss(s);
    int k;
    while (ss >> k) {
      printf("Buy %d for $%.2lf\n", k, price[k]);
    }
  }
  return 0;
}

UVa 990 - Diving for Gold

#include <cstdio>
#include <cstring>

struct Treasure {
  int d, v;
} trea[99];


int t, w, dp[33][1111], use[33][1111];

void show(int i, int time, int num) {
  if (!i) {
    printf("%d\n", num);
    return;
  }
  if (use[i][time]) {
    Treasure & treasure = trea[use[i][time]];
    show(i - 1, time - treasure.d * w * 3, num + 1);
    printf("%d %d\n", treasure.d, treasure.v);
  } else {
    show(i - 1, time, num);
  }
}


int main() {
  bool first = true;
  while (scanf("%d%d", &t, &w) == 2) {
    if (!first) {
      puts("");
    }
    first = false;
    memset(dp, 0, sizeof(dp));
    memset(use, 0, sizeof(use));
    int n, cost = 0, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= t; j++) {
        dp[i][j] = dp[i - 1][j];
      }
      scanf("%d%d", &trea[i].d, &trea[i].v);
      int need = trea[i].d * w * 3;
      for (int j = need; j <= t; j++) {
        if (dp[i][j] < dp[i - 1][j - need] + trea[i].v) {
          dp[i][j] = dp[i - 1][j - need] + trea[i].v;
          use[i][j] = i;
          if (dp[i][j] > ans) {
            ans = dp[i][j];
            cost = j;
          }
        }
      }
    }
    printf("%d\n", ans);
    show(n, cost, 0);
  }
  return 0;
}

2013年8月25日

UVa 10049 - Self-describing Sequence

#include <cstdio>
#include <algorithm>
using namespace std;

long long last[700000] = {0, 1, 3};
int N;

int main() {
  for (N = 3; last[N - 1] <= 2e9; N++) {
    last[N] = last[N - 1] + (lower_bound(last, last + N, N) - last);
  }
  int n;
  while (scanf("%d", &n) && n) {
    printf("%d\n", lower_bound(last, last + N, n) - last);
  }
  return 0;
}

UVa 275 - Expanding Fractions

#include <stdio.h>
 
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) && m) {
    int len, ans[3333] = {}, rec[3333] = {};
    for (len = 1; ; len++) {
      ans[len - 1] = n / m;
      n = n % m;
      if (rec[n]) {
        putchar('.');
        int i;
        for (i = 1; i < rec[n]; i++) {
          printf("%d", ans[i]);
        }
        int cycle = len - rec[n];
        if (cycle == 1 && ans[rec[n]] == 0) {
          puts("\nThis expansion terminates.");
        } else {
          for (i = rec[n]; i < rec[n] + cycle; i++) {
            printf("%d%s", ans[i], (i % 50) == 49 && (i != rec[n] + cycle - 1) ? "\n" : "");
          }
          printf("\nThe last %d digits repeat forever.\n", cycle);
        }
        puts("");
        break;
      }
      rec[n] = len;
      n = n * 10;
    }
  }
  return 0;
}

UVa 202 - Repeating Decimals

#include <stdio.h>

int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    printf("%d/%d = %d.", n, m, n / m);
    int len, ans[3333] = {}, rec[3333] = {};
    for (len = 1; ; len++) {
      ans[len - 1] = n / m;
      n = n % m;
      if (rec[n]) {
        int i;
        for (i = 1; i < rec[n]; i++) {
          printf("%d", ans[i]);
        }
        printf("(");
        int cycle = len - rec[n];
        for (i = 0; i < (cycle <= 50 ? cycle : 50); i++) {
          printf("%d", ans[rec[n] + i]);
        }
        printf("%s)\n", cycle <= 50 ? "" : "...");
        printf("   %d = number of digits in repeating cycle\n\n", cycle);
        break;
      }
      rec[n] = len;
      n = n * 10;
    }
  }
  return 0;
}

UVa 297 - Quadtrees

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

char tree[9999];
int now, pix[32][32];

void travel(int r, int c, int size) {
  now++;
  if (tree[now] == 'p') {
    size >>= 1;
    travel(r, c + size, size);
    travel(r, c, size);
    travel(r + size, c, size);
    travel(r + size, c + size, size);
  } else if (tree[now] == 'f') {
    int i, j;
    for (i = r; i < r + size; i++) {
      for (j = c; j < c + size; j++) {
        pix[i][j] = 1;
      }
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  getchar();
  while (T--) {
    memset(pix, 0, sizeof(pix));
    int num = 2;
    while (num--) {
      gets(tree);
      now = -1;
      travel(0, 0, 32);
    }
    int r, c, ans = 0;
    for (r = 0; r < 32; r++) {
      for (c = 0; c < 32; c++) {
        ans += pix[r][c];
      }
    }
    printf("There are %d black pixels.\n", ans);
  }
  return 0;
}

Python Simple File Compare

import sys
from Tkinter import *
from ScrolledText import ScrolledText

def fc(fn1, fn2):
  f = open(fn1, "rU")
  d1 = f.readlines()
  f.close();
  f = open(fn2, "rU")
  d2 = f.readlines()
  f.close();

  for i in range(len(d1)):
    d1[i] = d1[i].replace(' ', '_')
  for i in range(len(d2)):
    d2[i] = d2[i].replace(' ', '_')

  root = Tk()
  root.title('File Compare')
  
  txt = ScrolledText(root, undo=True)
  txt.pack(padx = 5, pady = 5, expand=True, fill='both')
  txt.configure(background='light goldenrod')

  diff = False
  for i in range(max(len(d1), len(d2))):
    if len(d1) > i and len(d2) > i:
      if d1[i] != d2[i]:
        diff = True
        txt.insert(INSERT, "L%03d" % (i + 1) + ':' + d1[i])
        txt.insert(INSERT, '---->' + d2[i])
    elif len(d1) > len(d2):
      diff = True
      txt.insert(INSERT, "L%03d" % (i + 1) + ':' + d1[i])
      txt.insert(INSERT, '---->No answer\n')
    else:
      diff = True
      txt.insert(INSERT, 'No output\n')
      txt.insert(INSERT, '---->' + d2[i])
  if diff:
    txt.configure(foreground='red')
  else:
    txt.insert(INSERT, 'No difference\n')
  root.mainloop()

def main():
  if len(sys.argv) < 3:
    fc("out.txt", "ans.txt")
  else:
    fc(sys.argv[1], sys.argv[2])

if __name__ == '__main__':
  main()

2013年8月24日

UVa 10706 - Number Sequence

#include <cstdio>
#include <map>
using namespace std;
 
inline int digit(int n) {
  int d = 0;
  while (n) {
    n /= 10;
    d++;
  }
  return d;
}

inline int digitOf(int n, int pos) {
  char s[99];
  sprintf(s, "%d", n);
  return s[pos - 1] - '0';
}

int main() {
  long long sum[40000], len[40000];
  for (long long i = 1, j = 0; j < 2147483647; i++) {
    len[i] = digit(i);
    sum[i] = sum[i - 1] + len[i];
    j += sum[i];
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; n > sum[i]; n -= sum[i++]);
    int num;
    for (num = 1; n > len[num]; n -= len[num++]);
    printf("%d\n", digitOf(num, n));
  }
  return 0;
}

UVa 10763 - Foreign Exchange

#include <cstdio>
#include <map>
using namespace std;

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    map<int, int> now, to;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      now[a]++;
      to[b]++;
    }
    bool ok = (now.size() == to.size());
    for (map<int, int>::iterator it = now.begin(); ok && it != now.end(); it++) {
      ok = (it->second == to[it->first]);
    }
    puts(ok ? "YES" : "NO");
  }
  return 0;
}

UVa 10047 - The Monocycle

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct State {
  int r, c, dir, color;
};

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  int R, C, Case = 1;
  bool first = true;
  while (scanf("%d%d", &R, &C) && R) {
    if (!first) {
      puts("");
    }
    printf("Case #%d\n", Case++);
    first = false;
    char map[99][99];
    int sr, sc, tr, tc;
    for (int r = 0; r < R; r++) {
      scanf("%s", map[r]);
      for (int c = 0; map[r][c]; c++) {
        if (map[r][c] == 'S') {
          sr = r;
          sc = c;
        } else if (map[r][c] == 'T') {
          tr = r;
          tc = c;
        }
      }
    }
    int dis[25][25][4][5] = {};
    dis[sr][sc][0][0] = 1;
    queue<State> q;
    q.push((State){sr, sc, 0, 0});
    bool found = false;
    while (!q.empty()) {
      int r = q.front().r, c = q.front().c;
      int dir = q.front().dir, color = q.front().color;
      q.pop();
      int len = dis[r][c][dir][color];
      if (!color && r == tr && c == tc) {
        found = true;
        printf("minimum time = %d sec\n", len - 1);
        break;
      }
      for (int i = 1; i <= 3; i += 2) {
        int nd = (dir + i) % 4;
        if (!dis[r][c][nd][color]) {
          dis[r][c][nd][color] = len + 1;
          q.push((State){r, c, nd, color});
        }
      }
      r += dr[dir];
      c += dc[dir];
      color = (color + 1) % 5;
      if (r >= 0 && r < R && c >= 0 && c < C && map[r][c] != '#' && !dis[r][c][dir][color]) {
        dis[r][c][dir][color] = len + 1;
        q.push((State){r, c, dir, color});
      }
    }
    if (!found) {
      puts("destination not reachable");
    }
  }
  return 0;
}

UVa 1203 - Argus

#include <cstdio>
#include <queue>
using namespace std;

struct Event {
  bool operator<(const Event & other) const {
    return (triggerTime != other.triggerTime) ? (triggerTime > other.triggerTime) : (id > other.id);
  }
  int id, triggerTime, period;
};

int main() {
  char s[99];
  int id, p;
  priority_queue<Event> pq;
  while (scanf("%s", s) && *s != '#') {
    scanf("%d%d", &id, &p);
    pq.push((Event){id, p, p});
  }
  int times;
  scanf("%d", &times);
  while (times--) {
    Event event = pq.top();
    pq.pop();
    printf("%d\n", event.id);
    event.triggerTime += event.period;
    pq.push(event);
  }
  return 0;
}

UVa 165 - Stamps

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

int h, k, max, ans[10];

int len(int * num, int size) {
  if (!size) {
    return 0;
  }
  int i, j, t, dp[10][1000] = {1}, limit = num[size - 1] * h + 1;
  for (t = 1; t <= h; t++) {
    for (j = 0; j < num[0]; j++) {
      dp[t][j] = dp[t - 1][j];
    }
    for (i = 0; i < size; i++) {
      for (j = num[i]; j < limit; j++) {
        dp[t][j] += dp[t - 1][j] + dp[t - 1][j - num[i]];
      }
    }
  }
  for (i = 1; i < limit && dp[h][i]; i++);
  return i - 1;
}

void find(int d, int * use, int used) {
  int l = len(use, used);
  if (used == k) {
    if (l > max) {
      max = l;
      memcpy(ans, use, sizeof(int) * k);
    }
    return;
  }
  for (d++; d <= l + 1; d++) {
    use[used] = d;
    find(d, use, used + 1);
  }
}

int main() {
  while (scanf("%d%d", &h, &k) && (h || k)) {
    max = 0;
    int i, use[10] = {};
    find(0, use, 0);
    for (i = 0; i < k; i++) {
      printf("%3d", ans[i]);
    }
    printf(" ->%3d\n", max);
  }
  return 0;
}

UVa 11729 - Commando War

#include <cstdio>
#include <algorithm>
using namespace std;

struct Soldier {
  bool operator<(const Soldier & other) const {
    return (j != other.j) ? (j > other.j) : (b < other.b);
  }
  int b, j;
} soldiers[1000];

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &soldiers[i].b, &soldiers[i].j);
    }
    sort(soldiers, soldiers + n);
    int bt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
      bt += soldiers[i].b;
      ans = max(ans, soldiers[i].j + bt);
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

UVa 11078 - Open Credit System

#include <stdio.h>

int main() {
  int T, n;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    int i, j, max, ans = -2e9;
    scanf("%d", &max);
    for (i = 1; i < n; i++) {
      scanf("%d", &j);
      ans = max - j > ans ? max - j : ans;
      max = j > max ? j : max;
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
using namespace std;

typedef string Course;

class Student {
 public:

  Student(string SID, int CID, string name, vector<int> scores) : SID(SID), CID(CID), name(name), scores(scores) {
    total = 0;
    for (int i = 0; i < scores.size(); i++) {
      total += scores[i];
    }
    average = total / (double)scores.size();
  }

  string SID, name;
  int CID;
  vector<int> scores;
  int total;
  double average;
};

class SPMS {
 public:

  SPMS(vector<Course> courses) : courses(courses) {}

  void run() {
    int option = -1;
    do {
      switch (option) {
       case 1:
        add();
        break;
       case 2:
        remove();
        break;
       case 3:
        query();
        break;
       case 4:
        showRanking();
        break;
       case 5:
        showStatics();
        break;
      }
      puts("Welcome to Student Performance Management System (SPMS).\n");
      puts("1 - Add");
      puts("2 - Remove");
      puts("3 - Query");
      puts("4 - Show ranking");
      puts("5 - Show Statistics");
      puts("0 - Exit");
      puts("");
    } while (scanf("%d", &option) && option);
  }

 private:

  void add() {
    char SID[99];
    puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
    while (scanf("%s", SID) && string(SID) != "0") {
      int CID;
      char name[99];
      vector<int> scores;
      scanf("%d%s", &CID, name);
      for (int i = 0; i < courses.size(); i++) {
        int score;
        scanf("%d", &score);
        scores.PB(score);
      }
      bool already = false;
      for (int i = 0; i < students.size() && !already; i++) {
        already = (students[i].SID == SID);
      }
      if (already) {
        puts("Duplicated SID.");
      } else {
        students.PB(Student(SID, CID, name, scores));
      }
      puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
    }
  }

  void remove() {
    char keyword[99];
    puts("Please enter SID or name. Enter 0 to finish.");
    while (scanf("%s", keyword) && string(keyword) != "0") {
      int removedNum = 0;
      for (int i = 0; i < students.size(); i++) {
        Student & student = students[i];
        if ((student.SID == keyword) || (student.name == keyword)) {
          students.erase(students.begin() + i--);
          removedNum++;
        }
      }
      printf("%d student(s) removed.\n", removedNum);
      puts("Please enter SID or name. Enter 0 to finish.");
    }
  }

  void query() {
    char keyword[99];
    puts("Please enter SID or name. Enter 0 to finish.");
    while (scanf("%s", keyword) && string(keyword) != "0") {
      adjustRank();
      for (int i = 0; i < students.size(); i++) {
        Student & student = students[i];
        if ((student.SID == keyword) || (student.name == keyword)) {
          printf("%d %s %d %s", rankOfScore[student.total], student.SID.c_str(), student.CID, student.name.c_str());
          for (int j = 0; j < student.scores.size(); j++) {
            printf(" %d", student.scores[j]);
          }
          printf(" %d %.2lf\n", student.total, student.average + 1e-5);
        }
      }
      puts("Please enter SID or name. Enter 0 to finish.");
    }
  }

  void showRanking() {
    puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
  }

  void showStatics() {
    puts("Please enter class ID, 0 for the whole statistics.");
    int CID;
    scanf("%d", &CID);
    for (int c = 0; c < courses.size(); c++) {
      puts(courses[c].c_str());
      int num = 0, total = 0, passed = 0;
      for (int i = 0; i < students.size(); i++) {
        Student & student = students[i];
        if (!CID || (student.CID == CID)) {
          num++;
          total += student.scores[c];
          passed += (student.scores[c] >= 60);
        }
      }
      printf("Average Score: %.2lf\n", total / (double)(num == 0 ? 1 : num) + 1e-5);
      printf("Number of passed students: %d\n", passed);
      printf("Number of failed students: %d\n", num - passed);
      puts("");
    }
    vector<int> passedNum(courses.size() + 1, 0);
    for (int i = 0; i < students.size(); i++) {
      Student & student = students[i];
      if (!CID || (student.CID == CID)) {
        int passed = 0;
        for (int c = 0; c < courses.size(); c++) {
          passed += (student.scores[c] >= 60);
        }
        passedNum[passed]++;
      }
    }
    puts("Overall:");
    printf("Number of students who passed all subjects: %d\n", passedNum.back());
    for (int i = passedNum.size() - 2; i > 0; i--) {
      passedNum[i] += passedNum[i + 1];
      printf("Number of students who passed %d or more subjects: %d\n", i, passedNum[i]);
    }
    printf("Number of students who failed all subjects: %d\n", passedNum[0]);
    puts("");
  }

  void adjustRank() {
    rankOfScore.clear();
    vector<int> allScores;
    for (int i = 0; i < students.size(); i++) {
      allScores.PB(students[i].total);
    }
    sort(allScores.begin(), allScores.end());
    reverse(allScores.begin(), allScores.end());
    for (int i = 0; i < allScores.size(); i++) {
      if (rankOfScore.find(allScores[i]) == rankOfScore.end()) {
        rankOfScore[allScores[i]] = i + 1;
      }
    }
  }

  vector<Course> courses;
  vector<Student> students;
  map<int, int> rankOfScore;
};

int main() {
  vector<Course> courses;
  courses.PB("Chinese");
  courses.PB("Mathematics");
  courses.PB("English");
  courses.PB("Programming");
  SPMS spms(courses);
  spms.run();
  return 0;
}

2013年8月23日

UVa 11384 - Help is needed for Dexter

#include <stdio.h>

int times(int n) {
  if (n == 1) {
    return 1;
  }
  return times(n / 2) + 1;
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    printf("%d\n", times(n));
  }
  return 0;
}

2013年8月22日

UVa 10785 - The Mad Numerologist

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int c[21] = {
  'J', 'S',
  'B', 'K', 'T',
  'C', 'L',
  'D', 'M', 'V',
  'N', 'W',
  'F', 'X',
  'G', 'P', 'Y',
  'H', 'Q', 'Z',
  'R',
};

const int v[5] = {'A', 'U', 'E', 'O', 'I'};

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int l;
    scanf("%d", &l);
    int vi = 0, ci = 0, cnt[128] = {};
    string vs, cs;
    printf("Case %d: ", C++);
    for (int i = 1; i <= l; i++) {
      if (i & 1) {
        vs += v[vi];
        cnt[v[vi]]++;
        if (cnt[v[vi]] == 21) {
          vi++;
        }
      } else {
        cs += c[ci];
        cnt[c[ci]]++;
        if (cnt[c[ci]] == 5) {
          ci++;
        }
      }
    }
    sort(vs.begin(), vs.end());
    sort(cs.begin(), cs.end());
    for (int i = 1; i <= l; i++) {
      if (i & 1) {
        putchar(vs[i / 2]);
      } else {
        putchar(cs[i / 2 - 1]);
      }
    }
    puts("");
  }
  return 0;
}

UVa 152 - Tree's a Crowd

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
  int N = 0, x[5555], y[5555], z[5555];
  while (scanf("%d%d%d", &x[N], &y[N], &z[N])) {
    if (!x[N] && !y[N] && !z[N]) {
      break;
    }
    N++;
  }
  int cnt[10] = {};
  for (int i = 0; i < N; i++) {
    int dis = 2e9;
    for (int j = 0; j < N; j++) {
      if (i != j) {
        dis = min(dis, (x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]) + (z[j] - z[i]) * (z[j] - z[i]));
      }
    }
    if (dis < 100) {
      cnt[(int)sqrt(dis)]++;
    }
  }
  for (int i = 0; i < 10; i++) {
    printf("%4d", cnt[i]);
  }
  puts(""); // keypoint
  return 0;
}

UVa 10194 - Football (aka Soccer)

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Team {
  Team(string name) : p(0), w(0), t(0), l(0), gp(0), gd(0), gs(0), ga(0), name(name) {
    lname = name;
    for (int i = 0; lname[i]; i++) {
      lname[i] = tolower(lname[i]);
    }
  }
  bool operator<(const Team & other) const {
    if (p != other.p) {
      return p > other.p;
    }
    if (w != other.w) {
      return w > other.w;
    }
    if (gd != other.gd) {
      return gd > other.gd;
    }
    if (gs != other.gs) {
      return gs > other.gs;
    }
    if (gp != other.gp) {
      return gp < other.gp;
    }
    return lname < other.lname;
  }
  int p, w, t, l, gd, mgs, gp, gs, ga;
  string name, lname;
};

int main() {
  char s[999];
  int T;
  gets(s);
  sscanf(s, "%d", &T);
  while (T--) {
    gets(s);
    puts(s);
    int N;
    gets(s);
    sscanf(s, "%d", &N);
    vector<Team> v;
    while (N--) {
      char name[99];
      gets(name);
      v.PB(Team(name));
    }
    int M;
    gets(s);
    sscanf(s, "%d", &M);
    while (M--) {
      gets(s);
      string temp(s);
      int p1, p2, p3;
      p1 = temp.find('#');
      p2 = temp.find('@', p1);
      p3 = temp.find('#', p2);
      string team[2];
      int score[2];
      team[0] = temp.substr(0, p1);
      score[0] = atoi(temp.substr(p1 + 1, p2 - p1 - 1).c_str());
      team[1] = temp.substr(p3 + 1);
      score[1] = atoi(temp.substr(p2 + 1, p3 - p2 - 1).c_str());
      for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < 2; j++) {
          if (v[i].name == team[j]) {
            if (score[j] > score[!j]) {
              v[i].p += 3;
              v[i].w++;
            } else if (score[j] == score[!j]) {
              v[i].p += 1;
              v[i].t++;
            } else {
              v[i].p += 0;
              v[i].l++;
            }
            v[i].gp++;
            v[i].gd += score[j] - score[!j];
            v[i].gs += score[j];
            v[i].ga += score[!j];
          }
        }
      }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
      printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n", i + 1, v[i].name.c_str(), v[i].p, v[i].gp, v[i].w, v[i].t, v[i].l, v[i].gd, v[i].gs, v[i].ga);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 10029 - Edit Step Ladders

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int ans = 0;
  map<string, int> dis[17];
  char temp[99];
  while (gets(temp)) {
    string s(temp);
    int len = s.length(), longest = 0;
    for (int i = 0; s[i]; i++) {
      for (char c = 'a'; c <= 'z'; c++) {
        string pre = s;
        pre[i] = c;
        if (s < pre) {
          break;
        }
        if (dis[len].count(pre)) {
          longest = max(longest, dis[len][pre]);
        }
      }
    }
    for (int i = 0; s[i]; i++) {
      string pre = s.substr(0, i) + s.substr(i + 1);
      if (dis[len - 1].count(pre) && s > pre) {
        longest = max(longest, dis[len - 1][pre]);
      }
    }
    if (len < 16) {
      for (int i = 0; s[i]; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
          string pre = s.substr(0, i) + c + s.substr(i);
          if (s < pre) {
            break;
          }
          if (dis[len + 1].count(pre) && s > pre) {
            longest = max(longest, dis[len + 1][pre]);
          }
        }
      }
    }
    dis[len][s] = longest + 1;
    ans = max(ans, longest + 1);
  }
  printf("%d\n", ans);
  return 0;
}

2013年8月21日

LCS among 3 strings

int lcs(char * a, char * b, char * c) {
  int len[20][20][20], ans = 0;
  for (int i = 1; a[i]; i++) {
    for (int j = 1; b[j]; j++) {
      for (int k = 1; c[k]; k++) {
        if (a[i] == b[j] && b[j] == c[k]) {
          len[i][j][k] = len[i - 1][j - 1][k - 1] + 1;
          ans = max(ans, len[i][j][k]);
        } else {
          len[i][j][k] = max(len[i - 1][j][k], max(len[i][j - 1][k], len[i][j][k - 1]));
        }
      }
    }
  }
  return ans;
}

UVa 11060 - Beverages

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#define PB push_back
using namespace std;


vector<string> words;
map<string, int> indexOf;
bool con[100][100]; 

void find(vector<int> & use, int * cnt) {
  if (use.size() == words.size()) {
    for (int i = 0; i < use.size(); i++) {
      printf("%s%s", words[use[i]].c_str(), i == words.size() - 1 ? ".\n" : " ");
    }
    return;
  }
  for (int i = 0; i < words.size(); i++) {
    if (!cnt[i]) {
      cnt[i] = -1;
      for (int j = 0; j < words.size(); j++) {
        cnt[j] -= con[i][j];
      }
      use.PB(i);
      find(use, cnt);
      return;
    }
  }
}

int main() {
  int N, M, C = 1;
  while (scanf("%d", &N) == 1) {
    char s[99];
    words.clear();
    for (int i = 0; i < N; i++) {
      scanf("%s", s);
      words.PB(s);
      indexOf[s] = i;
    }
    scanf("%d", &M);
    int cnt[100] = {};
    memset(con, false, sizeof(con));
    while (M--) {
      char a[99], b[99];
      scanf("%s%s", a, b);
      int i = indexOf[a], j = indexOf[b];
      if (!con[i][j]) {
        con[i][j] = true;
        cnt[j]++;
      }
    }
    vector<int> use;
    printf("Case #%d: Dilbert should drink beverages in this order: ", C++);
    find(use, cnt);
    puts("");
  }
  return 0;
}

UVa 872 - Ordering

#include <cstdio>
#include <cstring>
#include <sstream>
#include <vector>
#define PB push_back
using namespace std;


vector<char> alpha;
bool con[128][128], found;

void find(vector<char> & use, int * cnt) {
  if (use.size() == alpha.size()) {
    for (int i = 0; i < use.size(); i++) {
      printf("%c%s", use[i], i == alpha.size() - 1 ? "\n" : " ");
    }
    found = true;
    return;
  }
  for (int i = 0; i < alpha.size(); i++) {
    if (!cnt[alpha[i]]) {
      cnt[alpha[i]] = -1;
      for (int j = 0; j < alpha.size(); j++) {
        cnt[alpha[j]] -= con[alpha[i]][alpha[j]];
      }
      use.PB(alpha[i]);
      find(use, cnt);
      use.pop_back();
      for (int j = 0; j < alpha.size(); j++) {
        cnt[alpha[j]] += con[alpha[i]][alpha[j]];
      }
      cnt[alpha[i]] = 0;
    }
  }
}

int main() {
  char s[999];
  int T;
  gets(s);
  sscanf(s, "%d", &T);
  while (T--) {
    gets(s);
    gets(s);
    istringstream ss1(s);
    alpha.clear();
    while (ss1 >> s) {
      alpha.PB(s[0]);
    }
    gets(s);
    istringstream ss2(s);
    int cnt[128] = {};
    memset(con, false, sizeof(con));
    while (ss2 >> s) {
      con[s[0]][s[2]] = true;
      cnt[s[2]]++;
    }
    vector<char> use;
    found = false;
    find(use, cnt);
    if (!found) {
      puts("NO");
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 10874 - Segments

#include <cstdio>

inline int abs(int n) {
  return n < 0 ? -n : n;
}

inline int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int p1 = 1, p2 = 1, s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
      int l, r;
      scanf("%d%d", &l, &r);
      int d1 = min(s1 + abs(p1 - r) + abs(r - l), s2 + abs(p2 - r) + abs(r - l));
      int d2 = min(s1 + abs(p1 - l) + abs(l - r), s2 + abs(p2 - l) + abs(l - r));
      s1 = d1 + 1;
      s2 = d2 + 1;
      p1 = l;
      p2 = r;
    }
    printf("%d\n", min(s1 + abs(p1 - n), s2 + abs(p2 - n)) - 1);
  }
  return 0;
}

UVa 526 - String Distance and Transform Process

#include <cstdio>
#include <cstring>
 
inline int min(int a, int b) {
  return a < b ? a : b;
}
 
char s1[99], s2[99];
int op[99][99], ins, del, cnt;
 
void show(int i, int j) {
  switch (op[i][j]) {
    case 0:
      show(i - 1, j - 1);
      break;
    case 'C':
      show(i - 1, j - 1);
      printf("%d Replace %d,%c\n", ++cnt, i + ins - del, s2[j]);
      break;
    case 'D':
      show(i - 1, j);
      printf("%d Delete %d\n", ++cnt, i + ins - del);
      del++;
      break;
    case 'I':
      show(i, j - 1);
      printf("%d Insert %d,%c\n", ++cnt, j, s2[j]);
      ins++;
      break;
  }
}
 
int main() {
  bool first = true;
  while (gets(s1 + 1)) {
    gets(s2 + 1);
    if (!first) {
      puts("");
    }
    first = false;
    int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    int dis[99][99] = {};
    memset(op, 0, sizeof(op));
    for (int i = 1; s1[i]; i++) {
      dis[i][0] = i;
      op[i][0] = 'D';
    }
    for (int j = 1; s2[j]; j++) {
      dis[0][j] = j;
      op[0][j] = 'I';
    }
    for (int i = 1; s1[i]; i++) {
      for (int j = 1; s2[j]; j++) {
        int m = min(dis[i - 1][j - 1] + (s1[i] != s2[j]), min(dis[i - 1][j] + 1, dis[i][j - 1] + 1));
        dis[i][j] = m;
        if (m == dis[i - 1][j] + 1) {
          op[i][j] = 'D';
        } else if (m == dis[i][j - 1] + 1) {
          op[i][j] = 'I';
        } else {
          op[i][j] = (s1[i] != s2[j]) ? 'C' : 0;
        }
      }
    }
    ins = del = cnt = 0;
    printf("%d\n", dis[l1][l2]);
    show(l1, l2);
  }
  return 0;
}

UVa 164 - String Computer

#include <cstdio>
#include <cstring>
 
inline int min(int a, int b) {
  return a < b ? a : b;
}
 
char s1[99], s2[99];
int op[29][29], ins, del;
 
void show(int i, int j) {
  switch (op[i][j]) {
    case 0:
      show(i - 1, j - 1);
      break;
    case 'C':
      show(i - 1, j - 1);
      printf("C%c%02d", s2[j], i + ins - del);
      break;
    case 'D':
      show(i - 1, j);
      printf("D%c%02d", s1[i], i + ins - del);
      del++;
      break;
    case 'I':
      show(i, j - 1);
      printf("I%c%02d", s2[j], j);
      ins++;
      break;
  }
}
 
int main() {
  while (scanf("%s", s1 + 1) && s1[1] != '#') {
    scanf("%s", s2 + 1);
    int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    int dis[29][29] = {};
    memset(op, 0, sizeof(op));
    for (int i = 1; s1[i]; i++) {
      dis[i][0] = i;
      op[i][0] = 'D';
    }
    for (int j = 1; s2[j]; j++) {
      dis[0][j] = j;
      op[0][j] = 'I';
    }
    for (int i = 1; s1[i]; i++) {
      for (int j = 1; s2[j]; j++) {
        int m = min(dis[i - 1][j - 1] + (s1[i] != s2[j]), min(dis[i - 1][j] + 1, dis[i][j - 1] + 1));
        dis[i][j] = m;
        if (m == dis[i - 1][j] + 1) {
          op[i][j] = 'D';
        } else if (m == dis[i][j - 1] + 1) {
          op[i][j] = 'I';
        } else {
          op[i][j] = (s1[i] != s2[j]) ? 'C' : 0;
        }
      }
    }
    ins = del = 0;
    show(l1, l2);
    puts("E");
  }
  return 0;
}

UVa 11056 - Formula 1

#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

string lower(string s) {
  string ls = s;
  for (int i = 0; ls[i]; i++) {
    ls[i] = tolower(ls[i]);
  }
  return ls;
}

struct Person {
  Person(char * name, int time) : name(name), time(time) {
    lname = lower(name);
  }
  bool operator < (const Person & other) const {
    return (time != other.time) ? (time < other.time) : (lname < other.lname);
  }
  string name, lname;
  int time;
};

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    vector<Person> people;
    for (int i = 0; i < n; i++) {
      char name[99], t[99];
      int m, s, ms;
      scanf("%s%s%d%s%d%s%d%s", name, t, &m, t, &s, t, &ms, t);
      people.PB(Person(name, (m * 60 + s) * 1000 + ms));
    }
    sort(people.begin(), people.end());
    for (int i = 0, R = 1; i < n; i += 2, R++) {
      printf("Row %d\n", R);
      puts(people[i].name.c_str());
      if (i + 1 < n) {
        puts(people[i + 1].name.c_str());
      }
    }
    puts("");
  }
  return 0;
}

UVa 143 - Orchard Trees

#include <cstdio>
#include <cmath>
 
inline double area(double x1, double y1, double x2, double y2, double x3, double y3) {
  return fabs(0.5 * ((y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)));
}
 
inline double min(double a, double b) {
  return a < b ? a : b;
}
 
inline double max(double a, double b) {
  return a > b ? a : b;
}
 
int main() {
  char t;
  int n = 0;
  double x1, x2, x3, y1, y2, y3;
  while (scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3) && x1 || x2 || x3 || y1 || y2 || y3) {
    int xS = ceil(min(min(x1, x2), x3)), xE = max(max(x1, x2), x3);
    int yS = ceil(min(min(y1, y2), y3)), yE = max(max(y1, y2), y3);
    double x, y, a, a1, a2, a3;
    a = area(x1, y1, x2, y2, x3, y3);
    int ans = 0;
    if (xE > 99) xE = 99;
    if (yE > 99) yE = 99;
    if (!xS) xS = 1;
    if (!yS) yS = 1;
    for (x = xS; x <= xE; x++)
      for (y = yS; y <= yE; y++) {
        a1 = area(x1, y1, x2, y2, x, y);
        a2 = area(x1, y1, x, y, x3, y3);
        a3 = area(x, y, x2, y2, x3, y3);
        if ((fabs(a - (a1 + a2 + a3)) <= 1e-7)) ans++;
      }
    printf("%4d\n", ans);
  }
  return 0;
}

UVa 10112 - Myacm Triangles

#include <cstdio>

struct P {
  char c;
  int x, y;
} p[20];

inline double area(P & a, P & b, P & c) {
  double size = 0.5 * ((c.y - a.y) * (b.x - a.x) - (b.y - a.y) * (c.x - a.x));
  return size < 0 ? -size : size;
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      char c[9];
      int x, y;
      scanf("%s%d%d", c, &p[i].x, &p[i].y);
      p[i].c = c[0];
    }
    char a, b, c;
    double max = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
          double size = area(p[i], p[j], p[k]);
          if (size > max) {
            bool in = false;
            for (int l = 0; l < n && !in; l++) {
              if (l == i || l == j || l == k) {
                continue;
              }
              in = (area(p[i], p[j], p[l]) + area(p[i], p[k], p[l]) + area(p[j], p[k], p[l]) == size);
            }
            if (!in) {
              max = size;
              a = p[i].c;
              b = p[j].c;
              c = p[k].c;
            }
          }
        }
      }
    }
    printf("%c%c%c\n", a, b, c);
  }
  return 0;
}

UVa 185 - Roman Numerals

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#define PB push_back
using namespace std;

int solutionNumber;
char a[99], b[99], c[99];

void solve(int now, vector<char> & all, int * value, bool * used, bool * head) {
  if (solutionNumber > 1) {
    return;
  }
  if (now == all.size()) {
    int n1 = 0, n2 = 0, n3 = 0;
    for (int i = 0; a[i]; i++) {
      n1 = n1 * 10 + value[a[i]];
    }
    for (int i = 0; b[i]; i++) {
      n2 = n2 * 10 + value[b[i]];
    }
    for (int i = 0; c[i]; i++) {
      n3 = n3 * 10 + value[c[i]];
    }
    if (n1 + n2 == n3) {
      solutionNumber++;
    }
    return;
  }
  for (int d = 0 + head[all[now]]; d < 10 && solutionNumber <= 1; d++) {
    if (!used[d]) {
      value[all[now]] = d;
      used[d] = true;
      solve(now + 1, all, value, used, head);
      used[d] = false;
    }
  }
}

const int S1 = 13;
const int v1[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
const string s1[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
const int S2 = 16;
const int v2[] = {1, 4, 5, 9, 10, 40, 50, 90, 99, 100, 400, 500, 900, 990, 999, 1000};
const string s2[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "IC", "C", "CD", "D", "CM", "XM", "IM", "M"};

int main() {
  map<string, int> dic;
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = S1 - 1; i >= 0 && num; i--) {
      while (num >= v1[i]) {
        roman += s1[i];
        num -= v1[i];
      }
    }
    dic[roman] = n;
  }
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = S2 - 1; i >= 0 && num; i--) {
      while (num >= v2[i]) {
        roman += s2[i];
        num -= v2[i];
      }
    }
    dic[roman] = n;
  }
  char s[999];
  while (gets(s) && s[0] != '#') {
    bool ch[26] = {};
    for (int i = 0; s[i]; i++) {
      if (s[i] == '+' || s[i] == '=') {
        s[i] = ' ';
      } else {
        ch[s[i] - 'A'] = true;
      }
    }
    sscanf(s, "%s%s%s", a, b, c);
    bool head[128] = {};
    head[a[0]] = true;
    head[b[0]] = true;
    head[c[0]] = true;
    vector<char> all;
    for (int i = 0; i < 26; i++) {
      if (ch[i]) {
        all.PB(i + 'A');
      }
    }
    int value[128] = {};
    bool used[10] = {};
    solutionNumber = 0;
    solve(0, all, value, used, head);
    printf("%s ", dic[a] + dic[b] == dic[c] ? "Correct" : "Incorrect");
    switch (solutionNumber) {
      case 0:
        puts("impossible");
        break;
      case 1:
        puts("valid");
        break;
      default:
        puts("ambiguous");
        break;
    }
  }
  return 0;
}

2013年8月20日

UVa 148 - Anagram checker

#include <cstdio>
#include <cstring>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
using namespace std;

char s[99], word[2222][22];
int N, len[2222];
vector<int> originSet;

void find(int index, int remain, int * need, vector<int> & used) {
  if (!remain) {
    if (used != originSet) {
      printf("%s = ", s);
      for (int i = 0; i < used.size(); i++) {
        printf("%s%s", word[used[i]], i == used.size() - 1 ? "\n" : " ");
      }
    }
    return;
  }
  if (index >= N) {
    return;
  }
  int temp[26];
  memcpy(temp, need, sizeof(temp));
  bool add = true;
  for (int i = 0; word[index][i] && add; i++) {
    char c = word[index][i] - 'A';
    need[c]--;
    add = (need[c] >= 0);
  }
  if (add) {
    used.PB(index);
    find(index + 1, remain - len[index], need, used);
    used.pop_back();
  }
  memcpy(need, temp, sizeof(temp));
  find(index + 1, remain, need, used);
  memcpy(need, temp, sizeof(temp));
}

int main() {
  map<string, int> indexOf;
  while (gets(word[N]) && word[N][0] != '#') {
    len[N] = strlen(word[N]);
    indexOf[word[N]] = N;
    N++;
  }
  while (gets(s) && s[0] != '#') {
    int remain = 0, need[26] = {};
    for (int i = 0; s[i]; i++) {
      if (s[i] == ' ') {
        continue;
      }
      need[s[i] - 'A']++;
      remain++;
    }
    originSet.clear();
    istringstream ss(s);
    string tmp;
    while (ss >> tmp) {
      if (indexOf.count(tmp)) {
        originSet.PB(indexOf[tmp]);
      }
    }
    sort(originSet.begin(), originSet.end());
    vector<int> used;
    find(0, remain, need, used);
  }
  return 0;
}

UVa 10195 - The Knights Of The Round Table

#include <stdio.h>
#include <math.h>

int main() {
  double a, b, c;
  while (scanf("%lf%lf%lf", &a, &b, &c) == 3) {
    double s = (a + b + c) * 0.5;
    double area = sqrt(s * (s - a) * (s - b) * (s - c));
    printf("The radius of the round table is: %.3lf\n", area / (s == 0 ? 1 : s));
  }
  return 0;
}

UVa 759 - The Return of the Roman Empire

#include <cstdio>
#include <string>
#include <map>
using namespace std;

const int SIZE = 13;
const int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
const string sign[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};

int main() {
  map<string, int> dic;
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = SIZE - 1; i >= 0 && num; i--) {
      while (num >= value[i]) {
        roman += sign[i];
        num -= value[i];
      }
    }
    dic[roman] = n;
  }
  char s[99];
  while (gets(s)) {
    if (dic.count(s)) {
      printf("%d\n", dic[s]);
    } else {
      puts("This is not a valid number");
    }
  }
  return 0;
}

UVa 11616 - Roman Numerals

#include <cstdio>
#include <string>
#include <map>
using namespace std;

const int SIZE = 13;
const int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
const string sign[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};

int main() {
  map<string, string> dic;
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = SIZE - 1; i >= 0 && num; i--) {
      while (num >= value[i]) {
        roman += sign[i];
        num -= value[i];
      }
    }
    char s[99];
    sprintf(s, "%d", n);
    dic[s] = roman;
    dic[roman] = s;
  }
  char s[99];
  while (gets(s)) {
    puts(dic[s].c_str());
  }
  return 0;
}

2013年8月19日

UVa 12414 - Calculating Yuan Fen

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

int check(char * s) {
  return !s[3] || !strcmp(s, "100");
}

int solve(char * s) {
  while (!check(s)) {
    int i;
    for (i = 0; s[i + 1]; i++) {
      s[i] = (s[i] - '0' + s[i + 1] - '0') % 10 + '0';
    }
    s[i] = 0;
  }
  return !strcmp(s, "100");
}

int main() {
  char s[99];
  while (gets(s)) {
    int i, ST, solved = 0;
    for (ST = 1; ST <= 10000 && !solved; ST++) {
      char temp[999] = {};
      for (i = 0; s[i]; i++) {
        char num[99];
        sprintf(num, "%d", ST + s[i] - 'A');
        strcat(temp, num);
      }
      solved = solve(temp);
      if (solved) {
        printf("%d\n", ST);
      }
    }
    if (!solved) {
      puts(":(");
    }
  }
  return 0;
}

UVa 10810 - Ultra-QuickSort

#include <cstdio>

int num[500000], temp[500000];
long long swap;

void sort(int l, int r) {
  if (r - l <= 1) {
    return;
  }
  int mid = (l + r) / 2;
  sort(l, mid);
  sort(mid, r);
  int i = l, j = mid, k = 0;
  while (i < mid && j < r) {
    if (num[i] > num[j]) {
      temp[k++] = num[j++];
      swap += mid - i;
    } else {
      temp[k++] = num[i++];
    }
  }
  while (i < mid) {
    temp[k++] = num[i++];
  }
  while (j < r) {
    temp[k++] = num[j++];
  }
  for (i = l; i < r; i++) {
    num[i] = temp[i - l];
  }
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      scanf("%d", &num[i]);
    }
    swap = 0;
    sort(0, n);
    printf("%lld\n", swap);
  }
  return 0;
}

UVa 10703 - Free spots

#include <cstdio>

int main() {
  int W, H, N;
  while (scanf("%d%d%d", &W, &H, &N) && W) {
    bool spot[501][501] = {};
    while (N--) {
      int x1, x2, y1, y2;
      scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      if (x2 < x1) {
        int temp = x1;
        x1 = x2;
        x2 = temp;
      }
      if (y2 < y1) {
        int temp = y1;
        y1 = y2;
        y2 = temp;
      }
      for (int x = x1; x <= x2; x++) {
        for (int y = y1; y <= y2; y++) {
          spot[x][y] = true;
        }
      }
    }
    int empty = 0;
    for (int x = 1; x <= W; x++) {
      for (int y = 1; y <= H; y++) {
        empty += !spot[x][y];
      }
    }
    if (!empty) {
      puts("There is no empty spots.");
    } else if (empty == 1) {
      puts("There is one empty spot.");
    } else {
      printf("There are %d empty spots.\n", empty);
    }
  }
  return 0;
}

UVa 409 - Excuses, Excuses!

#include <cstdio>
#include <cctype>
#include <string>
#include <sstream>
using namespace std;

int main() {
  char s[999];
  int C = 1;
  while (gets(s)) {
    int K, E;
    sscanf(s, "%d%d", &K, &E);
    char keywords[20][99];
    for (int i = 0; i < K; i++) {
      gets(keywords[i]);
    }
    int num[20] = {}, max = 0;
    char excuses[20][99];
    for (int i = 0; i < E; i++) {
      gets(excuses[i]);
      string sentence(excuses[i]);
      for (int j = 0; sentence[j]; j++) {
        if (!isalpha(sentence[j])) {
          sentence[j] = ' ';
        } else {
          sentence[j] = tolower(sentence[j]);
        }
      }
      istringstream ss(sentence);
      string word;
      while (ss >> word) {
        for (int j = 0; j < K; j++) {
          num[i] += (word == keywords[j]);
        }
      }
      max = num[i] > max ? num[i] : max;
    }
    printf("Excuse Set #%d\n", C++);
    for (int i = 0; i < E; i++) {
      if (num[i] == max) {
        puts(excuses[i]);
      }
    }
    puts("");
  }
  return 0;
}

UVa 739 - Soundex Indexing

#include <cstdio>

int main() {
  int v[99] = {};
  v['B'] = v['P'] = v['F'] = v['V'] = 1;
  v['C'] = v['S'] = v['K'] = v['G'] = v['J'] = v['Q'] = v['X'] = v['Z'] = 2;
  v['D'] = v['T'] = 3;
  v['L'] = 4;
  v['M'] = v['N'] = 5;
  v['R'] = 6;
  printf("%9s%-25s%s\n", "", "NAME", "SOUNDEX CODE");
  char s[99];
  while (gets(s)) {
    int digit = 0;
    printf("%9s%-25s", "", s);
    putchar(s[0]);
    for (int i = 1; s[i] && digit < 3; i++) {
      if (v[s[i]] && v[s[i]] != v[s[i - 1]]) {
        printf("%d", v[s[i]]);
        digit++;
      }
    }
    while (digit < 3) {
      printf("0");
      digit++;
    }
    puts("");
  }
  printf("%19s%s\n", "", "END OF OUTPUT");
  return 0;
}

2013年8月18日

UVa 11954 - Binary Calculator

#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
#define PB push_back
using namespace std;

inline void removeZero(string & s) {
  while (s[0] == '0' && s.length() > 1) {
    s.erase(s.begin());
  }
}

int main() {
  char s[1005];
  gets(s);
  int T, C = 1;
  sscanf(s, "%d", &T);
  while (T--) {
    gets(s);
    istringstream ss(s);
    string word;
    vector<string> exp;
    while (ss >> word) {
      removeZero(word);
      exp.PB(word);
    }
    for (int i = exp.size() - 1; i > 0; i--) {
      if (exp[i - 1] == "not") {
        for (int j = 0; exp[i][j]; j++) {
          exp[i][j] = (exp[i][j] == '0') ? '1' : '0';
        }
        removeZero(exp[i]);
        exp.erase(exp.begin() + i - 1);
      } else if (exp[i - 1] == "shl") {
        exp[i] += "0";
        exp.erase(exp.begin() + i - 1);
      } else if (exp[i - 1] == "shr") {
        if (exp[i].length() > 1) {
          exp[i].erase(exp[i].begin() + exp[i].length() - 1);
        } else {
          exp[i] = "0";
        }
        exp.erase(exp.begin() + i - 1);
      }
    }
    for (int i = 1; i < exp.size(); i += 2) {
      int l1 = exp[i - 1].length(), l2 = exp[i + 1].length();
      int l = l1 > l2 ? l1 : l2;
      exp[i - 1] = string(l - l1, '0') + exp[i - 1];
      exp[i + 1] = string(l - l2, '0') + exp[i + 1];
      if (exp[i] == "xor") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] != exp[i - 1][j]) ? '1' : '0';
        }
      } else if (exp[i] == "and") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] == '1' && exp[i - 1][j] == '1') ? '1' : '0';
        }
      } else if (exp[i] == "or") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] == '1' || exp[i - 1][j] == '1') ? '1' : '0';
        }
      }
    }
    string ans = exp.back();
    removeZero(ans);
    printf("Case %d: %s\n", C++, ans.c_str());
  }
  return 0;
}

UVa 10171 - Meeting Prof. Miguel...

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int y[26][26], o[26][26];
    for (int a = 0; a < 26; a++) {
      for (int b = 0; b < 26; b++) {
        y[a][b] = o[a][b] = 1e7;
      }
    }
    for (int a = 0; a < 26; a++) {
      y[a][a] = o[a][a] = 0;
    }
    for (int i = 0; i < n; i++) {
      char age[9], dir[9], X[9], Y[9];
      int d;
      scanf("%s%s%s%s%d", age, dir, X, Y, &d);
      int a = *X - 'A', b = *Y - 'A';
      if (*dir == 'B') {
        if (*age == 'Y') {
          y[a][b] = min(y[a][b], d);
          y[b][a] = min(y[b][a], d);
        } else {
          o[a][b] = min(o[a][b], d);
          o[b][a] = min(o[b][a], d);
        }
      } else {
        if (*age == 'Y') {
          y[a][b] = min(y[a][b], d);
        } else {
          o[a][b] = min(o[a][b], d);
        }
      }
    }
    for (int k = 0; k < 26; k++) {
      for (int a = 0; a < 26; a++) {
        for (int b = 0; b < 26; b++) {
          y[a][b] = min(y[a][b], y[a][k] + y[k][b]);
          o[a][b] = min(o[a][b], o[a][k] + o[k][b]);
        }
      }
    }
    char X[9], Y[9];
    scanf("%s%s", X, Y);
    int a = *X - 'A', b = *Y - 'A', ans = 1e7;
    for (int meet = 0; meet < 26; meet++) {
      ans = min(ans, y[a][meet] + o[b][meet]);
    }
    if (ans == 1e7) {
      puts("You will never meet.");
    } else {
      printf("%d", ans);
      for (int meet = 0; meet < 26; meet++) {
        if (y[a][meet] + o[b][meet] == ans) {
          printf(" %c", meet + 'A');
        }
      }
      puts("");
    }
  }
  return 0;
}

UVa 436 - Arbitrage (II)

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    map<string, int> indexOf;
    for (int i = 0; i < n; i++) {
      char s[99];
      scanf("%s", s);
      indexOf[s] = i;
    }
    double change[30][30] = {};
    int m;
    scanf("%d", &m);
    while (m--) {
      char a[99], b[99];
      double arbitrage;
      scanf("%s%lf%s", a, &arbitrage, b);
      change[indexOf[a]][indexOf[b]] = arbitrage;
    }
    bool find = false;
    for (int k = 0; k < n && !find; k++) {
      for (int a = 0; a < n && !find; a++) {
        for (int b = 0; b < n; b++) {
          change[a][b] = max(change[a][b], change[a][k] * change[k][b]);
        }
        if (change[a][a] > 1.0) {
          find = true;
        }
      }
    }
    printf("Case %d: %s\n", C++, find ? "Yes" : "No");
  }
  return 0;
}

UVa 104 - Arbitrage

#include <cstdio>
#include <cstring>

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

int mid[20][20][20];

void showPath(int a, int b, int s) {
  if (mid[a][b][s] == -1) {
    printf("%d %d", a + 1, b + 1);
    return;
  }
  showPath(a, mid[a][b][s], s - 1);
  printf(" %d", b + 1);
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    memset(mid, -1, sizeof(mid));
    double change[20][20][20] = {};
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < n; b++) {
        if (a == b) {
          change[a][b][1] = 1.0;
        } else {
          scanf("%lf", &change[a][b][1]);
        }
      }
    }
    bool find = false;
    for (int s = 2; s <= n && !find; s++) {
      for (int k = 0; k < n; k++) {
        for (int a = 0; a < n; a++) {
          for (int b = 0; b < n; b++) {
            if (change[a][k][s - 1] * change[k][b][1] > change[a][b][s]) {
              change[a][b][s] = change[a][k][s - 1] * change[k][b][1];
              mid[a][b][s] = k;
            }
          }
        }
      }
      for (int a = 0; a < n && !find; a++) {
        if (change[a][a][s] >= 1.01) {
          showPath(a, a, s);
          puts("");
          find = true;
        }
      }
    }
    if (!find) {
      puts("no arbitrage sequence exists");
    }
  }
  return 0;
}

UVa 11015 - 05-2 Rendezvous

#include <cstdio>
#include <cstdlib>

int main() {
  int n, m, C = 1;
  while (scanf("%d%d", &n, &m) && n) {
    char name[99][99];
    int dis[99][99];
    for (int a = 1; a <= n; a++) {
      for (int b = 1; b <= n; b++) {
        dis[a][b] = (a == b ? 0 : 1e9);
      }
    }
    for (int a = 1; a <= n; a++) {
      scanf("%s", name[a]);
    }
    while (m--) {
      int a, b, d;
      scanf("%d%d%d", &a, &b, &d);
      dis[a][b] = dis[b][a] = d;
    }
    for (int k = 1; k <= n; k++) {
      for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
          if (dis[a][k] + dis[k][b] < dis[a][b]) {
            dis[a][b] = dis[a][k] + dis[k][b];
          }
        }
      }
    }
    int ans = 0, min = 1e9;
    for (int b = 1; b <= n; b++) {
      int sum = 0;
      for (int a = 1; a <= n; a++) {
        sum += dis[a][b];
      }
      if (sum < min) {
        min = sum;
        ans = b;
      }
    }
    printf("Case #%d : %s\n", C++, name[ans]);
  }
  return 0;
}

UVa 423 - MPI Maelstrom

#include <cstdio>
#include <cstdlib>

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int dis[101][101] = {};
    for (int a = 2; a <= n; a++) {
      for (int b = 1; b < a; b++) {
        char s[99];
        scanf("%s", s);
        dis[a][b] = dis[b][a] = (s[0] == 'x' ? 1e9 : atoi(s));
      }
    }
    for (int k = 1; k <= n; k++) {
      for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
          if (dis[a][k] + dis[k][b] < dis[a][b]) {
            dis[a][b] = dis[a][k] + dis[k][b];
          }
        }
      }
    }
    int ans = 0;
    for (int b = 1; b <= n; b++) {
      ans = dis[1][b] > ans ? dis[1][b] : ans;
    }
    printf("%d\n", ans);
  }
  return 0;
}

2013年8月17日

UVa 10916 - Factstone Benchmark

#include <cstdio>
#include <cmath>

int main() {
  int ans[217] = {};
  double limit[217] = {};
  for (int y = 196, bit = 4; y <= 216; y++, bit <<= 1) {
    ans[y] = ans[y - 1];
    limit[y] = limit[y - 1];
    while (limit[y] <= bit) {
      ans[y]++;
      limit[y] += log2(ans[y]);
    }
    limit[y] -= log2(ans[y]);
    ans[y]--;
  }
  int y;
  while (scanf("%d", &y) && y) {
    printf("%d\n", ans[y / 10]);
  }
  return 0;
}

UVa 11792 - Krochanska is Here!

#include <cstdio>
#include <vector>
#include <queue>
#define MP make_pair
#define PB push_back
using namespace std;

typedef pair<int, int> P;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, S;
    scanf("%d%d", &N, &S);
    int times[10001] = {};
    vector<int> con[10001];
    while (S--) {
      int pre, now;
      scanf("%d", &pre);
      if (!pre) {
        continue;
      }
      times[pre]++;
      while (scanf("%d", &now) && now) {
        times[now]++;
        con[pre].PB(now);
        con[now].PB(pre);
        pre = now;
      }
    }
    vector<int> important;
    for (int i = 1; i <= N; i++) {
      if (times[i] > 1) {
        important.PB(i);
      }
    }
    int min = 2e9, ans = 0;
    for (int i = 0; i < important.size(); i++) {
      int start = important[i];
      bool vis[10001] = {};
      vis[start] = true;
      queue<P> q;
      q.push(MP(start, 0));
      int sum = 0, found = 0;
      while (!q.empty()) {
        int now = q.front().first, dis = q.front().second;
        q.pop();
        if (times[now] > 1) {
          found++;
          sum += dis;
          if (found == important.size()) {
            break;
          }
        }
        for (int j = 0; j < con[now].size(); j++) {
          if (!vis[con[now][j]]) {
            vis[con[now][j]] = true;
            q.push(MP(con[now][j], dis + 1));
          }
        }
      }
      if (sum < min) {
        min = sum;
        ans = start;
      }
    }
    printf("Krochanska is in: %d\n", ans);
  }
  return 0;
}