2013年1月30日

UVa 10245 - The Closest Pair Problem


#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

struct P {
  double x, y;
};

bool cmp(P a, P b) {
  return a.x < b.x;
};

double sqr(double n) {
  return n * n;
}

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

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    P p[10000];
    for (int i = 0; i < n; i++)
      scanf("%lf%lf", &p[i].x, &p[i].y);
    if (n == 1) {
      puts("INFINITY");
      continue;
    }
    std::sort(p, p + n, cmp);
    double min = dis(p[0], p[1]);
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n && sqr(p[j].x - p[i].x) < min; j++)
        if (dis(p[j], p[i]) < min) min = dis(p[j], p[i]);
    min = sqrt(min);
    if (min > 10000.0 || fabs(min - 10000.0) < 0.00001) puts("INFINITY");
    else printf("%.4lf\n", min);
  }
  return 0;
}

2013年1月24日

UVa 200 - Rare Order


#include <stdio.h>

int main() {
  char s[30], prev[30] = {};
  int i, j, con[26] = {}, find[26] = {}, adj[26][26] = {};
  while (gets(s) && s[0] != '#') {
    for (i = 0; s[i]; i++) find[s[i] - 'A'] = 1;
    for (i = 0; s[i] && prev[i] && s[i] == prev[i]; i++);
    if (prev[i] && s[i]) adj[prev[i] - 'A'][s[i] - 'A'] = 1;
    sscanf(s, "%s", prev);
  }
  for (i = 0; i < 26; i++)
    for (j = 0; j < 26; j++)
      if (adj[i][j]) con[j]++;
  while (1) {
    for (i = 0; i < 26 && (!find[i] || con[i]); i++);
    if (i == 26) break;
    con[i] = -1;
    putchar(i + 'A');
    for (j = 0; j < 26; j++)
      if (adj[i][j]) con[j]--;
  }
  puts("");
  return 0;
}

2013年1月22日

UVa 216 - Getting in Line


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

int n, x[10], y[10], parent[10], end;
double d[10][10], min;

void dfs(int now, int depth, int* chk, int* prev, double dis) {
  int i;
  if (depth == n) {
    if (dis < min) {
      for (i = 1; i <= n; i++)
        parent[i] = prev[i];
      end = now;
      min = dis;
    }
    return;
  }
  for (i = 1; i <= n; i++)
    if (!chk[i]) {
      prev[i] = now;
      chk[i] = 1;
      dfs(i, depth + 1, chk, prev, dis + d[now][i]);
      prev[i] = i;
      chk[i] = 0;
    }
}

void path(int p) {
  if (parent[p] != p) path(parent[p]);
  else return;
  printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", x[parent[p]], y[parent[p]], x[p], y[p], d[p][parent[p]]);
}

int main() {
  int T = 1;
  while (scanf("%d", &n) && n) {
    int i, j;
    for (i = 1; i <= n; i++)
      scanf("%d%d", &x[i], &y[i]);
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        d[i][j] = 16 + sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
    int check[10] = {}, prev[10];
    for (i = 1; i <= n; i++)
      prev[i] = parent[i] = i;
    min = 2e9;
    for (i = 1; i <= n; i++) {
      check[i] = 1;
      dfs(i, 1, check, prev, 0);
      check[i] = 0;
    }
    puts("**********************************************************");
    printf("Network #%d\n", T++);
    path(end);
    printf("Number of feet of cable required is %.2lf.\n", min);
  }
  return 0;
}

2013年1月10日

UVa 116 - Unidirectional TSP


#include <stdio.h>

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

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

int main() {
  int R, C, r, c;
  while (scanf("%d%d", &R, &C) == 2) {
    int num[101][101] = {}, dp[101][101] = {}, next[101][101] = {};
    for (r = 0; r < R; r++)
      for (c = 0; c < C; c++)
        scanf("%d", &num[r][c]);
    for (c = C - 1; c >= 0; c--)
      for (r = 0; r < R; r++) {
        int r1 = (r - 1 + R) % R, r2 = r, r3 = (r + 1) % R;
        int up = small(r1, small(r2, r3)), down = big(r1, big(r2, r3)), mid = r1 + r2 + r3 - up - down;
        int min = dp[up][c + 1];
        next[r][c] = up;
        if (dp[mid][c + 1] < min) min = dp[mid][c + 1], next[r][c] = mid;
        if (dp[down][c + 1] < min) min = dp[down][c + 1], next[r][c] = down;
        dp[r][c] = num[r][c] + min;
      }
    int dis = 2e9, ans, c = 0;
    for (r = 0; r < R; r++)
      if (dp[r][0] < dis) dis = dp[r][0], ans = r;
    while (c < C) {
      printf("%d%s", ans + 1, c == C - 1 ? "\n" : " ");
      ans = next[ans][c++];
    }
    printf("%d\n", dis);
  }
  return 0;
}

2013年1月8日

UVa 11076 - Add Again


#include <stdio.h>

int main() {
  int i, j, n, fac[13] = {1};
  for (i = 1; i < 13; i++)
    fac[i] = fac[i - 1] * i;
  while (scanf("%d", &n) && n) {
    int check[10] = {}, sum = 0, kind = 0;
    for (i = 0; i < n; i++) {
      scanf("%d", &j);
      sum += j;
      if (!check[j]) kind++;
      check[j]++;
    }
    if (kind == 1) {
      if (sum / n) {
        for (i = 0; i < n; i++)
          printf("%d", sum / n);
        puts("");
      } else {
        puts("0");
      }
      continue;
    }
    int times = fac[n] / n;
    unsigned long long rec = 1;
    for (i = 0; i < 10; i++)
      if (!(sum % fac[check[i]])) sum /= fac[check[i]];
      else if (!(times % fac[check[i]])) times /= fac[check[i]];
      else rec *= fac[check[i]];
    unsigned long long temp, carry = 0, ans = 0, ten = 1;
    for (i = 0; i < n; i++) {
      temp = carry + times * sum / rec;
      carry = temp / 10;
      ans += ten * (temp % 10);
      ten *= 10;
    }
    if (carry) ans += ten * carry;
    printf("%llu\n", ans);
  }
  return 0;
}

2013年1月6日

UVa 10026 - Shoemaker's Problem


#include <cstdio>
#include <algorithm>

struct J {
  int t, c, n;
};

bool cmp(J a, J b) {
  return a.c * b.t > b.c * a.t;
}

int main() {
  int T;
  scanf("%d", &T);
  J job[1000];
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d%d", &job[i].t, &job[i].c), job[i].n = i + 1;
    std::sort(job, job + n, cmp);
    for (int i = 0; i < n; i++)
      printf("%d%s", job[i].n, i == n - 1 ? "\n" : " ");
    if (T) puts("");
  }
  return 0;
}

UVa 11503 - Virtual Friends


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

map<string, string> p;
map<string, int> num;

string find(string x) {
  return x == p[x] ? x : (p[x] = find(p[x]));
}

void add(string a, string b) {
  string x = find(a), y = find(b);
  if (x == y) {
    printf("%d\n", num[y]);
    return;
  }
  num[y] += num[x];
  num[x] = 0;
  p[x] = y;
  printf("%d\n", num[y]);
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    p.clear();
    num.clear();
    int n;
    scanf("%d", &n);
    while (n--) {
      char a[30], b[30];
      scanf("%s%s", a, b);
      string s1 = string(a), s2 = string(b);
      if (!p.count(s1)) p[s1] = s1, num[s1] = 1;
      if (!p.count(s2)) p[s2] = s2, num[s2] = 1;
      add(s1, s2);
    }
  }
  return 0;
}

UVa 10226 - Hardwood Species


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

int main() {
  int N;
  scanf("%d", &N);
  getchar();
  getchar();
  while (N--) {
    char s[100];
    int sum = 0;
    map<string, int> num;
    set<string> dic;
    while (gets(s) && s[0]) {
      sum++;
      string tree(s);
      num[tree]++;
      dic.insert(tree);
    }
    for (set<string>::iterator it = dic.begin(); it != dic.end(); it++)
      printf("%s %.4lf\n", (*it).c_str(), 100 * num[*it] / (double)sum);
    if (N) puts("");
  }
  return 0;
}

2013年1月5日

UVa 475 - Wild Thing


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

int main() {
  char in[1000];
  string s, target;
  bool find = 0, first = 1;
  while (gets(in)) {
    target = string(in);
    bool star = 0;
    int len = target.length(), N = 0;
    for (int i = 0; i < len; i++)
      if (target[i] == '*') star = 1;
    string temp, compare[1000];
    for (int i = 0; ; i++)
      if (target[i] && target[i] != '*') {
        temp.insert(temp.end(), target[i]);
      } else {
        if (temp != "") compare[N++] = temp;
        temp = "";
        if (i == len) break;
      }
    find = 0;
    while (gets(in) && in[0]) {
      s = string(in);
      bool flag = 1, head = (target[0] != '*'), tail = 0;
      if (!star && s != target) flag = 0;
      else {
        int loc = 0;
        for (int i = 0; i < N && flag; i++) {
          int pos = s.find(compare[i], loc);
          if (i == N - 1 && target[len - 1] != '*') tail = 1;
          if (pos == string::npos || (!i && head && pos) || (tail && pos + compare[i].length() != s.length())) {
            flag = 0;
            if (tail)
              while (pos != string::npos && !flag) {
                if (pos + compare[i].length() == s.length()) flag = 1;
                pos = s.find(compare[i], pos + 1);
              }
          }
          loc = pos + 1;
        }
      }
      if (flag) {
        if (!find && !first) puts("");
        if (!find) printf("MATCHES FOR THE PATTERN: %s\n", target.c_str());
        find = 1;
        printf("%s\n", s.c_str());
        first = 0;
      }
    }
  }
  return 0;
}

UVa 123 - Searching Quickly


#include <iostream>
#include <sstream>
#include <string>
#include <set>
using namespace std;

int main() {
  string s;
  set<string> ign, prt;
  while (cin >> s && s != "::")
    ign.insert(s);
  string input[300];
  int n = 0;
  while (getline(cin, s)) {
    for (int i = 0; s[i]; i++)
      if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
    input[n++] = s;
    istringstream ss(s);
    while (ss >> s)
      if (!ign.count(s)) prt.insert(s);
  }
  for (set<string>::iterator it = prt.begin(); it != prt.end(); it++)
    for (int i = 0; i < n; i++) {
      int pos = 0, len = (*it).length();
      while (input[i].find(*it, pos) != string::npos) {
        pos = input[i].find(*it, pos);
        if ((!pos || input[i][pos - 1] == ' ') && (!input[i][pos + len] || input[i][pos + len] == ' ')) {
          string p = input[i], rep = *it;
          for (int j = 0; rep[j]; j++)
            rep[j] = rep[j] - 'a' + 'A';
          p.replace(p.find(*it, pos), len, rep);
          cout << p << "\n";
        }
        pos++;
      }
    }
  return 0;
}

2013年1月4日

UVa 466 - Mirror, Mirror


#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

void rotate(vector<string>& v) {
  int r, c, n = v.size();
  vector<string> temp = v;
  for (r = 0; r < n; r++)
    for (c = 0; c < n; c++)
      temp[c][n - r - 1] = v[r][c];
  v = temp;
}

void reflect(vector<string>& v) {
  int r, c, n = v.size();
  vector<string> temp = v;
  for (r = 0; r < n; r++)
    for (c = 0; c < n; c++)
      temp[r][c] = v[n - r - 1][c];
  v = temp;
}

int main() {
  int n, C = 1;
  while (cin >> n) {
    vector<string> source, end;
    while (n--) {
      string a, b;
      cin >> a >> b;
      source.push_back(a);
      end.push_back(b);
    }
    printf("Pattern %d was ", C++);
    queue<vector<string> > q;
    map<vector<string>, int> path;
    path[source] = 0;
    q.push(source);
    bool found = 0;
    while (!q.empty()) {
      vector<string> now = q.front();
      q.pop();
      int len = path[now];
      if (now == end) {
        if (!len) puts("preserved.");
        else if (len < 4) printf("rotated %d degrees.\n", len * 90);
        else if (len == 10) puts("reflected vertically.");
        else printf("reflected vertically and rotated %d degrees.\n", ((4 - len % 10) % 4) * 90);
        found = 1;
        break;
      }
      for (int r = 1; r <= 4; r++) {
        rotate(now);
        if (!path.count(now)) {
          q.push(now);
          path[now] = len + r;
        }
        reflect(now);
        if (!path.count(now)) {
          q.push(now);
          path[now] = len + (r % 4) + 10;
        }
        reflect(now);
      }
    }
    if (!found) puts("improperly transformed.");
  }
  return 0;
}

2013年1月3日

UVa 115 - Climbing Trees


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

map<string, set<string> > parent, child;
set<string> check;
bool found;

void find(string a, string b, string path) {
  if (found) return;
  if (a == b) {
    int plus = 0, minus = 0;
    for (int i = 0; path[i]; i++)
      if (path[i] == '+') plus++;
      else minus++;
    if (plus && !minus) {
      while (plus-- > 2) printf("great ");
      while (plus--) printf("grand ");
      puts("child");
    } else if (minus && !plus) {
      while (minus-- > 2) printf("great ");
      while (minus--) printf("grand ");
      puts("parent");
    } else if (plus == 1 && minus == plus) {
      puts("sibling");
    } else {
      plus--;
      minus--;
      int min = plus < minus ? plus : minus;
      if (plus != minus) printf("%d cousin removed %d\n", min, plus > minus ? plus - minus : minus - plus);
      else printf("%d cousin\n", min);
    }
    found = 1;
    return;
  }
  check.insert(a);
  set<string>::iterator it;
  for (it = parent[a].begin(); it != parent[a].end(); it++)
    if (!check.count(*it)) {
      string next = path;
      next.insert(next.end(), '-');
      find(*it, b, next);
    }
  for (it = child[a].begin(); it != child[a].end(); it++)
    if (!check.count(*it)) {
      string next = path;
      next.insert(next.end(), '+');
      find(*it, b, next);
    }
}

int main() {
  string a, b;
  while (cin >> a >> b) {
    if (!a.compare("no.child")) break;
    child[a].insert(b);
    parent[b].insert(a);
  }
  while (cin >> a >> b) {
    check.erase(check.begin(), check.end());
    found = 0;
    if (a.compare(b)) find(a, b, "");
    if (!found) puts("no relation");
  }
  return 0;
}

2013年1月1日

UVa 10375 - Choose and divide

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    BigDecimal fac[] = new BigDecimal[10001];
    fac[0] = BigDecimal.valueOf(1);
    for (int i = 1; i <= 10000; i++)
      fac[i] = fac[i - 1].multiply(BigDecimal.valueOf(i));
    while (cin.hasNext()) {
      int p = cin.nextInt(), q = cin.nextInt(), r = cin.nextInt(), s = cin.nextInt();
      BigDecimal ans = BigDecimal.ONE;
      ans = ans.multiply(fac[p]);
      ans = ans.divide(fac[q], 1000, BigDecimal.ROUND_HALF_UP);
      ans = ans.multiply(fac[s]);
      ans = ans.divide(fac[p - q], 1000, BigDecimal.ROUND_HALF_UP);
      ans = ans.multiply(fac[r - s]);
      ans = ans.divide(fac[r], 1000, BigDecimal.ROUND_HALF_UP);
      System.out.println(ans.setScale(5, BigDecimal.ROUND_HALF_UP));
    }
  }
}