2013年8月3日

UVa 388 - Galactic Import

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

class Planet {
 public:
  Planet() {}
  Planet(char name, double value, string con) : name(name), value(value), con(con) {
    earth = false;
    for (int i = 0; con[i]; i++) {
      if (con[i] == '*') {
        con.erase(con.begin() + i);
        earth = true;
        break;
      }
    }
  }
  char name;
  double value;
  string con;
  bool earth;
} planets[26];

int index[999];
double max;
char answer;

void solve(char start, int now, double value, bool * done) {
  if (planets[now].earth) {
    if (fabs(value - max) < 1e-6) {
      max = value;
      answer = start < answer ? start : answer;
    } else if (value > max) {
      max = value;
      answer = start;
    }
    return;
  }
  done[now] = true;
  for (int i = 0; planets[now].con[i]; i++) {
    int next = index[planets[now].con[i]];
    if (!done[next]) {
      done[next] = true;
      solve(start, next, value * 0.95, done);
      done[next] = false;
    }
  }
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < n; i++) {
      char n[20], c[20];
      double v;
      scanf("%s%lf%s", n, &v, c);
      index[n[0]] = i;
      planets[i] = Planet(n[0], v, c);
    }
    max = 0;
    for (int i = 0; i < n; i++) {
      bool done[26] = {};
      solve(planets[i].name, i, planets[i].value, done);
    }
    printf("Import from %c\n", answer);
  }
  return 0;
}

沒有留言:

張貼留言