UVa 10610 - Gopher and Hawks

Accepted date: 2013-11-23
Ranking (as of 2013-11-23): 94 out of 637
Language: C++

/*
  UVa 10610 - Gopher and Hawks

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10610_Gopher_and_Hawks.cpp
*/

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;

const int n_max = 1024;
  // when I defined n_max = 1000, I got a verdict of Runtime error.

pair<double, double> holes[n_max];
vector<int> edges[n_max];
bool visited[n_max];

double euclidean_distance(const pair<double, double>& p,
  const pair<double, double>& q)
{
  double dx = p.first - q.first, dy = p.second - q.second;
  return sqrt(dx * dx + dy * dy);
}

int bfs(int n, int s, int t, const vector<int> edges[])
{
  queue< pair<int, int> > q;
  visited[s] = true;
  q.push(make_pair(s, 0));
  while (!q.empty()) {
    pair<int, int> u = q.front();
    q.pop();
    if (u.first == t)
      return u.second - 1;
    const vector<int>& e = edges[u.first];
    for (size_t i = 0, j = e.size(); i < j; i++) {
      int k = e[i];
      if (!visited[k]) {
        visited[k] = true;
        q.push(make_pair(k, u.second + 1));
      }
    }
  }
  return -1;
}

int main()
{
  string line;
  istringstream iss;
  while (true) {
    getline(cin, line);
    iss.str(line);
    int v, m;
    iss >> v >> m;
    iss.clear();
    if (!v && !m)
      break;
    double d = 60.0 * v * m;
    int n = 0;
    while (true) {
      getline(cin, line);
      if (line.empty())
        break;
      iss.str(line);
      iss >> holes[n].first >> holes[n].second;
      iss.clear();
      n++;
    }
    for (int i = 0; i < n; i++) {
      edges[i].clear();
      visited[i] = false;
    }
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
        if (euclidean_distance(holes[i], holes[j]) <= d) {
          edges[i].push_back(j);
          edges[j].push_back(i);
        }
    int nr_holes = bfs(n, 0, 1, edges);
    if (nr_holes != -1)
      cout << "Yes, visiting " << nr_holes << " other holes.\n";
    else
      cout << "No.\n";
  }
  return 0;
}

UVa 837 - Light and Transparencies

Accepted date: 2013-11-23
Ranking (as of 2013-11-23): 528 out of 672
Language: C++

/*
  UVa 837 - Light and Transparencies

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_837_Light_and_Transparencies.cpp
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

struct point {
  double x_;
  int tci_; // index to tcs[]
};

struct tc { // transparent coeficients
  bool effective_;
  double r_;
};

bool compare_point(const point& p, const point& q)
{
  return p.x_ < q.x_;
}

int main()
{
  int t;
  cin >> t;
  while (t--) {
    int nl;
    cin >> nl;
    int np = nl * 2;
    vector<point> points(np);
    vector<tc> tcs(nl);
    for (int i = 0; i < nl; i++) {
      double y1, y2;
      cin >> points[i * 2].x_ >> y1 >> points[i * 2 + 1].x_ >> y2 >> tcs[i].r_;
      points[i * 2].tci_ = points[i * 2 + 1].tci_ = i;
      tcs[i].effective_ = false;
    }
    sort(points.begin(), points.end(), compare_point);
    cout << np + 1 << endl;
    cout << fixed;
    for (int i = 0; i <= np; i++) {
      if (i)
        cout << setprecision(3) << points[i - 1].x_;
      else
          cout << "-inf";
      if (i < np)
          cout << ' ' << setprecision(3) << points[i].x_;
      else
        cout << " +inf";
      double pl = 1.0; // percentage of light
      if (i && i < np) {
        for (int j = 0; j < nl; j++)
          if (tcs[j].effective_)
            pl *= tcs[j].r_;
      }
      cout << ' ' << setprecision(3) << pl << endl;
      if (i < np)
        tcs[points[i].tci_].effective_ = !tcs[points[i].tci_].effective_;
    }
    if (t)
      cout << endl;
  }
  return 0;
}

UVa 776 - Monkeys in a Regular Forest

Accepted date: 2013-11-18
Ranking (as of 2013-11-18): 147 out of 641
Language: C++

/*
  UVa 776 - Monkeys in a Regular Forest

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_776_Monkeys_in_a_Regular_Forest.cpp
*/

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

void bfs(int nr_rows, int nr_columns, int r, int c, int fn,
  const vector< vector<char> >& forest, vector< vector<int> >& monkeys)
{
  const int nr_dirs = 8;
  const int dirs[nr_dirs][2] =
    {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
  char fc = forest[r][c];
  queue<pair<int, int> > q;
  monkeys[r][c] = fn;
  q.push(make_pair(r, c));
  while (!q.empty()) {
    pair<int, int> rc = q.front();
    q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      r = rc.first + dirs[i][0]; c = rc.second + dirs[i][1];
      if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns &&
        forest[r][c] == fc && !monkeys[r][c]) {
        monkeys[r][c] = fn;
        q.push(make_pair(r, c));
      }
    }
  }
}

int main()
{
  string line;
  while (getline(cin, line)) {
    vector< vector<char> > forest;
    do {
      if (line[0] == '%')
        break;
      forest.push_back(vector<char>());
      istringstream iss(line);
      char c;
      while (iss >> c)
        forest.back().push_back(c);
    } while (getline(cin, line));
    int nr_rows = static_cast<int>(forest.size()),
      nr_columns = static_cast<int>(forest[0].size());
    vector< vector<int> > monkeys(nr_rows, vector<int>(nr_columns, 0));
    for (int r = 0, fn = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        if (!monkeys[r][c])
          bfs(nr_rows, nr_columns, r, c, ++fn, forest, monkeys);
    vector<int> widths(nr_columns, 0);
    for (int c = 0; c < nr_columns; c++) {
      for (int r = 0; r < nr_rows; r++) {
        int fn = monkeys[r][c], w = ((c) ? 1 : 0);
        do {
          fn /= 10;
          w++;
        } while (fn);
        widths[c] = max(widths[c], w);
      }
    }
    cout << setfill(' ');
    for (int r = 0;r < nr_rows; r++) {
      for (int c = 0; c < nr_columns; c++)
        cout << setw(widths[c]) << monkeys[r][c];
      cout << endl;
    }
    cout << "%\n";
  }
  return 0;
}

UVa 296 - Safebreaker

Accepted date: 2013-11-15
Ranking (as of 2013-11-15): 30 out of 639
Language: C++

/*
  UVa 296 - Safebreaker

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_296_Safebreaker.cpp
*/

#include <iostream>
#include <cstring>
using namespace std;

const int nr_digits = 4, nr_guesses_max = 10, number_max = 10000;

struct guess {
  char code_[nr_digits + 1];
  int nr_correct_, nr_misplaced_;
};

void get_code(int n, char* code)
{
  for (int i = nr_digits - 1; i >= 0; i--) {
    code[i] = n % 10 + '0';
    n /= 10;
  }
}

bool is_consistent(const char* code, const guess* g)
{
  int nr_correct = 0;
  unsigned char correct = 0;
    // bit i (0 <= i <= 4) is 1 if i-th character is correct
  for (int i = 0, bi = 1; i < nr_digits; i++, bi <<= 1)
    if (code[i] == g->code_[i]) {
      correct |= bi;
      nr_correct++;
    }
  if (nr_correct != g->nr_correct_)
    return false;
  int nr_misplaced = 0;
  unsigned char misplaced = 0;
    // bit i (0 <= i <= 4) is 1 if i-th character is misplaced
  for (int i = 0, bi = 1; i < nr_digits; i++, bi <<= 1)
    if (!(correct & bi)) {
      int j = i + 1;
      if (j == nr_digits)
        j = 0;
      while (j != i) {
        int bj = 1 << j;
        if (!(correct & bj) && !(misplaced & bj) && code[i] == g->code_[j]) {
          misplaced |= bj;
          nr_misplaced++;
          break;
        }
        if (++j == nr_digits)
          j = 0;
      }
    }
  return nr_misplaced == g->nr_misplaced_;
}

int main()
{
  int n;
  cin >> n;
  while (n--) {
    int g;
    cin >> g;
    guess guesses[nr_guesses_max];
    for (int i = 0; i < g; i++) {
      char separator;
      cin >> guesses[i].code_ >> guesses[i].nr_correct_
        >> separator >> guesses[i].nr_misplaced_;
    }
    int nr_consistent = 0;
    char code[nr_digits + 1], secret_code[nr_digits + 1];
    code[nr_digits] = '\0';
    for (int i = 0; i < number_max; i++) {
      get_code(i, code);
      int j;
      for (j = 0; j < g; j++)
        if (!is_consistent(code, &guesses[j]))
          break;
      if (j == g) {
        if (!nr_consistent++)
          strcpy(secret_code, code);
      }
    }
    if (nr_consistent == 1)
      cout << secret_code << endl;
    else if (nr_consistent)
      cout << "indeterminate\n";
    else
      cout << "impossible\n";
  }
  return 0;
}

UVa 10901 - Ferry Loading III

Accepted date: 2013-11-13
Ranking (as of 2013-11-14): 201 out of 669
Language: C++

/*
  UVa 10901 - Ferry Loading III

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10901_Ferry_Loading_III.cpp
*/

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

const int m_max = 10000;

struct car {
  int at_; // arrival time
  int ut_; // unloaded time
  int ab_; // arrival bank
} cars[m_max];

int cars_at_left_bank[m_max], cars_at_right_bank[m_max];
  // cars_at_left/right_bank[i] is the index to cars[] that arrives at 
  // left/right bank

enum {left, right};

int main()
{
  int c;
  scanf("%d", &c);
  while (c--) {
    int n, t, m;
    scanf("%d %d %d", &n, &t, &m);
    int mlb = 0, mrb = 0; // number of cars that arrives at left/right bank
    for (int i = 0; i < m; i++) {
      char s[8];
      scanf("%d %s", &cars[i].at_, s);
      if (s[0] == 'l') {
        cars[i].ab_ = left;
        cars_at_left_bank[mlb++] = i;
      }
      else {
        cars[i].ab_ = right;
        cars_at_right_bank[mrb++] = i;
      }
    }
    int ft = 0, fb = left;
    for (int ilb = 0, irb = 0; ilb < mlb || irb < mrb; ) {
      int i, b;
      if (ilb < mlb && irb < mrb) {
        int il = cars_at_left_bank[ilb], ir = cars_at_right_bank[irb];
        if (fb == left && cars[il].at_ <= ft)
          i = il;
        else if (fb == right && cars[ir].at_ <= ft)
          i = ir;
        else if (cars[il].at_ < cars[ir].at_)
          i = il;
        else if (cars[il].at_ > cars[ir].at_)
          i = ir;
        else
          i = (fb == left) ? il : ir;
      }
      else if (ilb < mlb)
        i = cars_at_left_bank[ilb];
      else
        i = cars_at_right_bank[irb];
      b = cars[i].ab_;
      if (cars[i].at_ > ft)
        ft += cars[i].at_ - ft;
      if (fb != cars[i].ab_) {
        ft += t;
        fb = cars[i].ab_;
      }
      if (b == left)
        for (int j = 0; ilb < mlb && cars[cars_at_left_bank[ilb]].at_ <= ft
          && j < n; ilb++, j++)
          cars[cars_at_left_bank[ilb]].ut_ = ft + t;
      else
        for (int j = 0; irb < mrb && cars[cars_at_right_bank[irb]].at_ <= ft
          && j < n; irb++, j++)
          cars[cars_at_right_bank[irb]].ut_ = ft + t;
      ft += t;
      fb = (fb == left) ? right : left;
    }
    for (int i = 0; i < m; i++)
      printf("%d\n", cars[i].ut_);
    if (c)
      putchar('\n');
  }
  return 0;
}

UVa 11344 - The Huge One

Accepted date: 2013-11-12
Ranking (as of 2013-11-14): 316 out of 678
Language: C++

/*
  UVa 11344 - The Huge One

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11344_The_Huge_One.cpp
*/

#include <cstdio>
#include <cstring>

bool is_multiple_of_1(const char* number, int length)
{
  return true;
}

bool is_multiple_of_2(const char* number, int length)
{
  return ((number[length - 1] - '0') % 2) ? false : true;
}

bool is_multiple_of_3(const char* number, int length)
{
  int s = 0;
  for (int i = 0; i < length; i++)
    s += number[i] - '0';
  return (s % 3) ? false : true;
}

bool is_multiple_of_4(const char* number, int length)
{
  int s = number[length - 1] - '0';
  if (length > 1)
    s += (number[length - 2] - '0') * 10;
  return (s % 4) ? false : true;
}

bool is_multiple_of_5(const char* number, int length)
{
  return ((number[length - 1] - '0') % 5) ? false : true;
}

bool is_multiple_of_6(const char* number, int length)
{
  return is_multiple_of_2(number, length) && is_multiple_of_3(number,length);
}

bool is_multiple_of_7(const char* number, int length)
{
  int s = 0;
  for (int i = 0, j = length - 1; j >= 0; i++) {
    int k = number[j--] - '0';
    if (j >= 0)
      k += (number[j--] - '0') * 10;
    if (j >= 0)
      k += (number[j--] - '0') * 100;
    if (i & 1)
      s -= k;
    else
      s += k;
  }
  return (s % 7) ? false : true;
}

bool is_multiple_of_8(const char* number, int length)
{
  int s = number[length - 1] - '0';
  if (length > 1) {
    s += (number[length - 2] - '0') * 10;
    if (length > 2)
      s += (number[length - 3] - '0') * 100;
  }
  return (s % 8) ? false : true;
}

bool is_multiple_of_9(const char* number, int length)
{
  int s = 0;
  for (int i = 0; i < length; i++)
    s += number[i] - '0';
  return (s % 9) ? false : true;
}

bool is_multiple_of_10(const char* number, int length)
{
  return number[length - 1] == '0';
}

bool is_multiple_of_11(const char* number, int length)
{
  int s = 0;
  for (int i = 0, j = length - 1; j >= 0; i++, j--) {
    int k = number[j] - '0';
    if (i & 1)
      s -= k;
    else
      s += k;
  }
  return (s % 11) ? false : true;
}

bool is_multiple_of_12(const char* number, int length)
{
  return is_multiple_of_3(number, length) && is_multiple_of_4(number, length);
}

int main()
{
  typedef bool (*IS_MULTIPLE_OF_N_FUNCTION)(const char* number, int length);
  const IS_MULTIPLE_OF_N_FUNCTION is_multiple_of_n_functions[] = {
    NULL,
    is_multiple_of_1, is_multiple_of_2, is_multiple_of_3,
    is_multiple_of_4, is_multiple_of_5, is_multiple_of_6,
    is_multiple_of_7, is_multiple_of_8, is_multiple_of_9,
    is_multiple_of_10, is_multiple_of_11, is_multiple_of_12
  };

  int N;
  scanf("%d", &N);
  while (N--) {
    const int M_digits_max = 1001;
    char M[M_digits_max + 1];
    scanf("%s", M);
    int length = strlen(M), S;
    scanf("%d", &S);
    bool wonderful = true;
    while (S--) {
      int number;
      scanf("%d", &number);
      if (wonderful && !is_multiple_of_n_functions[number](M, length))
        wonderful = false;
    }
    printf("%s - %s.\n", M, ((wonderful) ? "Wonderful" : "Simple"));
  }
  return 0;
}