UVa 890 - Maze (II)

Accepted date: 2016-02-29
Run Time: 0.046
Ranking (as of 2016-02-29): 4 out of 62
Language: C++

/*
  UVa 890 - Maze (II)

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

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

const int M_max = 39, N_max = 39;

int M, N, nr_cells;
char maze[M_max + 1][2 * (N_max + 1)];
bool visited[M_max + 1][N_max + 1];
pair<int, int> cells[M_max * N_max];

inline bool unvisited(int r, int c)
{
  return r >= 0 && r < M && c >= 0 && c < N && !visited[r][c];
}

inline void add_cell(int r, int c)
{
  visited[r][c] = true;
  cells[nr_cells++] = make_pair(r, c);
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &M, &N);
    for (int i = 0; i <= M; i++) {
      int j, k = (i) ? 2 * N : 2 * N - 1;
      for (j = 0; j <= k; j++) {
        if (j & 1)
          maze[i][j] = '_';
        else if (i)
          maze[i][j] = '|';
        else
          maze[i][j] = ' ';
      }
      maze[i][j] = '\0';
    }
#ifdef DEBUG
    for (int i = 0; i <= M; i++)
      puts(maze[i]);
#endif
    nr_cells = 0;
    for (int i = 0; i < M; i++)
      for (int j = 0; j < N; j++)
        visited[i][j] = false;
    int r, c;
    scanf("%d %d", &r, &c);
    r = M - r, c--;
    add_cell(r, c);
    while (true) {
      for ( ; nr_cells; nr_cells--) {
        const pair<int, int>& cell = cells[nr_cells - 1];
        if (unvisited(cell.first - 1, cell.second) ||
          unvisited(cell.first + 1, cell.second) ||
          unvisited(cell.first, cell.second - 1) ||
          unvisited(cell.first, cell.second + 1))
          break;
      }
      if (!nr_cells)
        break;
      const pair<int, int>& cell = cells[nr_cells - 1];
      char command[2];
      scanf("%s", command);
      switch (command[0]) {
      case 'F':
      {
        int n;
        scanf("%d", &n);
        reverse(cells + (n - 1), cells + nr_cells);
      }
        break;
      case 'U':
        r = cell.first - 1, c = cell.second;
        maze[r + 1][c * 2 + 1] = ' ';
        add_cell(r, c);
        break;
      case 'D':
        r = cell.first + 1, c = cell.second;
        maze[r][c * 2 + 1] = ' ';
        add_cell(r, c);
        break;
      case 'L':
        r = cell.first, c = cell.second - 1;
        maze[r + 1][(c + 1) * 2] = ' ';
        add_cell(r, c);
        break;
      case 'R':
        r = cell.first, c = cell.second + 1;
        maze[r + 1][c * 2] = ' ';
        add_cell(r, c);
        break;
      }
#ifdef DEBUG
      for (int i = 0; i <= M; i++)
        puts(maze[i]);
#endif
    }
    for (int i = 0; i <= M; i++)
      puts(maze[i]);
    putchar('\n');
  }
  return 0;
}

UVa 11482 - Building a Triangular Museum

Accepted date: 2016-02-28
Run Time: 0.003
Ranking (as of 2016-02-28): 3 out of 347
Language: C++

/*
  UVa 11482 - Building a Triangular Museum

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

#include <cstdio>

const int M_max = 100, N_max = 100;
char buff[M_max * 2 * N_max + 1];

int main()
{
  for (int x = 1; ; x++) {
    int M, N;
    scanf("%d %d", &M, &N);
    if (!M)
      break;
    printf("Triangular Museum %d\n", x);
    for (int n = 1, indent = M * N - 1; n <= N; n++)
      for (int m = 0, s = 0, t = 2 * (M - 1); m < M; m++, indent--, s += 2, t -= 2) {
        char* p = buff;
        for (int i = 0; i < indent; i++)
          *p++ = ' ';
        for (int i = 0; i < n; i++) {
          *p++ = '/';
          char c = (m < M - 1) ? ' ' : '_';
          for (int j = 0; j < s; j++)
            *p++ = c;
          *p++ = '\\';
          if (i < n - 1)
            for (int j = 0; j < t; j++)
              *p++ = ' ';
        }
        *p = '\0';
        puts(buff);
      }
    putchar('\n');
  }
  return 0;
}

UVa 570 - Stats

Accepted date: 2016-02-27
Run Time: 0.000
Ranking (as of 2016-02-27): 52 out of 228
Language: C++

/*
  UVa 570 - Stats

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

#include <cstdio>
#include <cstring>

const int nr_player_digits = 5;

struct stat {
  int g_; // number of games played
  int h_, k_, e_, b_, d_;
} stats[nr_player_digits + 1][nr_player_digits + 1];

int main()
{
  int n, p, g = 0;
  double h, k, e, b, d;
  char key[2];
  while (scanf("%s", key) != EOF) {
    switch (key[0]) {
    case 'C':
      scanf("%d", &n);
      while (n--) {
        scanf("%d", &p);
        stats[p / 10][p % 10].g_++;
      }
      g++;
      break;
    case 'H':
      scanf("%d", &p);
      stats[p / 10][p % 10].h_++;
      break;
    case 'K':
      scanf("%d", &p);
      stats[p / 10][p % 10].k_++;
      break;
    case 'E':
      scanf("%d", &p);
      stats[p / 10][p % 10].e_++;
      break;
    case 'B':
      scanf("%d", &p);
      stats[p / 10][p % 10].b_++;
      break;
    case 'D':
      scanf("%d", &p);
      stats[p / 10][p % 10].d_++;
      break;
    case 'R':
      puts("Player  Hit Pct    KPG      BPG      DPG");
      puts("-----------------------------------------");
      h = k = e = b = d = 0;
      for (int i = 0; i <= nr_player_digits; i++)
        for (int j = 0; j <= nr_player_digits; j++)
          if (stats[i][j].g_) {
            const stat& s = stats[i][j];
            printf("%02d      %+5.3lf  %7.3lf  %7.3lf  %7.3lf\n",
              i * 10 + j,
              ((s.k_ || s.e_ || s.h_) ?
                (static_cast<double>(s.k_) - s.e_) /
                  (static_cast<double>(s.k_) + s.e_ + s.h_) : 0.0),
              static_cast<double>(s.k_) / s.g_,
              static_cast<double>(s.b_) / s.g_,
              static_cast<double>(s.d_) / s.g_
            );
            h += s.h_, k += s.k_, e += s.e_, b += s.b_, d += s.d_;
          }
      printf("team    %+5.3lf  %7.3lf  %7.3lf  %7.3lf\n\n",
        (k - e) / (k + e + h), k / g, b / g, d / g);
      g = 0;
      memset(stats, 0, sizeof(stats));
      break;
    }
  }
  return 0;
}

UVa 12364 - In Braille

Accepted date: 2016-02-26
Run Time: 0.000
Ranking (as of 2016-02-26): 24 out of 396
Language: C++

/*
  UVa 12364 - In Braille

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

#include <cstdio>

const int nr_digits = '9' - '0' + 1, D_max = 100,
  nr_braille_lines = 3, nr_braille_chars = D_max * 3;
char digits[D_max + 1], braille[nr_braille_lines][nr_braille_chars];

const char* braille_numbers[nr_digits][nr_braille_lines] = {
  {".*", "**", ".."},
  {"*.", "..", ".."},
  {"*.", "*.", ".."},
  {"**", "..", ".."},
  {"**", ".*", ".."},
  {"*.", ".*", ".."},
  {"**", "*.", ".."},
  {"**", "**", ".."},
  {"*.", "**", ".."},
  {".*", "*.", ".."}
};

int braille_to_number(int bi)
{
  for (int n = 0; n < nr_digits; n++) {
    const char** b = braille_numbers[n];
    if (braille[0][bi] == b[0][0] && braille[0][bi + 1] == b[0][1] &&
      braille[1][bi] == b[1][0] && braille[1][bi + 1] == b[1][1])
      return n;
  }
  return -1;
}

int main()
{
  while (true) {
    int D;
    scanf("%d", &D);
    if (!D)
      break;
    getchar();
    char sb[8];
    gets(sb);
    if (sb[0] == 'S') {
      gets(digits);
      for (int i = 0, k = 0; i < D; i++, k += 3) {
        const char** b = braille_numbers[digits[i] - '0'];
        for (int j = 0; j < nr_braille_lines; j++) {
          braille[j][k] = b[j][0], braille[j][k + 1] = b[j][1];
          braille[j][k + 2] = (i < D - 1) ? ' ' : '\0';
        }
      }
      for (int i = 0; i < nr_braille_lines; i++)
        puts(braille[i]);
    }
    else {
      for (int i = 0; i < nr_braille_lines; i++)
        gets(braille[i]);
      for (int i = 0, j = 0; i < D; i++, j += 3)
        digits[i] = braille_to_number(j) + '0';
      digits[D] = '\0';
      puts(digits);
    }
  }
  return 0;
}

UVa 10333 - The Tower of ASCII

Accepted date: 2016-02-25
Run Time: 0.003
Ranking (as of 2016-02-25): 5 out of 361
Language: C++

/*
  UVa 10333 - The Tower of ASCII

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

#include <cstdio>

const int H_max = 500;
int nr_lefts, nr_rights, lefts[H_max], rights[H_max],
  left_heights[H_max + 1], right_heights[H_max + 1];

int main()
{
  int H;
  for (int t = 1; scanf("%d", &H) != EOF; t++) {
    nr_lefts = 0, nr_rights = 0;
    for (int lh = 1, h = H; ; lh++) {
      if (h - lh > lh) {
        lefts[nr_lefts++] = lh;
        h -= lh;
      }
      else {
        lefts[nr_lefts++] = h;
        break;
      }
    }
    for (int i = 0; i < nr_lefts - 1; i++)
      rights[nr_rights++] = lefts[i];
    rights[nr_rights - 1] += lefts[nr_lefts - 1];
    left_heights[0] = right_heights[0] = 0;
    for (int i = 1; i <= nr_lefts; i++)
      left_heights[i] = left_heights[i - 1] + lefts[i - 1];
    for (int i = 1; i <= nr_rights; i++)
      right_heights[i] = right_heights[i - 1] + rights[i - 1];
#ifdef DEBUG
    printf("left heights: ");
    for (int i = 0; i <= nr_lefts; i++)
      printf(" %d%c", left_heights[i], ((i < nr_lefts) ? ' ' : '\n'));
    printf("right heights: ");
    for (int i = 0; i <= nr_rights; i++)
      printf(" %d%c", right_heights[i], ((i < nr_rights) ? ' ' : '\n'));
#endif
    printf("Tower #%d\n", t);

    int indent = nr_lefts - 1;
    for (int i = 0; i < indent; i++)
      printf("  ");
    puts("#****#");
    for (int h = 1, lh = 1, rh = 1, w = 4; h < H; h++) {
      if (h == left_heights[lh])
        indent--;
      for (int i = 0; i < indent; i++)
        printf("  ");
      if (h == left_heights[lh])
        printf("#**");
      else
        putchar('#');
      for (int i = 0; i < w; i++)
        putchar('.');
      if (h == right_heights[rh])
        puts("**#");
      else
        puts("#");
      if (h == left_heights[lh])
        w += 2;
      else if (h + 1 == left_heights[lh + 1])
        lh++;
      if (h == right_heights[rh])
        w += 2;
      else if (h + 1 == right_heights[rh + 1])
        rh++;
    }
    putchar('\n');
  }
  return 0;
}

UVa 12414 - Calculating Yuan Fen

Accepted date: 2016-02-24
Run Time: 0.109
Ranking (as of 2016-02-24): 6 out of 245
Language: C++

/*
  UVa 12414 - Calculating Yuan Fen

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

#include <cstdio>
#include <cstring>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int nr_letters_max = 10, st_max = 10000, nr_chars_max = 127;
char previous[nr_chars_max + 1], current[nr_chars_max + 1];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  char s[nr_letters_max + 1];
  while (scanf("%s", s) != EOF) {
    int st, n, length = strlen(s);
    bool found = false;
    for (st = 1; st <= st_max; st++) {
      char* p = &previous[nr_chars_max];
      for (int i = length - 1; i >= 0; i--) {
        n = st + s[i] - 'A';
        do {
          *--p = '0' + n % 10;
          n /= 10;
        } while (n);
      }
#ifdef DEBUG
      printf("%s\n", p);
#endif
      char *ps = p, *cs = current, *pp, *cp;
      while (true) {
        for (pp = ps + 1, cp = cs; *pp; *pp++, *cp++)
          *cp = (*(pp - 1) - '0' + *pp - '0') % 10 + '0';
        *cp = '\0';
#ifdef DEBUG
        printf("%s\n", cs);
#endif
        if (cp - cs == 3 && cs[0] == '1' && cs[1] == '0' && cs[2] == '0') {
          found = true; break;
        }
        else if (cp - cs < 3)
          break;
        swap(ps, cs);
      }
      if (found)
        break;
    }
    if (found)
      printf("%d\n", st);
    else
      puts(":(");
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 645 - File Mapping

Accepted date: 2016-02-24
Run Time: 0.003
Ranking (as of 2016-02-24): 8 out of 210
Language: C++

/*
  UVa 645 - File Mapping

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

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

struct dir {
  const string name_;
  dir* parent_;
  vector<dir*> children_;
  vector<string> files_;

  dir(const string& name, dir* parent) : name_(name), parent_(parent) {}

  ~dir()
  {
    for (size_t i = 0, j = children_.size(); i < j; i++)
      delete children_[i];
  }

  void print(int depth)
  {
    for (int d = 0; d < depth; d++)
      cout << "|     ";
    cout << name_ << endl;
    for (size_t i = 0, j = children_.size(); i < j; i++)
      children_[i]->print(depth + 1);
    sort(files_.begin(), files_.end());
    for (size_t i = 0, j = files_.size(); i < j; i++) {
      for (int d = 0; d < depth; d++)
        cout << "|     ";
      cout << files_[i] << endl;
    }
  }
};

int main()
{
  for (int ds = 1; ; ds++) {
    string s;
    cin >> s;
    if (s == "#")
      break;
    if (ds > 1)
      cout << endl;
    dir* root = new dir("ROOT", NULL);
    dir* current = root;
    while (s != "*") {
      switch (s[0]) {
      case 'd':
      {
        dir* child = new dir(s, current);
        current->children_.push_back(child);
        current = child;
      }
        break;
      case 'f':
        current->files_.push_back(s);
        break;
      case ']':
        current = current->parent_;
        break;
      }
      cin >> s;
    }
    cout << "DATA SET " << ds << ":\n";
    root->print(0);
    delete root;
  }
  return 0;
}