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

UVa 10287 - Gifts in a Hexagonal Box

Accepted date: 2013-09-16
Ranking (as of 2013-09-16): 143 out of 765
Language: C++

/*
  UVa 10287 - Gifts in a Hexagonal Box

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

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

int main()
{
  const double c1 = sqrt(3.0) / 2.0, c2 = sqrt(3.0) / (2.0 + sqrt(3.0)),
    c3 = sqrt(3.0) / 4.0, c4 = (6.0 * sqrt(21.0) - 21.0) / (10.0 * sqrt(3.0));
  double s;
  while (cin >> s)
    cout << fixed <<
      setprecision(10) << c1 * s << ' ' << setprecision(10) << c2 * s << ' ' <<
      setprecision(10) << c3 * s << ' ' << setprecision(10) << c4 * s << endl;
  return 0;
}

UVa 462 - Bridge Hand Evaluator

Accepted date: 2013-09-15
Ranking (as of 2013-09-15): 118 out of 765
Language: C++

/*
  UVa 462 - Bridge Hand Evaluator

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

#include <cstdio>

enum {spade, heart, diamond, club};
const int nr_suits = club + 1, nr_ranks = 13;

struct suit {
  int nr_;
  bool ace_, jack_, queen_, king_;
} suits[nr_suits];

void initialize_suits()
{
  for (int i = 0; i < nr_suits; i++) {
    suits[i].nr_ = 0;
    suits[i].ace_ = suits[i].jack_ = suits[i].queen_ = suits[i].king_ = false;
  }
}

bool read_cards()
{
  char card[2 + 1];
  int si;
  for (int i = 0; i < nr_ranks; i++) {
    if (scanf("%s", card) == EOF)
      return false;
    switch (card[1]) {
    case 'S':
      si = spade; break;
    case 'H':
      si = heart; break;
    case 'D':
      si = diamond; break;
    default:
      si = club; break;
    }
    suits[si].nr_++;
    switch (card[0]) {
    case 'A':
      suits[si].ace_ = true; break;
    case 'J':
      suits[si].jack_ = true; break;
    case 'Q':
      suits[si].queen_ = true; break;
    case 'K':
      suits[si].king_ = true; break;
    default:
      break;
    }
  }
  return true;
}

int calculate_points_1_4()
{
  int points = 0;
  for (int si = 0; si < nr_suits; si++) {
    const suit& s = suits[si];
    if (s.ace_)
      points += 4;
    if (s.king_)
      points += (s.nr_ < 2) ? 2 : 3;
    if (s.queen_)
      points += (s.nr_ < 3) ? 1 : 2;
    if (s.jack_ && s.nr_ > 3)
      points++;
  }
  return points;
}

int calculate_points_5_7()
{
  int points = 0;
  for (int si = 0; si < nr_suits; si++) {
    const suit& s = suits[si];
    if (s.nr_ == 2)
      points++;
    else if (s.nr_ < 2)
      points += 2;
  }
  return points;
}

bool is_no_trump(int points)
{
  if (points < 16)
    return false;
  for (int si = 0; si < nr_suits; si++) {
    const suit& s = suits[si];
    if (s.ace_ || s.king_ && s.nr_ > 1 ||
      s.queen_ && s.nr_ > 2) // suit is stopped
      ;
    else
      return false;
  }
  return true;
}

char bid()
{
  const char ss[] = "SHDC";
  int max_si, max_nr = 0;
  for (int si = 0; si < nr_suits; si++)
    if (suits[si].nr_ > max_nr) {
      max_si = si;
      max_nr = suits[si].nr_;
    }
  return ss[max_si];
}

int main()
{
  while (true) {
    initialize_suits();
    if (!read_cards())
      break;
    int points = calculate_points_1_4();
    if (is_no_trump(points))
      puts("BID NO-TRUMP");
    else {
      points += calculate_points_5_7();
      if (points < 14)
        puts("PASS");
      else
        printf("BID %c\n", bid());
    }
  }
  return 0;
}

UVa 10284 - Chessboard in FEN

Accepted date: 2013-09-15
Ranking (as of 2013-09-15): 160 out of 757
Language: C++

/*
  UVa 10284 - Chessboard in FEN

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

#include <cstdio>
#include <cstring>
#include <cctype>

const int nr_rows = 8, nr_columns = 8;
char chessboard[nr_rows][nr_columns], fen[nr_rows * (nr_columns + 1) + 1];

bool attack(int r, int c)
{
  if (r < 0 || r >= nr_rows || c < 0 || c >= nr_columns ||
    isalpha(chessboard[r][c]))
    return false;
  chessboard[r][c] = '+';
  return true;
}

void king_attack(int r, int c)
{
  for (int ri = r - 1; ri <= r + 1; ri++)
    for (int ci = c - 1; ci <= c + 1; ci++)
      if (ri != r || ci != c)
        attack(ri, ci);
}

void rook_attack(int r, int c)
{
  int ri, ci;
  for (ri = r - 1; ; ri--)
    if (!attack(ri, c))
      break;
  for (ri = r + 1; ; ri++)
    if (!attack(ri, c))
      break;
  for (ci = c - 1; ; ci--)
    if (!attack(r, ci))
      break;
  for (ci = c + 1; ; ci++)
    if (!attack(r, ci))
      break;
}

void bishop_attack(int r, int c)
{
  int ri, ci;
  for (ri = r - 1, ci = c - 1; ; ri--, ci--)
    if (!attack(ri, ci))
      break;
  for (ri = r - 1, ci = c + 1; ; ri--, ci++)
    if (!attack(ri, ci))
      break;
  for (ri = r + 1, ci = c - 1; ; ri++, ci--)
    if (!attack(ri, ci))
      break;
  for (ri = r + 1, ci = c + 1; ; ri++, ci++)
    if (!attack(ri, ci))
      break;
}

void knight_attack(int r, int c)
{
  attack(r - 2, c - 1);
  attack(r - 2, c + 1);
  attack(r - 1, c - 2);
  attack(r - 1, c + 2);
  attack(r + 1, c - 2);
  attack(r + 1, c + 2);
  attack(r + 2, c - 1);
  attack(r + 2, c + 1);
}

#ifdef DEBUG
void print_chessboard()
{
  for (int r = 0; r < nr_rows; r++)
    for (int c = 0; c < nr_columns; c++)
    printf("%c%c", chessboard[r][c], ((c == nr_columns - 1) ? '\n' : ' '));
}
#endif

int main()
{
  while (scanf("%s", fen) != EOF) {
    memset(chessboard, '-', sizeof(chessboard));
    int r = 0, c = 0;
    for (const char* p = fen; *p; p++) {
      if (*p == '/') {
        r++; c = 0;
      }
      else if (isdigit(*p))
        c += *p - '0';
      else
        chessboard[r][c++] = *p;
    }
    for (r = 0; r < nr_rows; r++)
      for (c = 0; c < nr_columns; c++) {
        switch (chessboard[r][c]) {
        case 'k': case 'K':
          king_attack(r, c);
          break;
        case 'q': case 'Q':
          rook_attack(r, c);
          bishop_attack(r, c);
          break;
        case 'b': case 'B':
          bishop_attack(r, c);
          break;
        case 'n': case 'N':
          knight_attack(r, c);
          break;
        case 'r': case 'R':
          rook_attack(r, c);
          break;
        case 'p':
          attack(r + 1, c - 1);
          attack(r + 1, c + 1);
          break;
        case 'P':
          attack(r - 1, c - 1);
          attack(r - 1, c + 1);
          break;
        }
#ifdef DEBUG
        if (isalpha(chessboard[r][c])) {
          printf("%d %d: %c\n", r, c, chessboard[r][c]);
          print_chessboard();
        }
#endif
      }
    int nr_unoccupied = 0;
    for (r = 0; r < nr_rows; r++)
      for (c = 0; c < nr_columns; c++)
        if (chessboard[r][c] == '-')
          nr_unoccupied++;
    printf("%d\n", nr_unoccupied);
  }
  return 0;
}

UVa 10500 - Robot maps

Accepted date: 2013-09-14
Language: C++

/*
  UVa 10500 - Robot maps

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

#include <iostream>
using namespace std;

const int n_max = 10, m_max = 10;
char map[n_max + 1][m_max + 1], robot_map[n_max +1][m_max + 1];
bool visited[n_max + 1][m_max + 1];

int dfs(int n, int m, int px, int py)
{
  const int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  const size_t nr_dirs = sizeof(dirs) / sizeof(dirs[0]);

  visited[px][py] = true;
  for (size_t i = 0; i < nr_dirs; i++) {
    int x = px + dirs[i][0], y = py + dirs[i][1];
    if (x >= 1 && x <= n && y >= 1 && y <= m)
      robot_map[x][y] = map[x][y];
  }
  int nr_visited = 0;
  for (size_t i = 0; i < nr_dirs; i++) {
    int x = px + dirs[i][0], y = py + dirs[i][1];
    if (x >= 1 && x <= n && y >= 1 && y <= m &&
      map[x][y] == '0' && !visited[x][y]) {
      nr_visited = 1 + dfs(n, m, x, y);
      break;
    }
  }
  return nr_visited;
}

int main()
{
  while (true) {
    int n, m;
    cin >> n >> m;
    if (!n && !m)
      break;
    int x_ini, y_ini;
    cin >> x_ini >> y_ini;
    for (int x = 1; x <= n; x++)
      for (int y = 1; y <= m; y++) {
        visited[x][y] = false;
        robot_map[x][y] = '?';
        cin >> map[x][y];
      }
    robot_map[x_ini][y_ini] = '0';
    int nr_movements = dfs(n, m, x_ini, y_ini);
    cout << endl;
    for (int y = 1; y <= m; y++)
      cout << "|---";
    cout << "|\n";
    for (int x = 1; x <= n; x++) {
      for (int y = 1; y <= m; y++)
        cout << "| " << robot_map[x][y] << ' ';
      cout << "|\n";
      for (int y = 1; y <= m; y++)
        cout << "|---";
      cout << "|\n";
    }
    cout << "\nNUMBER OF MOVEMENTS: " << nr_movements << endl;
  }
  return 0;
}

UVa 416 - LED Test

Accepted date: 2013-09-14
Ranking (as of 2013-09-14): 312 out of 754
Language: C++

/*
  UVa 416 - LED Test

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

#include <cstdio>

const unsigned char leds[] =
  {0x7e, 0x30, 0x6d, 0x79, 0x33, 0x5b, 0x5f, 0x70, 0x7f, 0x7b};
const int n_max = sizeof(leds);

unsigned char s_to_sequence(const char* s)
{
  unsigned char sq = 0, b = 0x40;
  do {
    if (*s++ == 'Y')
      sq |= b;
    b >>= 1;
  } while (b);
  return sq;
}

bool match_sequence(int n, unsigned char sequence[])
{
  for (int ns = n_max; ns >= n; ns--) {
    bool match = true;
    unsigned char not_burned = 0x7f;
    for (int i = 1; i <= n; i++) {
      unsigned char led = leds[ns - i];
      led &= not_burned;
      unsigned char diff = led ^ sequence[i - 1];
      unsigned char db = diff, lb = led;
      for ( ; db; db >>= 1, lb >>= 1)
        if (db & 1 && !(lb & 1))
          break; // no burned-out segments will recover
      if (db) {
        match = false; break;
      }
      not_burned &= ~diff;
    }
    if (match)
      return true;
  }
  return false;
}

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    unsigned char sequence[n_max];
    for (int i = 0; i < n; i++) {
      char s[7 + 1];
      scanf("%s", s);
      sequence[i] = s_to_sequence(s);
    }
    if (match_sequence(n, sequence))
      puts("MATCH");
    else
      puts("MISMATCH");
  }
  return 0;
}

UVa 10493 - Cats, with or without Hats

Accepted date: 2013-09-13
Ranking (as of 2013-09-14): 496 out of 762
Language: C++

/*
  UVa 10493 - Cats, with or without Hats

  To build using Visual Studio 2010:
    cl -EHsc -O2 UVa_10493_Cats_with_or_without_Hats.cpp
*/

#include <iostream>
using namespace std;

int how_many_cats(int n, int m)
{
  if (n == 1)
    return (m == 1) ? -1 : 0;
  if (m == 1)
    return 1;
  int nc = m;
  while (m > 1) {
    if (m < n)
      return 0;
    nc += m / n;
    m = m / n + m % n;
  }
  return nc;
}

int main()
{
  while (true) {
    int n, m;
    cin >> n >> m;
    if (!n)
      break;
    cout << n << ' ' << m << ' ';
    int nc = how_many_cats(n, m);
    if (nc == -1)
      cout << "Multiple\n";
    else if (!nc)
      cout << "Impossible\n";
    else
      cout << nc << endl;
  }
  return 0;
}

UVa 11384 - Help is needed for Dexter

Accepted date: 2013-09-07
Ranking (as of 2013-09-08): 672 out of 764
Language: C++

/*
  UVa 11384 - Help is needed for Dexter

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

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

int main()
{
  const double log2 = log(2.0);
  int n;
  while (cin >> n)
    cout << static_cast<int>(log(static_cast<double>(n)) / log2) + 1 << endl;
      // log2(n) + 1
  return 0;
}