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;
}

UVa 11056 - Formula 1

Accepted date: 2013-09-29
Ranking (as of 2013-09-29): 110 out of 746
Language: C++

/*
  UVa 11056 - Formula 1

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

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

#ifdef ONLINE_JUDGE
#define _stricmp strcasecmp
#endif

const int nr_name_chars_max = 31, nr_pilots_max = 100;

struct pilot {
  char name_[nr_name_chars_max + 1];
  int lap_;

  bool operator<(const pilot& p) const;
} pilots[nr_pilots_max];

bool pilot::operator<(const pilot& p) const
{
  if (lap_ < p.lap_)
    return true;
  else if (lap_ > p.lap_)
    return false;
  else
    return _stricmp(name_, p.name_) < 0;
}

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; i++) {
      int m, s, ms;
      scanf("%s %*s %d %*s %d %*s %d %*s", pilots[i].name_, &m, &s, &ms);
      pilots[i].lap_ = m * 60000 + s * 1000 + ms;
#ifdef DEBUG
      printf("%s %d\n", pilots[i].name_, pilots[i].lap_);
#endif
    }
    sort(pilots, pilots + n);
    for (int i = 0, r = 1; i < n; r++) {
      printf("Row %d\n", r);
      puts(pilots[i++].name_);
      if (i < n)
        puts(pilots[i++].name_);
    }
    putchar('\n');
  }
  return 0;
}

UVa 245 - Uncompress

Accepted date: 2013-09-23
Ranking (as of 2013-09-23): 19 out of 775
Language: C++

/*
  UVa 245 - Uncompress

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

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

int main()
{
  int n = 0; // number of words
  vector<char*> words; // word list
  while (true) {
    string s;
    getline(cin, s);
    if (s[0] == '0')
      break;
    for (const char *p = s.c_str(), *q = s.c_str(); ; ) {
      if (isdigit(*p)) {
        int i = *p - '0';
        for (p++; isdigit(*p); p++) {
          i *= 10;
          i += *p - '0';
        }
        q = p;
        i--;
        char* r = words[n - 1 - i];
        cout << r;
        // move the word to the back of the list
        memmove(&words[n - 1 - i], &words[n - i], sizeof(char*) * i);
        words[n - 1] = r;
      }
      else {
        if (*p)
          cout << *p;
        if (isalpha(*p))
          p++;
        else {
          if (p - q) {
            // add a word at the back of the list
            char* t = new char[p - q + 1];
            memcpy(t, q, p - q);
            *(t + (p - q)) = '\0';
            words.push_back(strdup(t));
            n++;
            q = p;
          }
          if (*p) {
            p++; q++;
          }
          else // end of line
            break;
        }
      }
    }
    cout << endl;
  }
  return 0;
}

UVa 168 - Theseus and the Minotaur

Accepted date: 2013-09-21
Ranking (as of 2013-09-22): 22 out of 789
Language: C++

/*
  UVa 168 - Theseus and the Minotaur

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

#include <cstdio>

const int nr_letters = 26;

struct cavern {
  int reachables_[nr_letters + 1];
  bool candle_;
} caverns[nr_letters];

int main()
{
  const int nr_chars_max = 255;
  char s[nr_chars_max + 1];
  while (true) {
    scanf("%s", s);
    if (s[0] == '#')
      break;
    cavern caverns[nr_letters];
    for (int i = 0; i < nr_letters; i++) {
      caverns[i].reachables_[0] = -1;
      caverns[i].candle_ = false;
    }
    for (const char* p = s; *p; p++) {
      int i = *p++ - 'A', j = 0;
      for (p++; *p >= 'A' && *p <= 'Z'; p++)
        caverns[i].reachables_[j++] = *p - 'A';
      caverns[i].reachables_[j] = -1; // terminator
    }
    char mc[1 + 1], tc[1 + 1];
    int mi, pmi, k, ki = 1;
    scanf("%s %s %d", mc, tc, &k);
    mi = mc[0] - 'A', pmi = tc[0] - 'A';
    int np = 0, passed[nr_letters];
    while (true) {
#ifdef DEBUG
      printf("%d %d\n", pmi, mi);
#endif
      if (pmi == mi) {
        if (!caverns[mi].candle_)
          passed[np++] = mi;
        break;
      }
      if (ki == k) {
        ki = 0;
#ifdef DEBUG
        printf("%d\n", mi);
#endif
        caverns[mi].candle_ = true;
        passed[np++] = mi;
      }
      const int* pc;
      for (pc = caverns[mi].reachables_; *pc != -1; pc++)
        if (*pc != pmi && !caverns[*pc].candle_)
          break;
      if (*pc == -1) {
        if (!caverns[mi].candle_)
          passed[np++] = mi;
        break;
      }
      else {
        pmi = mi;
        mi = *pc;
        ki++;
      }
    }
    for (int i = 0; i < np; i++) {
      if (i)
        putchar(' ');
      if (i == np - 1)
        putchar('/');
      putchar(passed[i] + 'A');
    }
    putchar('\n');
  }
  return 0;
}