UVa 11624 - Fire!

Accepted date: 2013-10-19
Ranking (as of 2013-10-19): 40 out of 732
Language: C++

/*
  UVa 11624 - Fire!

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

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

const int R_max = 1000, C_max = 1000;
char maze[R_max][C_max + 1];

int bfs(int R, int C, int jr, int jc)
{
  const int nr_dirs = 4;
  int dirs[nr_dirs][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  queue< pair<pair<int, int>, int> > q;
  q.push(make_pair(make_pair(jr, jc), 0));
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      if (maze[r][c] == 'F')
        q.push(make_pair(make_pair(r, c), -1));
  while (!q.empty()) {
    pair<pair<int, int>, int> s = q.front(); q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int r = s.first.first + dirs[i][0], c = s.first.second + dirs[i][1];
      if (r < 0 || r >= R || c < 0 || c >= C) {
        if (maze[s.first.first][s.first.second] == 'J')
          return s.second + 1;
      }
      else if (maze[s.first.first][s.first.second] == 'J') {
        if (maze[r][c] == '.') {
          maze[r][c] = 'J';
          q.push(make_pair(make_pair(r, c), s.second + 1));
        }
      }
      else { // maze[s.first.first][s.first.second] == 'F'
        if (maze[r][c] == '.' || maze[r][c] == 'J') {
          maze[r][c] = 'F';
          q.push(make_pair(make_pair(r, c), -1));
        }
      }
    }
  }
  return -1;
}

int main()
{
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    int R, C;
    scanf("%d %d", &R, &C);
    int jr = -1, jc = -1;
    for (int r = 0; r < R; r++) {
      scanf("%s", maze[r]);
      if (jr == -1) {
        for (int c = 0; c < C; c++)
          if (maze[r][c] == 'J') {
            jr = r; jc = c; break;
          }
      }
    }
    int minutes = bfs(R, C, jr, jc);
    if (minutes == -1)
      puts("IMPOSSIBLE");
    else
      printf("%d\n", minutes);
  }
  return 0;
}

UVa 11239 - Open Source

Accepted date: 2013-10-13
Ranking (as of 2013-10-13): 194 out of 724
Language: C++

/*
  UVa 11239 - Open Source

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
using namespace std;

struct project {
  string name_;
  int nr_students_;

  project() : nr_students_(0) {}
  project(const string& name) : name_(name), nr_students_(0) {}

  bool operator<(const project& p) const {
    if (nr_students_ > p.nr_students_)
      return true;
    else if (nr_students_ < p.nr_students_)
      return false;
    else
      return name_ < p.name_;
  }
};

int main()
{
  bool continued = false;
  string s;
  while (true) {
    vector<project> projects;
    map<string, int> students;
    int pi;
    while (true) {
      if (!continued)
        getline(cin, s);
      else
        continued = false;
      if (s[0] == '1')
        break;
      if (isupper(s[0])) {
        pi = static_cast<int>(projects.size());
        projects.push_back(project(s));
      }
      else {
        pair< map<string, int>::iterator, bool >
          result = students.insert(make_pair(s, pi));
        if (result.second)
          projects[pi].nr_students_++;
        else if (result.first->second != pi) {
          if (result.first->second != -1) {
            projects[result.first->second].nr_students_--;
            result.first->second = -1;
          }
        }
      }
    }
    sort(projects.begin(), projects.end());
    for (vector<project>::const_iterator i = projects.begin(),
      e = projects.end(); i != e; ++i)
      cout << i->name_ << ' ' << i->nr_students_ << endl;
    getline(cin, s);
    if (s[0] == '0')
      break;
    continued = true;
  }
  return 0;
}

UVa 10920 - Spiral Tap

Accepted date: 2013-10-13
Ranking (as of 2013-10-13): 265 out of 725
Language: C++

/*
  UVa 10920 - Spiral Tap

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

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

int main()
{
  while (true) {
    int sz;
    long long p;
    cin >> sz >> p;
    if (!sz && !p)
      break;
    long long x = (sz + 1) / 2, y = (sz + 1) / 2;
    long long q = sqrt(static_cast<double>(p));
      // max. odd number equal to or less than sqrt(p)
    if (!(q & 1))
      q--;
    x += (q - 1) / 2; y += (q - 1) / 2;
    p -= q * q;
    if (p) {
      q++;
      if (p <= q) {
        x -= p - 1; y++;
      }
      else if (p <= q * 2) {
        x -= q - 1; y -= p - q - 1;
      }
      else if (p <= q * 3) {
        x -= q * 3 - p - 1; y -= q - 1;
      }
      else {
        x++; y -= q * 4 - p - 1;
      }
    }
    cout << "Line = " << y << ", column = " << x << ".\n";
  }
  return 0;
}

UVa 162 - Beggar My Neighbour

Accepted date: 2013-10-06
Ranking (as of 2013-10-06): 108 out of 736
Language: C++

/*
  UVa 162 - Beggar My Neighbour

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

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

int face_card(char c)
{
  switch (c) {
  case 'J':
    return 1;
  case 'Q':
    return 2;
  case 'K':
    return 3;
  case 'A':
    return 4;
  default:
    return 0;
  }
}

int play(int nc, list<char>& player, list<char>& played)
{
  if (!nc)
    nc = 1;
  while (nc--) {
    if (player.empty())
      return -1;
    char c = player.front();
    player.pop_front();
    played.push_back(c);
    int fc = face_card(c);
    if (fc)
      return fc;
  }
  return 0;
}

int main()
{
  const int nr_cards = 52;
  while (true) {
    list<char> players[2], played;
      // players[0] is the non-dealer, players[1] is the dealer
      char card[2 + 1];
      scanf("%s", card);
    if (card[0] == '#')
      break;
    players[0].push_front(card[1]);
    for (int i = 1; i < nr_cards; i++) {
      scanf("%s", card);
      players[i % 2].push_front(card[1]);
    }
    bool done = false;
    int pi = 0, nc = 0;
    while (true) {
      int fc = play(nc, players[pi], played);
      pi = (pi + 1) % 2;
      if (fc == -1)
        break;
      if (!fc && nc)
        players[pi].splice(players[pi].end(), played);
      nc = fc;
    }
    printf("%d%3d\n", 2 - pi, static_cast<int>(players[pi].size()));
  }
  return 0;
}

UVa 535 - Globetrotter

Accepted date: 2013-10-04
Ranking (as of 2013-10-05): 60 out of 791
Language: C++

/*
  UVa 535 - Globetrotter

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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

const double pi = 2.0 * acos(0.0);

const double sphere_radius  = 6378.0;
const int nr_cities_max = 100, nr_chars_max = 31;

struct city {
  char name_[nr_chars_max + 1];
  double latitude_, longitude_;
} cities[nr_cities_max + 1];

int compare_city(const void* i, const void* j)
{
  const city *ci = reinterpret_cast<const city*>(const_cast<void*>(i)),
    *cj = reinterpret_cast<const city*>(const_cast<void*>(j));
  return strcmp(ci->name_, cj->name_);
}

double degree_to_radian(double degree)
{
  return (pi / 180.0) * degree;
}

double great_circle_distance(double radius,
  double latitude_s, double longitude_s,
  double latitude_f, double longitude_f)
{
/*
  latitude_s/_f and longitude_s/_f are in units of radian 
  (radian = (pi / 180) * degree)
*/
  double phi = latitude_f - latitude_s, lambda = longitude_f - longitude_s;
  double delta = pow(sin(phi / 2.0), 2) +
    cos(latitude_s) * cos(latitude_f) * pow(sin(lambda / 2.0), 2);
  delta = 2 * asin(sqrt(delta));
  return radius * delta;
}

int main()
{
  int n = 0;
  while (true) {
    scanf("%s %lf %lf",
      cities[n].name_, &cities[n].latitude_, &cities[n].longitude_);
    if (!strcmp(cities[n].name_, "#"))
      break;
    cities[n].latitude_ = degree_to_radian(cities[n].latitude_);
    cities[n].longitude_ = degree_to_radian(cities[n].longitude_);
    n++;
  }
  qsort(cities, n, sizeof(city), compare_city);
  while (true) {
    city ca, cb;
    scanf("%s %s", ca.name_, cb.name_);
    if (!strcmp(ca.name_, "#") && !strcmp(cb.name_, "#"))
      break;
    city *pca = reinterpret_cast<city*>(
      bsearch(&ca, cities, n, sizeof(city), compare_city)),
      *pcb = reinterpret_cast<city*>(
        bsearch(&cb, cities, n, sizeof(city), compare_city));
    printf("%s - %s\n", ca.name_, cb.name_);
    if (!pca || !pcb)
      puts("Unknown");
    else
      printf("%.0lf km\n",
        great_circle_distance(sphere_radius, pca->latitude_, pca->longitude_,
        pcb->latitude_, pcb->longitude_));
  }
  return 0;
}

UVa 314 - Robot

Accepted date: 2013-10-03
Ranking (as of 2013-10-03): 110 out of 748
Language: C++

/*
  UVa 314 - Robot

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

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

enum {north, south, east, west};

struct path {
  pair<int, int> pos_;
  int dir_;
  int seconds_;
};

const int m_max = 50, n_max = 50;
bool store[m_max][n_max], visited[m_max][n_max][west - north + 1];

int go_forward(int m, int n, int step, const path& p, queue<path>& q)
{
  path np;
  switch (p.dir_) {
  case north:
    if (p.pos_.first - step - 1 < 0 ||
      store[p.pos_.first - step - 1][p.pos_.second - 1] ||
      store[p.pos_.first - step - 1][p.pos_.second])
      return -1;
    np.pos_ = make_pair(p.pos_.first - step, p.pos_.second);
    break;
  case south:
    if (p.pos_.first + step >= m ||
      store[p.pos_.first + step][p.pos_.second - 1] ||
      store[p.pos_.first + step][p.pos_.second])
      return -1;
    np.pos_ = make_pair(p.pos_.first + step, p.pos_.second);
    break;
  case east:
    if (p.pos_.second + step >= n ||
      store[p.pos_.first][p.pos_.second + step] ||
      store[p.pos_.first - 1][p.pos_.second + step])
      return -1;
    np.pos_ = make_pair(p.pos_.first, p.pos_.second + step);
    break;
  default:
    if (p.pos_.second - step - 1 < 0 ||
      store[p.pos_.first][p.pos_.second  - step - 1] ||
      store[p.pos_.first - 1][p.pos_.second - step - 1])
      return -1;
    np.pos_ = make_pair(p.pos_.first, p.pos_.second - step);
    break;
  }
  np.dir_ = p.dir_;
  if (visited[np.pos_.first][np.pos_.second][np.dir_])
    return 0;
  np.seconds_ = p.seconds_ + 1;
  visited[np.pos_.first][np.pos_.second][np.dir_] = true;
  q.push(np);
  return 1;
}

bool turn(bool right, const path &p, queue<path>& q)
{
  path np;
  switch (p.dir_) {
  case north:
    np.dir_ = (right) ? east : west; break;
  case south:
    np.dir_ = (right) ? west : east; break;
  case east:
    np.dir_ = (right) ? south : north; break;
  default:
    np.dir_ = (right) ? north : south; break;
  }
  if (visited[p.pos_.first][p.pos_.second][np.dir_])
    return false;
  np.pos_ = p.pos_; np.seconds_ = p.seconds_ + 1;
  visited[np.pos_.first][np.pos_.second][np.dir_] = true;
  q.push(np);
  return true;
}

int bfs(int m, int n, const pair<int, int>&b, const pair<int, int>&e, int dir)
{
  path p;
  p.pos_ = b; p.dir_ = dir; p.seconds_ = 0;
  queue<path> q;
  visited[b.first][b.second][dir] = true;
  q.push(p);
  while (!q.empty()) {
    path p = q.front(); q.pop();
#ifdef DEBUG
    printf("%d %d %d, %d\n", p.pos_.first, p.pos_.second, p.dir_, p.seconds_);
#endif
    if (p.pos_ == e)
      return p.seconds_;
    turn(false, p, q); // turn left
    turn(true, p, q); // turn right
    for (int step = 1; step <= 3; step++)
      if (go_forward(m, n, step, p, q) == -1)
        break;
  }
  return -1;
}

int main()
{
  while (true) {
    int m, n;
    scanf("%d %d", &m, &n);
    if (!m && !n)
      break;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        visited[i][j][north] = visited[i][j][south] =
          visited[i][j][east] = visited[i][j][west] = false;
        int zeor_or_one;
        scanf("%d", &zeor_or_one);
        store[i][j] = zeor_or_one;
      }
    pair<int, int> b, e;
    char s[8];
    scanf("%d %d %d %d %s", &b.first, &b.second, &e.first, &e.second, s);
    int dir;
    switch (s[0]) {
    case 'n':
      dir = north; break;
    case 's':
      dir = south; break;
    case 'e':
      dir = east; break;
    default:
      dir = west; break;
    }
    printf("%d\n", bfs(m, n, b, e, dir));
  }
  return 0;
}

UVa 10393 - The One-Handed Typist

Accepted date: 2013-10-02
Ranking (as of 2013-10-02): 425 out of 742
Language: C++

/*
  UVa 10393 - The One-Handed Typist

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

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int nr_letters = 128;
const char* keyboard_chars[] = 
  {"", "qaz", "wsx", "edc", "rfvtgb", "", "", "yhnujm", "ik,", "ol.", "p;/"};

const int nr_chars_max = 63, n_max = 1000;

struct word {
  int length_;
  char s_[nr_chars_max + 1];
} words[n_max];

int compare_word(const void* i, const void* j)
{
  const word *wi = reinterpret_cast<const word*>(const_cast<void*>(i)),
    *wj = reinterpret_cast<const word*>(const_cast<void*>(j));
  if (wi->length_ > wj->length_)
    return -1;
  else if (wi->length_ < wj->length_)
    return 1;
  else
    return strcmp(wi->s_, wj->s_);
}

int main()
{
  bool letters[nr_letters]; // letters[i] is true if a letter i can be typed
  int i, j, f, n, m, mm, max_length;
  const char* p;
  while (scanf("%d %d", &f, &n) != EOF) {
    memset(letters, -1, sizeof(letters));
    while (f--) {
      scanf("%d", &i);
      for (p = keyboard_chars[i]; *p; p++)
        letters[*p] = false;
    }
    m = mm = max_length = 0;
    while (n--) {
      scanf("%s", words[m].s_);
      for (p = words[m].s_; *p; p++)
        if (!letters[*p])
          break;
      if (!*p && p - words[m].s_) {
        words[m].length_ = p - words[m].s_;
        if (words[m].length_ > max_length) {
          max_length = words[m].length_;
          mm = 1;
        }
        else if (words[m].length_ == max_length)
          mm++;
        m++;
      }
    }
    qsort(words, m, sizeof(word), compare_word);
#ifdef DEBUG
    for (i = 0; i < m; i++)
      printf("%s%c", words[i].s_, ((i == m - 1) ? '\n' : ' '));
#endif
    for (i = 0, j = mm - 1; i < j; i++) // remove duplicated words
      if (!strcmp(words[i].s_, words[i + 1].s_)) {
        words[i].s_[0] = '\0';
        mm--;
      }
    printf("%d\n", mm);
    for (i = 0, j = 0; j < mm; i++) 
      if (words[i].s_[0]) {
        printf("%s\n", words[i].s_);
        j++;
      }
  }
  return 0;
}