2013年7月31日

UVa 10150 - Doublets

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

struct Word {
  Word(string s, int index) : s(s), index(index) {}
  string s;
  int index;
};

typedef pair<Word, vector<string> > P;

bool ok(string & a, string & b) {
  int diff = 0;
  for (int i = 0; a[i]; i++) {
    diff += (a[i] != b[i]);
  }
  return diff <= 1;
}

vector<string> dic[99];
vector<int> con[99][29999];

int main() {
  char s[99];
  while (gets(s) && s[0]) {
    dic[string(s).length()].push_back(s);
  }

  for (int i = 1; i <= 16; i++) {
    for (int j = 0; j < dic[i].size(); j++) {
      for (int k = 0; k < dic[i].size(); k++) {
        if (j == k) {
          continue;
        }
        if (ok(dic[i][j], dic[i][k])) {
          con[i][j].push_back(k);
        }
      }
    }
  }

  bool first = true;

  while (gets(s)) {
    printf("%s", first ? "" : "\n");
    first = false;
    char t1[99], t2[99];
    sscanf(s, "%s%s", t1, t2);
    int i1, i2, len = string(t1).length();
    if (string(t2).length() != len) {
      puts("No solution.");
      continue;
    }
    for (int i = 0; i < dic[len].size(); i++) {
      if (dic[len][i] == t1) {
        i1 = i;
        break;
      }
    }
    Word now(t1, i1);
    string target(t2);
    queue<P> q;
    vector<string> path;
    path.push_back(t1);
    q.push(MP(now, path));
    bool find = false, visited[29999] = {};
    while (!q.empty()) {
      now = q.front().first;
      path = q.front().second;
      q.pop();
      if (now.s == target) {
        for (int i = 0; i < path.size(); i++) {
          puts(path[i].c_str());
        }
        find = true;
        break;
      }
      for (int i = 0; i < con[len][now.index].size(); i++) {
        int j = con[len][now.index][i];
        if (!visited[j]) {
          vector<string> newP = path;
          string newS = dic[len][j];
          newP.push_back(newS);
          q.push(MP(Word(newS, j), newP));
          visited[j] = true;
        }
      }
    }
    if (!find) {
      puts("No solution.");
    }
  }

  return 0;
}

UVa 10610 - Gopher and Hawks

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

struct P {
  P (double x, double y) : x(x), y(y), len(0) {}
  bool operator==(P other) const {
    return (fabs(x - other.x) <= 1e-5) && (fabs(y - other.y) <= 1e-5);
  }
  double x, y;
  int len;
};

double dis(P a, P b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() {
  char s[99];
  int v, m;
  while (gets(s)) {
    sscanf(s, "%d%d", &v, &m);
    if (!v && !m) {
      break;
    }
    double x, y;
    gets(s);
    sscanf(s, "%lf%lf", &x, &y);
    P start(x, y);
    gets(s);
    sscanf(s, "%lf%lf", &x, &y);
    P end(x, y);
    vector<P> all;
    while (gets(s) && s[0]) {
      sscanf(s, "%lf%lf", &x, &y);
      all.push_back(P(x, y));
    }
    all.push_back(end);
    queue<P> q;
    q.push(start);
    bool find = false;
    bool visit[9999] = {};
    while (!q.empty()) {
      P now = q.front();
      q.pop();
      if (now == end) {
        printf("Yes, visiting %d other holes.\n", now.len >= 1 ? now.len - 1 : now.len);
        find = true;
        break;
      }
      for (int i = 0; i < all.size(); i++) {
        if (!visit[i] && (dis(now, all[i]) < (m * m * 60.0 * 60.0 * v * v))) {
          all[i].len = now.len + 1;
          q.push(all[i]);
          visit[i] = true;
        }
      }
    }
    if (!find) {
      puts("No.");
    }
  }
  return 0;
}

UVa 924 - Spreading The News

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

int main() {
  int e;
  scanf("%d", &e);
  vector<int> knows[2500];
  for (int i = 0, n, id; i < e; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d", &id);
      knows[i].push_back(id);
    }
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int source;
    scanf("%d", &source);
    bool hear[2500] = {};
    hear[source] = true;
    vector<int> list;
    list.push_back(source);
    int day = 1, max = 0, ans = 0;
    while (list.size()) {
      vector<int> newList;
      for (int i = 0; i < list.size(); i++) {
        for (int j = 0; j < knows[list[i]].size(); j++) {
          int id = knows[list[i]][j];
          if (!hear[id]) {
            newList.push_back(id);
            hear[id] = true;
          }
        }
      }
      if (newList.size() > max) {
        max = newList.size();
        ans = day;
      }
      day++;
      list = newList;
    }
    if (max) {
      printf("%d %d\n", max, ans);
    } else {
      puts("0");
    }
  }
  return 0;
}

UVa 10919 - Prerequisites?

#include <stdio.h>

int main() {
  int k, m;
  while (scanf("%d", &k) && k) {
    scanf("%d", &m);
    int take[10000] = {};
    while (k--) {
      int id;
      scanf("%d", &id);
      take[id] = 1;
    }
    int fail = 0;
    while (m--) {
      int num, need, taken = 0;
      scanf("%d%d", &num, &need);
      while (num--) {
        int id;
        scanf("%d", &id);
        if (take[id]) {
          taken++;
        }
      }
      if (taken < need) fail = 1;
    }
    puts(fail ? "no" : "yes");
  }
  return 0;
}

C++ Default parameter value

#include <stdio.h>

int mul(int a, int b = 0) {
  return a * b;
}

int main() {
  printf("%d %d", mul(5), mul(5, 1));
  return 0;
}

2013年7月30日

UVa 11679 - Sub-prime

#include <stdio.h>

int main() {
  int B, N;
  while (scanf("%d%d", &B, &N) && B || N) {
    int i, res[99];
    for (i = 1; i <= B; i++) {
      scanf("%d", &res[i]);
    }
    while (N--) {
      int d, c, v;
      scanf("%d%d%d", &d, &c, &v);
      res[d] -= v;
      res[c] += v;
    }
    int ok = 1;
    for (i = 1; i <= B; i++) {
      if (res[i] < 0) {
        ok = 0;
      }
    }
    puts(ok ? "S" : "N");
  }
  return 0;
}

UVa 10114 - Loansome Car Buyer

#include <stdio.h>

int main() {
  int M, N;
  double first, cost;
  while (scanf("%d%lf%lf%d", &M, &first, &cost, &N) && M >= 0) {
    double deps[999] = {};
    while (N--) {
      int startM;
      scanf("%d", &startM);
      scanf("%lf", &deps[startM]);
    }
    double value = first + cost, owes = cost, earn = cost / M;
    int i;
    for (i = 0; i <= M; i++) {
      if (!deps[i]) {
        deps[i] = deps[i - 1];
      }
      value = value * (1 - deps[i]);
      if (value >= owes) {
        printf("%d %s%s\n", i, "month", i != 1 ? "s" : "");
        break;
      }
      owes -= earn;
    }
  }
  return 0;
}

UVa 1124 - Celebrity jeopardy

This is interesting.
#include <stdio.h>

int main() {
  char s[99];
  while (gets(s)) puts(s);
  return 0;
}

2013年7月28日

C++ Get array count

#include <cstdio>

template <class T, int N>
int len(T (&a)[N]) {
  return N ;
}

int main() {
  int a[7];
  printf("%d", len(a));
  return 0;
}

C Variadic function

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

int sum(char * s, ...) {
  va_list ap;
  int i, argNumbers = atoi(s), sum = 0;
  va_start(ap, s);
  for (i = 0; i < argNumbers; i++)
    sum += va_arg(ap, int);
  va_end(ap);
  return sum;
}

int main() {
  printf("%d\n", sum("3", 1, 2, 3));
  return 0;
}