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

UVa 426 - Fifth Bank of Swamp County

Accepted date: 2016-02-23
Run Time: 0.013
Ranking (as of 2016-02-23): 5 out of 207
Language: C++

/*
  UVa 426 - Fifth Bank of Swamp County

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

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

#ifndef BUFSIZ
#define BUFSIZ  1024
#endif

const int number_max = 9999;

struct check {
  int y_, m_, d_;
  int number_;
  double amount_;

bool operator<(const check& c) const {return number_ < c.number_;}
} checks[number_max];

int main()
{
  int N;
  scanf("%d", &N);
  getchar();
  getchar();
  while (N--) {
    char s[BUFSIZ];
    int nr_checks = 0;
    while (gets(s) && s[0]) {
      char *p = s, *q;
      check& c = checks[nr_checks];
      c.y_ = strtol(p, &q, 10);
      p = ++q;
      c.m_ = strtol(p, &q, 10);
      p = ++q;
      c.d_ = strtol(p, &q, 10);
      p = q;
      c.number_ = strtol(p, &q, 10);
      c.amount_ = strtod(q, NULL);
      if (c.amount_ < 1000000.0)
        nr_checks++;
    }
    sort(checks, checks + nr_checks);
    int nr_rows = (nr_checks + 2) / 3;
    for (int i = 0; i < nr_rows; i++)
      for (int j = i; j < nr_checks; j += nr_rows) {
        const check& c = checks[j];
        printf("%4d%c %9.2lf %02d/%02d/%02d%s", c.number_,
          ((j && c.number_ != checks[j - 1].number_ + 1) ? '*' : ' '),
          c.amount_, c.y_, c.m_, c.d_,
          ((j + nr_rows < nr_checks) ? "   " : "\n"));
      }
    if (N)
      putchar('\n');
  }
  return 0;
}

UVa 736 - Lost in Space

Accepted date: 2016-02-20
Run Time: 0.016
Ranking (as of 2016-02-20): 5 out of 195
Language: C++

/*
  UVa 736 - Lost in Space

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

#include <cstdio>

const int nr_dirs = 8, N_max = 50;

const struct dir {
  const char* s_;
  int r_, c_;
} dirs[nr_dirs] = {
  {"N", -1, 0}, {"NE", -1, 1}, {"E", 0, 1}, {"SE", 1, 1},
  {"S", 1, 0}, {"SW", 1, -1}, {"W", 0, -1}, {"NW", -1, -1}
};

bool appear(int N, const char strings[N_max][N_max + 1], const char s[N_max + 1],
  int r, int c, int dr, int dc)
{
  for (int i = 1; s[i]; i++) {
    do {
      r += dr, c += dc;
      if (r < 0 || r >= N || c < 0 || c >= N)
        return false;
    } while (strings[r][c] == ' ');
    if (strings[r][c] != s[i])
      return false;
  }
  return true;
}

int main()
{
  int ds;
  scanf("%d", &ds);
  while (ds--) {
    int N;
    scanf("%d", &N);
    getchar();
    char strings[N_max][N_max + 1];
    for (int r = 0; r < N; r++)
      gets(strings[r]);
    while (true) {
      char s[N_max + 1];
      if (!gets(s) || !s[0])
        break;
      printf("\n%s\n", s);
      bool found = false;
      for (int r = 0; r < N; r++)
        for (int c = 0; c < N; c++)
          if (strings[r][c] == s[0])
            for (int d = 0; d < nr_dirs; d++)
              if (appear(N, strings, s, r, c, dirs[d].r_, dirs[d].c_)) {
                found = true;
                printf("(%d,%d) - %s\n", r + 1, c + 1, dirs[d].s_);
              }
      if (!found)
        puts("not found");
    }
    if (ds)
      putchar('\n');
  }
  return 0;
}

UVa 760 - DNA Sequencing

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

/*
  UVa 760 - DNA Sequencing

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

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

const int nr_chars_max = 300;

int lengths[nr_chars_max][nr_chars_max], indices[nr_chars_max];
char lcss[nr_chars_max][nr_chars_max + 1];

int compare_string(const void* i,const void* j)
{
  return strcmp(reinterpret_cast<const char*>(i),
    reinterpret_cast<const char*>(j));
}

int main()
{
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  while (true) {
    gets(s);
    gets(t);
    int m = strlen(s), n = strlen(t), longest = 0, nr_lcss;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        if (s[i] == t[j]) {
          if (i == 0 || j == 0)
            lengths[i][j] = 1;
          else
            lengths[i][j] = lengths[i - 1][j - 1] + 1;
          if (lengths[i][j] > longest) {
            longest = lengths[i][j];
            nr_lcss = 1;
            indices[0] = i;
          }
          else {
            if (lengths[i][j] == longest)
              indices[nr_lcss++] = i;
          }
        }
        else
          lengths[i][j] = 0;
      }
    if (longest) {
      for (int i = 0; i < nr_lcss; i++) {
        strncpy(lcss[i], s + indices[i] - longest + 1, longest);
        lcss[i][longest] = '\0';
      }
      qsort(lcss, nr_lcss, nr_chars_max + 1, compare_string);
      for (int i = 0, j = 0; i < nr_lcss; i++) {
        if (i) {
          if (strcmp(lcss[j], lcss[i])) {
            j = i;
            puts(lcss[i]);
          }
        }
        else
          puts(lcss[i]);
      }
    }
    else
      puts("No common sequence.");
    if (!gets(s))
      break;
    putchar('\n');
  }
  return 0;
}

UVa 11048 - Automatic Correction of Misspellings

Accepted date: 2016-02-13
Run Time: 0.066
Ranking (as of 2016-02-13): 48 out of 435
Language: C++

/*
  UVa 11048 - Automatic Correction of Misspellings

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

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

const int nr_words_max = 10000, nr_chars_max = 25;
char words[nr_words_max + 1][nr_chars_max + 1],
  sorted_words[nr_words_max + 1][nr_chars_max + 1];

int compare_word(const void* i, const void* j)
{
  return strcmp(reinterpret_cast<const char*>(i),
    reinterpret_cast<const char*>(j));
}

int correct_or_misspelling(const char* w, const char* s)
{
  while (*w && *s && *w == *s)
    w++, s++;
  if (!*w && !*s)
    return 1; // correct
  else if (!strcmp(w + 1, s) || !strcmp(w, s + 1) || !strcmp(w + 1, s + 1))
    return 0;
  else if (*(w + 1) == *s && *w == *(s + 1) && !strcmp(w + 2, s + 2))
    return 0;
  else
    return -1;
}

int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", words[i]);
    strcpy(sorted_words[i], words[i]);
  }
  qsort(sorted_words, n, nr_chars_max + 1, compare_word);
  int q;
  scanf("%d", &q);
  while (q--) {
    char s[nr_chars_max + 1];
    scanf("%s", s);
    if (bsearch(s, sorted_words, n, nr_chars_max + 1, compare_word))
      printf("%s is correct\n", s);
    else {
      int misspelling = -1;
      for (int i = 0; i < n; i++)
        if (correct_or_misspelling(words[i], s) == 0) {
          misspelling = i;
          break;
        }
      if (misspelling != -1)
        printf("%s is a misspelling of %s\n", s, words[misspelling]);
      else
        printf("%s is unknown\n", s);
    }
  }
  return 0;
}

UVa 10466 - How Far?

Accepted date: 2016-02-12
Run Time: 0.023
Ranking (as of 2016-02-12): 15 out of 470
Language: C++

/*
  UVa 10466 - How Far?

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

#include <cstdio>
#include <cmath>

int main()
{
  const double pi = 2.0 * acos(0.0);
  int n;
  double T;
  while (scanf("%d %lf", &n, &T) != EOF) {
    double angle, x = 0.0, y = 0.0, r, t;
    while (n--) {
      scanf("%lf %lf", &r, &t);
      angle = T * pi * 2.0 / t;
      x += r * cos(angle), y += r * sin(angle);
      printf("%.4lf%c", sqrt(x * x + y * y), ((n) ?  ' ' : '\n'));
    }
  }
  return 0;
}

UVa 10577 - Bounding box

Accepted date: 2016-02-11
Run Time: 0.000
Ranking (as of 2016-02-11): 91 out of 435
Language: C++

/*
  UVa 10577 - Bounding box

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

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

const double pi = 2.0 * acos(0.0);

struct point {
  double x_, y_;
  point() {}
  point(double x, double y) : x_(x), y_(y) {}
};

double square_distance(const point& p, const point& q)
{
  double dx = p.x_ - q.x_, dy = p.y_ - q.y_;
  return dx * dx + dy * dy;
}

point rotate(const point& o, const point& p, double angle)
{
  // rotate p around o by angle
  double dx = p.x_ - o.x_, dy = p.y_ - o.y_;
  return point(o.x_ + dx * cos(angle) - dy * sin(angle),
    o.y_ + dx * sin(angle) + dy * cos(angle));
}

int main()
{
  for (int p = 1; ; p++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    const int nr_points = 3;
    point A, B, C;
    scanf("%lf %lf", &A.x_, &A.y_);
    scanf("%lf %lf", &B.x_, &B.y_);
    scanf("%lf %lf", &C.x_, &C.y_);
    double as = square_distance(B, C), bs = square_distance(C, A),
      cs = square_distance(A, B);
    double ad = bs + cs - as, bd = cs + as - bs, cd = as + bs - cs;
    double ud = as * ad + bs * bd + cs * cd;
    point cc; // circumcenter
    cc.x_ = (as * ad * A.x_ + bs * bd * B.x_ + cs * cd * C.x_) / ud;
    cc.y_ = (as * ad * A.y_ + bs * bd * B.y_ + cs * cd * C.y_) / ud;
    double angle = pi * 2.0 / n;
    double x_min = A.x_, x_max = A.x_, y_min = A.y_, y_max = A.y_;
    for (int i = 1; i < n; i++) {
      point p = rotate(cc, A, angle * i);
      x_min = min(x_min, p.x_), x_max = max(x_max, p.x_);
      y_min = min(y_min, p.y_), y_max = max(y_max, p.y_);
    }
    printf("Polygon %d: %.3lf\n", p, (x_max - x_min) * (y_max - y_min));
  }
  return 0;
}

UVa 11532 - Simple Adjacency Maximization

Accepted date: 2016-02-09
Run Time: 0.000
Ranking (as of 2016-02-09): 47 out of 441
Language: C++

/*
  UVa 11532 - Simple Adjacency Maximization

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

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

int main()
{
  int C, P, Q;
  scanf("%d", &C);
  while (C--) {
    scanf("%d %d", &P, &Q);
    int p = 0, q = 0;
    unsigned long long l = 0, b = 1;
    if (p < P) {
      p++;
      l |= b;
      b <<= 1;
    }
    if (q < Q) {
      q++;
      b <<= 1;
    }
    while (p < P || q < Q) {
      if (p < P) {
        p++;
        l |= b;
        b <<= 1;
      }
      if (p < P) {
        p++;
        l |= b;
        b <<= 1;
      }
      if (q < Q) {
        q++;
        b <<= 1;
      }
    }
    b >>= 1;
    unsigned long long rl = 0, rb = 1;
    for (int i = P + Q - 1; i >= 0; i--, b >>= 1, rb <<= 1)
      if (l & b)
        rl |= rb;
    printf("%llu\n", min(l, rl));
  }
  return 0;
}

UVa 11076 - Add Again

Accepted date: 2016-02-08
Run Time: 0.019
Ranking (as of 2016-02-09): 27 out of 787
Language: C++

/*
  UVa 11076 - Add Again

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

#include <cstdio>
#include <cstring>

const int nr_digits = '9' - '0' + 1, N_max = 12;
int freqs[nr_digits], factorials[N_max + 1];

int main()
{
  factorials[0] = factorials[1] = 1;
  for (int i = 2; i <= N_max; i++)
    factorials[i] = factorials[i - 1] * i;
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    memset(freqs, 0, sizeof(freqs));
    for (int i = 0; i < N; i++) {
      int d;
      scanf("%d", &d);
      freqs[d]++;
    }
    unsigned long long ds = 0;
    for (int i = 1; i < nr_digits; i++)
      if (freqs[i]) {
        int f = factorials[N - 1];
        for (int j = 0; j < nr_digits; j++)
          if (freqs[j]) {
            if (i == j)
              f /= factorials[freqs[j] - 1];
            else
              f /= factorials[freqs[j]];
          }
        ds += i * f;
#ifdef DEBUG
        printf("%d: %d %llu\n", i, i * f, ds);
#endif
      }
    unsigned long long s = 0;
    for (int i = 0; i < N; i++, ds *= 10)
      s += ds;
    printf("%llu\n", s);
  }
  return 0;
}

UVa 10060 - A hole to catch a man

Accepted date: 2016-02-03
Run Time: 0.000
Ranking (as of 2016-02-03): 31 out of 667
Language: C++

/*
  UVa 10060 - A hole to catch a man

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

#include <cstdio>
#include <cmath>

const double pi = 2.0 * acos(0.0);

double get_sheet_volume()
{
  double T, x0, y0;
  scanf("%lf %lf %lf", &T, &x0, &y0);
  double x = x0, y = y0, area = 0.0;
  while (true) {
    double nx, ny;
    scanf("%lf %lf", &nx, &ny);
    area += x * ny - nx * y;
    x = nx, y = ny;
    if (x == x0 && y == y0)
      break;
  }
  return T * fabs(area) / 2.0;
}

int main()
{
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    double sv = 0.0;
    while (N--)
      sv += get_sheet_volume();
    double R, T;
    scanf("%lf %lf", &R, &T);
    double cv = pi * R * R * T;
    printf("%d\n", static_cast<int>(sv / cv));
  }
  return 0;
}