2012年11月30日

UVa 11074 - Draw Grid


#include <stdio.h>

char map[1000][1000];

int main() {
  int s, t, n, test = 1;
  while (scanf("%d%d%d", &s, &t, &n) && s) {
    printf("Case %d:\n", test++);
    int r, c, l = s * n + t * (n + 1);
    for (r = 1; r <= l; r++) {
      for (c = 1; c <= l; c++)
        map[r][c] = '*';
      map[r][c] = 0;
    }
    int sr, sc;
    for (sr = t + 1; sr < l; sr += s + t)
      for (sc = t + 1; sc < l; sc += s + t) {
        int er, ec;
        for (er = sr; er < sr + s; er++)
          for (ec = sc; ec < sc + s; ec++)
            map[er][ec] = '.';
      }
    for (r = 1; r <= l; r++)
      puts(map[r] + 1);
    puts("");
  }
  return 0;
}

2012年11月27日

UVa 10027 - Language Cardinality


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

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  getchar();
  while (n--) {
    int now, l;
    char init[50];
    set<string> dic;
    gets(init);
    for (l = 0; init[l]; l++);
    init[l - 1] = '\0';
    dic.insert(string(init + 1));
    int num = 0, len[200], inf = 0;
    char s[100], ori[20][100], rep[20][100];
    while (gets(s) && s[0]) {
      int l1 = 0, l2 = 0;
      for (l = 1; s[l]; l++)
        if (s[l] == '\"') break;
        else ori[num][l1++] = s[l];
      ori[num][l1] = '\0';
      len[num] = l1;
      for (l += 4; s[l]; l++)
        if (s[l] == '\"') break;
        else rep[num][l2++] = s[l];
      rep[num][l2] = '\0';
      if (!l1 && l2) {
        inf = 1;
      } else if (l1 && l2 && l1 != l2) {
        int loc = string(rep[num]).find(ori[num]);
        if (loc >= 0 && loc < l2) inf = 1;
      }
      num++;
    }
    for (now = 0; now < num && !inf; now++) {
      int rec = dic.size();
      for (set<string>::iterator it = dic.begin(); it != dic.end() && !inf; it++) {
        string temp = *it;
        int start, add = 0;
        while (!inf) {
          start = temp.find(ori[now], add++);
          if (start < 0 || start >= temp.length()) break;
          string next(temp);
          next.erase(start, len[now]);
          next.insert(start, rep[now]);
          dic.insert(next);
          if (dic.size() > 1000) inf = 1;
        }
      }
      if (rec != dic.size()) now = -1;
    }
    if (!inf) printf("%d\n", dic.size());
    else puts("Too many.");
    if (n) puts("");
  }
  return 0;
}

UVa 762 - We Ship Cheap

STL, STL, and STL! lol
#include <cstdio>
#include <string>
#include <map>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<string, string> P;

void print(map<string, string> parent, string now) {
  if (now.compare(parent[now]) == 0) return;
  print(parent, parent[now]);
  printf("%s %s\n", parent[now].c_str(), now.c_str());
}

int main() {
  int n, first = 1;
  while (scanf("%d", &n) == 1) {
    if (!first) puts("");
    first = 0;
    set<string> road;
    set<P> con;
    while (n--) {
      char s1[20], s2[20];
      scanf("%s%s", s1, s2);
      road.insert(string(s1));
      road.insert(string(s2));
      con.insert(MP(string(s1), string(s2)));
      con.insert(MP(string(s2), string(s1)));
    }
    char s[20], e[20];
    scanf("%s%s", s, e);
    map<string, string> parent;
    map<string, int> d;
    set<string> visit;
    for (set<string>::iterator it = road.begin(); it != road.end(); it++)
      d[*it] = 2e9;
    d[s] = 0;
    parent[s] = s;
    while (1) {
      int min = 2e9, flag = 0;
      set<string>::iterator now;
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (!visit.count(*it) && d[*it] < min) min = d[*it], now = it, flag = 1;
      if (!flag) break;
      visit.insert(*now);
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (con.count(MP(*it, *now)) && !visit.count(*it) && d[*now] + 1 < d[*it]) {
          d[*it] = d[*now] + 1;
          parent[*it] = *now;
        }
    }
    if (!road.count(s) || !road.count(e) || d[e] == 2e9)puts("No route");
    else print(parent, e);
  }
  return 0;
}

UVa 599 - The Forrest for the Trees


#include <stdio.h>

int i, num[26], team[26];

void u(int a, int b) {
  int t1 = team[a], t2 = team[b];
  for (i = 0; i < 26; i++)
    if (team[i] == t2) num[t1]++, num[t2]--, team[i] = t1;
}

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  while (n--) {
    char s[200] = {};
    for (i = 0; i < 26; i++)
      num[i] = 1, team[i] = i;
    while (gets(s) && s[0] != '*')
      u(s[1] - 'A', s[3] - 'A');
    char t[200] = {};
    gets(t);
    int check[26] = {}, tree = 0, acorn = 0;
    for (i = 0; t[i]; i += 2) {
      int now = team[t[i] - 'A'];
      if (!check[now]) {
        check[now] = 1;
        if (num[now] == 1) acorn++;
        else tree++;
      }
    }
    printf("There are %d tree(s) and %d acorn(s).\n", tree, acorn);
  }
  return 0;
}

UVa 336 - A Node Too Far


#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<int, int> P;

int main() {
  int i, n, c = 1;
  while (scanf("%d", &n) && n) {
    map<int, vector<int> > road;
    set<int> number;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      number.insert(a);
      number.insert(b);
      road[a].push_back(b);
      road[b].push_back(a);
    }
    int s, l;
    while (scanf("%d%d", &s, &l) && s || l) {
      queue<P> q;
      set<int> visit;
      visit.insert(s);
      q.push(MP(s, 0));
      int ans = 0;
      while (!q.empty()) {
        int now = q.front().first, dis = q.front().second;
        q.pop();
        if (dis <= l) ans++;
        else break;
        for (i = 0; i < road[now].size(); i++) {
          int next = road[now][i];
          if (!visit.count(next)) {
            q.push(MP(next, dis + 1));
            visit.insert(next);
          }
        }
      }
      printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", c++, number.size() - ans, s, l);
    }
  }
  return 0;
}

2012年11月26日

UVa 10004 - Bicoloring


#include <cstdio>
#include <vector>

std::vector<int> v[210];
int flag, rec[210];

void dfs(int now, int c) {
  if (!flag) return;
  rec[now] = c;
  for (int i = 0; i < v[now].size(); i++)
    if (rec[v[now][i]] == -1) dfs(v[now][i], !c);
    else if (rec[v[now][i]] == c) flag = 0;
}

int main() {
  int n, m, c = 1;
  while (scanf("%d", &n) && n) {
    int a, b;
    for (a = 0; a <= n; a++) {
      v[a].clear();
      rec[a] = -1;
    }
    scanf("%d", &m);
    while (m--) {
      scanf("%d%d", &a, &b);
      v[a].push_back(b);
      v[b].push_back(a);
    }
    flag = 1;
    dfs(0, 0);
    if (flag) puts("BICOLORABLE.");
    else puts("NOT BICOLORABLE.");
  }
  return 0;
} 

2012年11月22日

UVa 10986 - Sending email


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

typedef pair<int, int> P;

int main() {
  int i, j, k, C, N;
  scanf("%d", &N);
  for (C = 1; C <= N; C++) {
    int n, m, S, T;
    scanf("%d%d%d%d", &n, &m, &S, &T);
    map<P, int> dis;
    vector<int> v[20005];
    for (i = 0; i < m; i++) {
      int a, b, w;
      scanf("%d%d%d", &a, &b, &w);
      dis[MP(a, b)] = dis[MP(b, a)] = w;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    int d[20005];
    for (i = 0; i < n; i++)
      d[i] = 2e9;
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
      int a = q.front(), b;
      q.pop();
      for (i = 0; i < v[a].size(); i++) {
        b = v[a][i];
        if (dis.count(MP(a, b))) {
          int w = dis[MP(a, b)];
          if (d[a] + w < d[b]) {
            d[b] = d[a] + w;
            q.push(b);
          }
        }
      }
    }
    printf("Case #%d: ", C);
    if (d[T] != 2e9) printf("%d\n", d[T]);
    else puts("unreachable");
  }
  return 0;
}

2012年11月21日

UVa 10801 - Lift Hopping


#include <stdio.h>

int main() {
  int n, i, j, k, E;
  while (scanf("%d %d", &n, &E) == 2) {
    getchar();
    int t[100];
    for (i = 0; i < n; i++) {
      scanf("%d", &t[i]);
      getchar();
    }
    int max[5] = {}, d[5][100], visit[5][100] = {}, ok[5][100] = {};
    for (i = 0; i < 5; i++)
      for (j = 0; j < 100; j++)
        d[i][j] = 1e9;
    for (i = 0; i < n; i++) {
      char temp[200];
      gets(temp);
      int sum = 0;
      for (j = 0; ; j++)
        if ('0' <= temp[j] && temp[j] <= '9') {
          sum = sum * 10 + temp[j] - '0';
        } else {
          ok[i][sum] = 1;
          max[i] = sum > max[i] ? sum : max[i];
          if (!sum) d[i][0] = 0;
          sum = 0;
          if (!temp[j]) break;
        }
    }
    int ans = -1;
    while (1) {
      int type = -1, h, min = 1e9;
      for (i = 0; i < n; i++)
        for (j = 0; j <= max[i]; j++)
        if (ok[i][j] && !visit[i][j] && d[i][j] < min) {
          min = d[i][j];
          type = i;
          h = j;
        }
        if (type == -1) break;
        if (h == E) {
          ans = min;
          break;
        }
        visit[type][h] = 1;
        for (i = 0; i < n; i++)
          for (j = 0; j <= max[i]; j++)
            if (ok[i][j] && !visit[i][j]) {
              int w = d[type][h] + t[i] * ((j - h) < 0 ? (h - j) : (j - h));
              if (i == type) {
                if (w < d[i][j]) d[i][j] = w;
              } else if (j == h) {
                if (w + 60 < d[i][j]) d[i][j] = w + 60;
              }
            }
    }
    if (ans != -1) printf("%d\n", ans);
    else puts("IMPOSSIBLE");
  }
  return 0;
}

2012年11月12日

UVa 314 - Robot


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

typedef pair<int, int> P;

int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int word[] = {'s', 'e', 'n', 'w'};
int r0, c0, r1, c1;

int BFS(int dir, set<P> ok) {
  int i;
  queue<pair<P, int> > q;
  map<pair<P, int>, int> visit;
  visit[MP(MP(r0, c0), dir)] = 0;
  q.push(MP(MP(r0, c0), dir));
  while (!q.empty()) {
    int r = q.front().first.first, c = q.front().first.second, dis = visit[q.front()];
    if (r == r1 && c == c1) return dis;
    int d = q.front().second, times;
    q.pop();
    P p;
    for (times = 1; times < 4; times++) {
      p = MP(r + dr[d] * times, c + dc[d] * times);
      if (!ok.count(p)) break;
      if (visit.count(MP(p, d))) continue;
      visit[MP(p, d)] = dis + 1;
      q.push(MP(p, d));
    }
    int left, right;
    right = (d + 1) % 4;
    p = MP(r, c);
    if (ok.count(p) && !visit.count(MP(p, right))) {
      visit[MP(p, right)] = dis + 1;
      q.push(MP(p, right));
    }
    left = (d + 4 - 1) % 4;
    if (!visit.count(MP(p, left))) {
      visit[MP(p, left)] = dis + 1;
      q.push(MP(p, left));
    }
  }
  return -1;
}

int main() {
  int i, j, r, c;
  while (scanf("%d%d", &r, &c) && r || c) {
    int grid[50][50];
    set<P> ok;
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++) {
        scanf("%d", &grid[i][j]);
        if (!grid[i][j]) ok.insert(MP(i, j));
      }
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
        if (grid[i][j]) {
          ok.erase(MP(i, j));
          ok.erase(MP(i, j + 1));
          ok.erase(MP(i + 1, j));
          ok.erase(MP(i + 1, j + 1));
        }
    for (i = 0; i <= r; i++) {
      ok.erase(MP(i, 0));
      ok.erase(MP(i, c));
    }
    for (i = 0; i <= c; i++) {
      ok.erase(MP(0, i));
      ok.erase(MP(r, i));
    }
    char dir[20];
    scanf("%d%d%d%d%s", &r0, &c0, &r1, &c1, dir);
    if (!ok.count(MP(r1, c1))) {
      puts("-1");
      continue;
    }
    int d;
    for (d = 0; d < 4; d++)
      if (word[d] == dir[0]) break;
    printf("%d\n", BFS(d, ok));
  }
  return 0;
}

UVa 785 - Grid Colouring


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

typedef pair<int, int> P;

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

int main() {
  int n;
  char grid[100][100];
  while (gets(grid[0]) != NULL) {
    set<P> ok;
    map<P, int> visit;
    queue<pair<P, char> > start;
    int r, c, r0, c0;
    for (r = 1; ; r++) {
      gets(grid[r]);
      if (grid[r][0] == '_') break;
      for (c = 0; grid[r][c]; c++) {
        if (grid[r][c] != 'X') ok.insert(MP(r, c));
        if (grid[r][c] != 'X' && grid[r][c] != ' ') {
          ok.insert(MP(r, c));
          start.push(MP(MP(r, c), grid[r][c]));
        }
      }
    }
    while (!start.empty()) {
      queue<P> q;
      q.push(MP(start.front().first.first, start.front().first.second));
      char ch = start.front().second;
      while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
          P p = MP(r + dr[i], c + dc[i]);
          if (visit.count(p) || !ok.count(p)) continue;
          grid[r + dr[i]][c + dc[i]] = ch;
          q.push(p);
          visit[p] = 1;
        }
      }
      start.pop();
    }
    for (r = 0; ; r++) {
      puts(grid[r]);
      if (grid[r][0] == '_') break;
    }
  }
  return 0;
}