2013年12月13日

UVa 12718 - Dromicpalin Substrings

#include <stdio.h>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    char s[1111];
    scanf("%s", s);
    int i, j, ans = 0;
    for (i = 0; s[i]; i++) {
      int cnt[26] = {}, odd = 0;
      for (j = i; s[j]; j++) {
        odd += (cnt[s[j] - 'a'] & 1) ? -1 : 1;
        cnt[s[j] - 'a']++;
        ans += (odd <= 1);
      }
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

UVa 12712 - Pattern Locker

#include <stdio.h>

int main() {
  long long mod = 1e13 + 7;
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int L, M, N;
    scanf("%d%d%d", &L, &M, &N);
    L *= L;
    long long i, ans = 0, sum = 1;
    for (i = 0; i < M - 1; i++) {
      sum = (sum * (L - i)) % mod;
    }
    for (; M <= N; M++) {
      sum = (sum * (L - M + 1)) % mod;
      ans = (ans + sum) % mod;
    }
    printf("Case %d: %lld\n", C++, ans);
  }
  return 0;
}

UVa 12709 - Falling Ants

#include <stdio.h>

int main() {
  int T;
  while (scanf("%d", &T) && T) {
    int L, W, H;
    int maxH = 0, maxV = 0;
    while (T--) {
      scanf("%d%d%d", &L, &W, &H);
      int v = L * W * H;
      if (H > maxH || (H == maxH && v > maxV)) {
        maxH = H;
        maxV = v;
      }
    }
    printf("%d\n", maxV);
  }
  return 0;
}

2013年11月16日

UVa 12673 - Football

#include <cstdio>
#include <algorithm>

struct S {
  int s1, s2;
  bool operator < (const S & other) const {
    return (s1 - s2) > (other.s1 - other.s2);
  }
} s[100000];

int main() {
  int N, G;
  while (scanf("%d%d", &N, &G) == 2) {
    for (int i = 0; i < N; i++) {
      scanf("%d%d", &s[i].s1, &s[i].s2);
    }
    std::sort(s, s + N);
    int sum = 0;
    for (int i = 0; i < N; i++) {
      int need = -(s[i].s1 - s[i].s2);
      if (need >= 0) {
        if (G > need) {
          G -= need + 1;
          need = -1;
        } else {
          need -= G;
          G = 0;
        }
      }
      sum += (need < 0) * 3 + !need;
    }
    printf("%d\n", sum);
  }
  return 0;
}

2013年11月1日

UVa 11956 - Brainfuck

#include <stdio.h>

int main() {
  int n, T = 1;
  scanf("%d\n", &n);
  char s[111111];
  while (n--) {
    gets(s);
    int i, v[100] = {}, now = 0;
    for (i = 0; s[i]; i++) {
      switch (s[i]) {
      case '>':
        now = (now + 1) % 100;
        break;
      case '<':
        now = (now + 100 - 1) % 100;
        break;
      case '+':
        v[now] = (v[now] + 1) % 256;
        break;
      case '-':
        v[now] = (v[now] + 256 - 1) % 256;
        break;
      }
    }
    printf("Case %d: ", T++);
    for (i = 0; i < 100; i++) {
      printf("%02X%s", v[i], i == 99 ? "\n" : " ");
    }
  }
  return 0;
}

2013年9月5日

UVa 338 - Long Multiplication

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

void rev(char * s) {
  char * head = s, * tail = s, c;
  while (*tail) {
    tail++;
  }
  tail--;
  while (head < tail) {
    c = *head;
    *head++ = *tail;
    *tail-- = c;
  }
}

string removeZero(string s) {
  while (s.length() > 1 && s[0] == '0') {
    s = s.substr(1);
  }
  return s;
}

string add(string s1, string s2) {
  int l1 = s1.length(), l2 = s2.length();
  char result[99];
  int d = 0, carry = 0;
  while (l1 || l2) {
    int digit = carry;
    if (l1) {
      digit += (s1[--l1] - '0');
    }
    if (l2) {
      digit += (s2[--l2] - '0');
    }
    result[d++] = digit % 10 + '0';
    carry = digit / 10;
  }
  if (carry) {
    result[d++] = carry + '0';
  }
  result[d++] = 0;
  rev(result);
  return removeZero(string(result));
}

string simpleMut(string s, char base) {
  int l = s.length();
  char result[99];
  int d = 0, carry = 0;
  while (l) {
    int digit = carry + (s[--l] - '0') * (base - '0');
    result[d++] = digit % 10 + '0';
    carry = digit / 10;
  }
  if (carry) {
    result[d++] = carry + '0';
  }
  result[d++] = 0;
  rev(result);
  return removeZero(string(result));
}

void solve(string s1, string s2) {
  s1 = removeZero(s1);
  s2 = removeZero(s2);
  int len = max(s1.length(), s2.length());
  string ans = "0";
  vector<string> process;
  for (int pos = s2.length() - 1; pos >= 0; pos--) {
    string result = simpleMut(s1, s2[pos]);
    process.PB(result);
    ans = add(ans, result + string(s2.length() - pos - 1, '0'));
  }
  len = max(len, (int)ans.length());
  printf("%*s\n", len, s1.c_str());
  printf("%*s\n", len, s2.c_str());
  printf("%*s\n", len, string(max(s1.length(), s2.length()), '-').c_str());
  int processNum = 0;
  for (int i = 0; i < process.size(); i++) {
    if (process[i] == "0" || (!processNum && i == process.size() - 1)) {
      continue;
    }
    printf("%*s\n", len - i, process[i].c_str());
    processNum++;
  }
  if (processNum > 1) {
    printf("%*s\n", len, string(len, '-').c_str());
  }
  if (processNum != 1) {
    printf("%*s\n", len, ans.c_str());
  }
}

int main() {
  char s[99];
  while (gets(s) && s[1]) {
    char s1[99], s2[99];
    sscanf(s, "%s%s", s1, s2);
    solve(s1, s2);
    puts("");
  }
  return 0;
}

UVa 271 - Simply Syntax

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

int main() {
  char s[999];
  while (gets(s)) {
    stack<char> exp;
    bool ok = true;
    for (int i = strlen(s) - 1; ok && i >= 0; i--) {
      if (s[i] >= 'p' && s[i] <= 'z') {
        exp.push(s[i]);
      } else if (s[i] == 'N') {
        if (!exp.size()) {
          ok = false;
        }
      } else if (s[i] == 'C' || s[i] == 'D' || s[i] == 'E' || s[i] == 'I') {
        if (exp.size() >= 2) {
          exp.pop();
        } else {
          ok = false;
        }
      }
    }
    puts((exp.size() == 1 && ok) ? "YES" : "NO");
  }
  return 0;
}

2013年9月4日

UVa 10912 - Simple Minded Hashing

#include <cstdio>

int main() {
  int L, S, C = 1;
  int dp[27][352][27] = {};
  for (int t = 1; t <= 26; t++) {
    dp[1][t][t] = 1;
  }
  for (int l = 2; l <= 26; l++) {
    for (int s = 351; s; s--) {
      for (int pre = 0; pre < 26; pre++) {
        for (int tail = pre + 1; tail <= 26 && tail <= s; tail++) {
          dp[l][s][tail] += dp[l - 1][s - tail][pre];
        }
      }
    }
  }
  while (scanf("%d%d", &L, &S) && L) {
    int ans = 0;
    if (L <= 26 && S <= 351) {
      for (int t = 1; t <= 26; t++) {
        ans += dp[L][S][t];
      }
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

UVa 11420 - Chest of Drawers

#include <cstdio>

int main() {
  long long dp[66][66][2] = {};
  dp[1][0][0] = dp[1][1][1] = 1;
  for (int i = 2; i < 66; i++) {
    for (int j = 0; j <= i; j++) {
      dp[i][j][0] = dp[i - 1][j][0];
      if (j) {
        dp[i][j][1] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1];
      }
      if (j != i) {
        dp[i][j][0] += dp[i - 1][j + 1][1];
      }
    }
  }
  int n, s;
  while (scanf("%d%d", &n, &s) && n > 0) {
    printf("%lld\n", dp[n][s][0] + dp[n][s][1]);
  }
  return 0;
}

UVa 196 - Spreadsheet

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

int grid[1000][18279];
char formula[1000][18279][100];
bool done[1000][18279];

int solve(int r, int c) {
  if (done[r][c]) {
    return grid[r][c];
  }
  for (int i = 0; formula[r][c][i]; i++) {
    if (formula[r][c][i] == '+' || formula[r][c][i] == '=') {
      formula[r][c][i] = ' ';
    }
  }
  istringstream ss(formula[r][c]);
  string s;
  int sum = 0;
  while (ss >> s) {
    int r = 0, c = 0;
    for (int i = 0; s[i]; i++) {
      if (isdigit(s[i])) {
        r = r * 10 + (s[i] - '0');
      } else {
        c = c * 26 + (s[i] - 'A' + 1);
      }
    }
    sum += solve(r, c);
  }
  done[r][c] = true;
  return (grid[r][c] = sum);
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int R, C;
    scanf("%d%d", &C, &R);
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        scanf("%s", formula[r][c]);
        done[r][c] = false;
        if (isdigit(formula[r][c][0])) {
          done[r][c] = true;
          grid[r][c] = atoi(formula[r][c]);
        }
      }
    }
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        printf("%d%s", solve(r, c), c == C ? "\n" : " ");
      }
    }
  }
  return 0;
}

UVa 10898 - Combo Deal

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

struct Combo {
  Combo() {
    for (int i = 0; i < 6; i++) {
      num[i] = 0;
    }
  }
  int num[6], price;
};

int best[1000000];

int main() {
  int N;
  while (scanf("%d", &N) == 1) {
    vector<Combo> combos;
    for (int i = 0; i < N; i++) {
      Combo combo;
      scanf("%d", &combo.price);
      combo.num[i] = 1;
      combos.PB(combo);
    }
    int M;
    scanf("%d", &M);
    while (M--) {
      Combo combo;
      for (int i = 0; i < N; i++) {
        scanf("%d", &combo.num[i]);
      }
      scanf("%d", &combo.price);
      combos.PB(combo);
    }
    int last = 0;
    for (int i = 0; i < N; i++) {
      last = last * 10 + 9;
    }
    for (int i = 1; i <= last; i++) {
      best[i] = 2e9;
    }
    best[0] = 0;
    for (int price = 0; price <= last; price++) {
      if (best[price] == 2e9) {
        continue;
      }
      int num[6] = {};
      for (int temp = price, d = N - 1; temp; temp /= 10, d--) {
        num[d] = temp % 10;
      }
      for (int i = 0; i < combos.size(); i++) {
        int next[6] = {}, index = 0;
        bool push = true;
        for (int j = 0; j < N && push; j++) {
          next[j] = num[j] + combos[i].num[j];
          index = index * 10 + next[j];
          push = (next[j] <= 9);
        }
        if (!push) {
          continue;
        }
        best[index] = min(best[index], best[price] + combos[i].price);
      }
    }
    scanf("%d", &M);
    while (M--) {
      int index = 0;
      for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        index = index * 10 + num;
      }
      printf("%d\n", best[index]);
    }
  }
  return 0;
}

UVa 10911 - Forming Quiz Teams

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

inline double dis(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
  int bits[17] = {1};
  for (int b = 1; b < 17; b++) {
    bits[b] = bits[b - 1] << 1;
  }
  int N, C = 1;
  while (scanf("%d", &N) && N) {
    N <<= 1;
    int x[16], y[16];
    for (int i = 0; i < N; i++) {
      scanf("%*s%d%d", &x[i], &y[i]);
    }
    int last = bits[N];
    double dp[1 << 16];
    dp[0] = 0;
    for (int state = 1; state < last; state++) {
      bool found = false;
      for (int i = 0; bits[i] < state; i++) {
        for (int j = i + 1; bits[j] < state; j++) {
          if (state & bits[i] && state & bits[j]) {
            double sum = dp[state ^ bits[i] ^ bits[j]] + dis(x[i], y[i], x[j], y[j]);
            dp[state] = min(found ? dp[state] : 2e9, sum);
            found = true;
          }
        }
      }
    }
    printf("Case %d: %.2lf\n", C++, dp[last - 1]);
  }
  return 0;
}

2013年9月3日

UVa 10389 - Subway

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

typedef pair<int, int> P;

struct State {
  State(P p, double need) : p(p), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  P p;
  double need;
};

const double mpm[2] = {10000 / 60.0, 40000 / 60.0};

inline double dis(P & a, P & b) {
  int dx = a.first - b.first, dy = a.second - b.second;
  return sqrt(dx * dx + dy * dy);
}

int main() {
  char temp[9999];
  gets(temp);
  int T;
  sscanf(temp, "%d", &T);
  gets(temp);
  while (T--) {
    gets(temp);
    int sx, sy, ex, ey;
    sscanf(temp, "%d%d%d%d", &sx, &sy, &ex, &ey);
    P s = MP(sx, sy), e = MP(ex, ey);
    vector<P> walk;
    map<P, vector<P> > next;
    walk.PB(e);
    while (gets(temp) && *temp) {
      istringstream ss(temp);
      int x, y;
      vector<P> v;
      while (ss >> x >> y) {
        if (x < 0) {
          break;
        }
        v.PB(MP(x, y));
      }
      for (int i = 0; i < v.size(); i++) {
        walk.PB(v[i]);
        if (i) {
          next[v[i]].PB(v[i - 1]);
        }
        if (i < v.size() - 1) {
          next[v[i]].PB(v[i + 1]);
        }
      }
    }
    priority_queue<State> pq;
    map<P, double> best;
    best[s] = 0;
    pq.push(State(s, 0));
    while (!pq.empty()) {
      P now = pq.top().p;
      double need = pq.top().need;
      pq.pop();
      if (now == e) {
        printf("%.0lf\n", need);
        break;
      }
      for (int i = 0; i < walk.size(); i++) {
        P & j = walk[i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[0];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
      for (int i = 0; i < next[now].size(); i++) {
        P & j = next[now][i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[1];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 1112 - Mice and Maze

WA for 7 times just beacuse I always use T as variable of case number.
#include <cstdio>
#include <vector>
#include <queue>
#define PB push_back
using namespace std;

struct State {
  State(int now, int need) : now(now), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  int now, need;
};

int main() {
  int Case;
  scanf("%d", &Case);
  while (Case--) {
    int N, E, T, M, need[101][101];
    vector<int> con[101];
    scanf("%d%d%d%d", &N, &E, &T, &M);
    while (M--) {
      int a, b, t;
      scanf("%d%d%d", &a, &b, &t);
      con[b].PB(a);
      need[b][a] = t;
    }
    int best[101];
    for (int i = 1; i <= N; i++) {
      best[i] = 1e8;
    }
    best[E] = 0;
    priority_queue<State> pq;
    pq.push(State(E, 0));
    while (!pq.empty()) {
      int now = pq.top().now, use = pq.top().need;
      pq.pop();
      if (use > T) {
        break;
      }
      for (int i = 0; i < con[now].size(); i++) {
        int j = con[now][i];
        if (use + need[now][j] < best[j]) {
          best[j] = use + need[now][j];
          pq.push(State(j, best[j]));
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
      ans += (best[i] <= T);
    }
    printf("%d\n", ans);
    if (Case) {
      puts("");
    }
  }
  return 0;
}

UVa 10718 - Bit Mask

#include <cstdio>

int main() {
  long long N, L, U, bits[33] = {1};
  for (int b = 1; b < 33; b++) {
    bits[b] = bits[b - 1] << 1;
  }
  while (scanf("%lld%lld%lld", &N, &L, &U) == 3 ) {
    long long ans = 0;
    for (int b = 32; b >= 0; b--) {
      if (N & bits[b]) {
        if (ans + bits[b] <= L) {
          ans += bits[b];
        }
      } else if (ans + bits[b] <= U) {
        ans += bits[b];
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

2013年9月2日

UVa 10926 - How Many Dependencies?

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

int n;
vector<int> con[101];
bool vis[101];

void dfs(int i) {
  vis[i] = true;
  for (int j = 0; j < con[i].size(); j++) {
    if (!vis[con[i][j]]) {
      dfs(con[i][j]);
    }
  }
}

int main() {
  while (scanf("%d", &n) && n) {
    for (int i = 1; i <= n; i++) {
      con[i].clear();
      int num;
      scanf("%d", &num);
      while (num--) {
        int j;
        scanf("%d", &j);
        con[i].PB(j);
      }
    }
    int ans, maxDep = 0;
    for (int i = 1; i <= n; i++) {
      memset(vis, false, sizeof(vis));
      dfs(i);
      int dep = 0;
      for (int j = 1; j <= n; j++) {
        dep += vis[j];
      }
      if (dep > maxDep) {
        maxDep = dep;
        ans = i;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 501 - Black Box

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

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int M, N, num[30000];
    scanf("%d%d", &M, &N);
    for (int i = 0; i < M; i++) {
      scanf("%d", &num[i]);
    }
    vector<int> box;
    int done = 0, need = 0;
    while (N--) {
      int index;
      scanf("%d", &index);
      while (box.size() < index) {
        vector<int>::iterator it = lower_bound(box.begin(), box.end(), num[done]);
        box.insert(it, num[done++]);
      }
      printf("%d\n", box[need++]);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 450 - Little Black Book

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

struct Data {
  Data (string title,
        string firstName,
        string lastName, 
        string address,
        string department,
        string homePhone,
        string workPhone,
        string campusBox)

    :   title(title),
        firstName(firstName),
        lastName(lastName),
        address(address),
        department(department),
        homePhone(homePhone),
        workPhone(workPhone),
        campusBox(campusBox) {}

  bool operator<(const Data & other) const {
    return lastName < other.lastName;
  }
  string title, firstName, lastName;
  string address, department, homePhone, workPhone, campusBox;
};

int main() {
  vector<Data> lists;
  char temp[9999];
  gets(temp);
  int N;
  sscanf(temp, "%d", &N);
  while (N--) {
    char department[99];
    gets(department);
    while (gets(temp) && temp[0]) {
      string s(temp);
      int comma[6];
      comma[0] = s.find(',');
      for (int i = 1; i < 6; i++) {
        comma[i] = s.find(',', comma[i - 1] + 1);
      }
      lists.PB(Data(s.substr(0, comma[0]),
                    s.substr(comma[0] + 1, comma[1] - comma[0] - 1),
                    s.substr(comma[1] + 1, comma[2] - comma[1] - 1),
                    s.substr(comma[2] + 1, comma[3] - comma[2] - 1),
                    department,
                    s.substr(comma[3] + 1, comma[4] - comma[3] - 1),
                    s.substr(comma[4] + 1, comma[5] - comma[4] - 1),
                    s.substr(comma[5] + 1)));
    }
  }
  sort(lists.begin(), lists.end());
  for (int i = 0; i < lists.size(); i++) {
    Data & data = lists[i];
    puts("----------------------------------------");
    printf("%s %s %s\n", data.title.c_str(), data.firstName.c_str(), data.lastName.c_str());
    puts(data.address.c_str());
    printf("Department: %s\n", data.department.c_str());
    printf("Home Phone: %s\n", data.homePhone.c_str());
    printf("Work Phone: %s\n", data.workPhone.c_str());
    printf("Campus Box: %s\n", data.campusBox.c_str());
  }
  return 0;
}

UVa 11310 - Delivery Debacle

#include <cstdio>

int main() {
  long long f[41] = {1, 1, 5};
  for (int i = 3; i <= 40; i++) {
    f[i] = f[i - 1] + 4 * f[i - 2] + 2 * f[i - 3];
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    printf("%lld\n", f[n]);
  }
  return 0;
}

UVa 11492 - Babel

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

struct Node {
  Node(int index, int len, int head) : index(index), len(len), head(head) {}
  bool operator<(const Node & other) const {
    return (len > other.len);
  }
  int index, len, head;
};

const int SIZE = 4000;

int main() {
  int M;
  while (scanf("%d", &M) && M) {
    vector<int> con[SIZE], d[SIZE], letter[SIZE];
    char start[99], end[99];
    scanf("%s%s", start, end);
    map<string, int> indexOf;
    int N = 0;
    while (M--) {
      char s1[99], s2[99], word[99];
      scanf("%s%s%s", s1, s2, word);
      int a, b;
      if (indexOf.find(s1) != indexOf.end()) {
        a = indexOf[s1];
      } else {
        a = N;
        indexOf[s1] = N++;
      }
      if (indexOf.find(s2) != indexOf.end()) {
        b = indexOf[s2];
      } else {
        b = N;
        indexOf[s2] = N++;
      }
      con[a].PB(b);
      con[b].PB(a);
      int len = string(word).length();
      d[a].PB(len);
      d[b].PB(len);
      letter[a].PB(word[0] - 'a');
      letter[b].PB(word[0] - 'a');
    }
    if (string(start) == string(end)) {
      puts("0");
    } else if (indexOf.find(start) != indexOf.end() && indexOf.find(end) != indexOf.end()) {
      priority_queue<Node> pq;
      pq.push(Node(indexOf[start], 0, -1));
      int dis[SIZE][26];
      for (int i = 0; i < N; i++) {
        fill(dis[i], dis[i] + 26, 1e8);
      }
      while (!pq.empty()) {
        Node now = pq.top();
        pq.pop();
        int a = now.index;
        for (int i = 0; i < con[a].size(); i++) {
          int b = con[a][i];
          int head = letter[a][i];
          if (now.head != head && now.len + d[a][i] < dis[b][head]) {
            dis[b][head] = now.len + d[a][i];
            pq.push(Node(b, dis[b][head], head));
          }
        }
      }
      int ans = 1e8;
      for (int i = 0; i < 26; i++) {
        ans = min(ans, dis[indexOf[end]][i]);
      }
      if (ans >= 1e8) {
        puts("impossivel");
      } else {
        printf("%d\n", ans);
      }
    } else {
      puts("impossivel");
    }
  }
  return 0;
}

2013年9月1日

UVa 11389 - The Bus Driver Problem

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
 
int main() {
  int n, d, r;
  while (scanf("%d%d%d", &n, &d, &r) && n) {
    vector<int> len[2];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < n; j++) {
        int l;
        scanf("%d", &l);
        len[i].PB(l);
      }
      sort(len[i].begin(), len[i].end());
    }
    int ans = 0;
    for (int i = 0; i < len[0].size(); i++) {
      int price = (len[0][i] + len[1][n - i - 1] - d) * r;
      ans += price < 0 ? 0 : price;
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 11003 - Boxes

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

const int SIZE = 3000 + 1;
int num[1001][SIZE], load[1001][SIZE];

int main() {
  int N;
  while (scanf("%d", &N) && N) {
    memset(num, 0, sizeof(num));
    memset(load, 0, sizeof(load));
    load[0][0] = 2e9;
    int ans = 0, limit = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= limit; j++) {
        num[i][j] = num[i - 1][j];
        load[i][j] = load[i - 1][j];
      }
      int w, l;
      scanf("%d%d", &w, &l);
      limit = max(limit, l);
      for (int j = 0; j <= limit; j++) {
        if (load[i - 1][j] >= w) {
          int newNum = num[i - 1][j] + 1, newLoad = min(load[i - 1][j] - w, l);
          if ((num[i][newLoad] < newNum) || ((num[i][newLoad] == newNum) && (load[i][newLoad] < newLoad))) {
            num[i][newLoad] = newNum;
            load[i][newLoad] = newLoad;
            ans = max(ans, newNum);
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 1209 - Wordfish

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

int main() {
  char s[99];
  while (gets(s)) {
    int len = string(s).length();
    for (int i = 0; i < 10; i++) {
      prev_permutation(s, s + len);
    }
    int dis = 0;
    string ans;
    for (int i = 0; i < 21; i++) {
      int d = 2e9;
      for (int i = 1; s[i]; i++) {
        d = min(d, abs(s[i] - s[i - 1]));
      }
      if (d > dis) {
        dis = d;
        ans = s;
      }
      next_permutation(s, s + len);
    }
    printf("%s%d\n", ans.c_str(), dis);
  }
  return 0;
}

UVa 10616 - Divisible Group Sums

#include <cstdio>

int main() {
  int N, Q, S = 1;
  while (scanf("%d%d", &N, &Q) && N) {
    printf("SET %d:\n", S++);
    int num[200];
    for (int i = 0; i < N; i++) {
      scanf("%d", &num[i]);
    }
    int q = 1;
    while (Q--) {
      int D, M;
      scanf("%d%d", &D, &M);
      long long dp[11][20] = {1};
      for (int i = 0; i < N; i++) {
        for (int m = M; m; m--) {
          for (int r = 0; r < D; r++) {
            dp[m][r] += dp[m - 1][(r - num[i] % D + D) % D];
          }
        }
      }
      printf("QUERY %d: %lld\n", q++, dp[M][0]);
    }
  }
  return 0;
}

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