UVa 391 - Mark-up

Accepted date: 2013-10-31
Language: C++

/*
  UVa 391 - Mark-up

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

#include <cstdio>
#include <cctype>

int main()
{
  bool mark_ups = true;
  int c;
  while ((c = getchar()) != EOF) {
    if (c == '\\') {
      if ((c = getchar()) == EOF) {
        putchar('\\');
        return 0;
      }
      else if (c == '*')
        mark_ups = !mark_ups;
      else if (mark_ups) {
        switch (c) {
        case 'b': case 'i':
          break;
        case 's':
          do
            c = getchar();
          while (isdigit(c) || c == '.');
          if (c == EOF)
            return 0;
          else
            ungetc(c, stdin);
          break;
        default:
          putchar(c);
          break;
        }
      }
      else {
        ungetc(c, stdin);
        putchar('\\');
      }
    }
    else
      putchar(c);
  }
  return 0;
}

UVa 10016 - Flip-Flop the Squarelotron

Accepted date: 2013-10-29
Ranking (as of 2013-10-29): 35 out of 701
Language: C++

/*
  UVa 10016 - Flip-Flop the Squarelotron

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

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

const int n_max = 100;
int matrix[n_max][n_max];

/*
For the rgi-th ring (rgi >= 0), the corresponding elements of matrix are:
  matrix[rgi][rgi] - matrix[rgi][n - 1 - rgi] // top row
  matrix[n - 1 - rgi][rgi] - matrix[n - 1 - rgi][n - 1 - rgi] // bottom row

  matrix[rgi][rgi] - matrix[n - 1 - rgi][rgi] // left column
  matrix[rgi][n - 1 - rgi] - matrix[n - 1 - rgi][n - 1 - rgi] // right column
*/

enum {upside_down = 1, left_right, main_diagonal, main_inverse_diagonal};

void upside_down_flip(int n, int rgi)
{
  for (int c = rgi; c < n - rgi; c++)
    swap(matrix[rgi][c], matrix[n - 1 - rgi][c]);
  for (int r = rgi + 1; r < n / 2; r++) {
    swap(matrix[r][rgi], matrix[n - 1 - r][rgi]);
    swap(matrix[r][n - 1 - rgi], matrix[n - 1 - r][n - 1 - rgi]);
  }
}

void left_right_flip(int n, int rgi)
{
  for (int r = rgi; r < n - rgi; r++)
    swap(matrix[r][rgi], matrix[r][n - 1 - rgi]);
  for (int c = rgi + 1; c < n / 2; c++) {
    swap(matrix[rgi][c], matrix[rgi][n - 1 - c]);
    swap(matrix[n - 1 - rgi][c], matrix[n - 1 - rgi][n - 1 - c]);
  }
}

void main_diagonal_flip(int n, int rgi)
{
  for (int c = rgi + 1; c < n - rgi; c++)
    swap(matrix[rgi][c], matrix[c][rgi]);
  for (int c = rgi + 1; c < n - rgi - 1; c++)
    swap(matrix[n - 1 - rgi][c], matrix[c][n - 1 - rgi]);
}

void main_inverse_diagonal_flip(int n, int rgi)
{
  for (int c = rgi; c < n - rgi - 1; c++)
    swap(matrix[rgi][c], matrix[n - 1 - c][n - 1 - rgi]);
  for (int c = rgi + 1; c < n - rgi - 1; c++)
    swap(matrix[n - 1 - rgi][c], matrix[n - 1 - c][rgi]);
}

int main()
{
  int m;
  scanf("%d", &m);
  while (m--) {
    int n;
    scanf("%d", &n);
    for (int r = 0; r < n; r++)
      for (int c = 0; c < n; c++)
        scanf("%d", &matrix[r][c]);
    for (int rgi = 0, nr_rings = (n + 1) / 2; rgi < nr_rings; rgi++) {
      int t;
      scanf("%d", &t);
      while (t--) {
        int c;
        scanf("%d", &c);
        switch (c) {
        case upside_down:
          upside_down_flip(n, rgi);
          break;
        case left_right:
          left_right_flip(n, rgi);
          break;
        case main_diagonal:
          main_diagonal_flip(n, rgi);
          break;
        case main_inverse_diagonal:
          main_inverse_diagonal_flip(n, rgi);
          break;
        }
#ifdef DEBUG
        for (int r = 0; r < n; r++)
          for (int c = 0; c < n; c++)
            fprintf(stderr, "%d%c", matrix[r][c], ((c == n - 1) ? '\n' : ' '));
#endif
      }
    }
    for (int r = 0; r < n; r++)
      for (int c = 0; c < n; c++)
        printf("%d%c", matrix[r][c], ((c == n - 1) ? '\n' : ' '));
  }
  return 0;
}

UVa 10247 - Complete Tree Labeling

Accepted date: 2011-02-15
Ranking (as of 2013-10-27): 164 out of 453
Language: JAVA

/*
  6.6.5 Complete Tree Labeling
  PC/UVa IDs: 110605/10247, Popularity: C, Success rate: average Level: 2
*/

/*
total number of nodes for a k-ary tree of depth d = Σ(i = 0 to d) pow(k, i) = 
  (pow(k, d + 1) - 1) / (k - 1).
number of nodes at the i-th level of depth = pow(k, i), 
  each of which has pow(k, i + 1) nodes.
*/

import java.util.Scanner;
import java.util.HashMap;
import java.math.BigInteger;

class Main {
  static int numberOfNodes(int k, int d) {
    // number of nodes for a k-ary tree of depth d
    return ((int)Math.pow((double)k, (double)d + 1.0) - 1) / (k - 1);
  }

  static BigInteger factorial(int n) {
    BigInteger f = BigInteger.ONE;
    for (int i = 1; i <= n; i++)
      f = f.multiply(BigInteger.valueOf(i));
    return f;
  }

  static HashMap<Long, BigInteger> combinationCache = 
    new HashMap<Long, BigInteger>();

  static BigInteger combination(int n, int k) {
    if (k == 0 || n == k)
      return BigInteger.ONE;
    else {
      long nk = (long)n << 32 | k;
      BigInteger c = combinationCache.get(nk);
      if (c != null)
        return c;
      c = factorial(n).divide(factorial(n - k).multiply(factorial(k)));
      combinationCache.put(nk, c);
      return c;
    }
  }

  static HashMap<Long, BigInteger> cache = new HashMap<Long, BigInteger>();

  static BigInteger completeTreeLabeling(
    int k /* branching factor */, int d /* depth */) {
    if (k == 1)
      return BigInteger.ONE;
    long kd = (long)k << 32 | d;
    BigInteger nrLabeling = cache.get(kd);
    if (nrLabeling != null)
      return nrLabeling;
    nrLabeling = factorial(k);
    if (d > 1) {
      // number of nodes for a k-ary tree of depth d
      int nrNodes = numberOfNodes(k, d);
      // number of descendants of the root node for a k-ary tree of depth (d - 1)
      int nrDescendants = numberOfNodes(k, d - 1) - 1;
      // number of labeling for a k-ary tree of depth (d - 1)
      BigInteger nrDescendantsLabeling = completeTreeLabeling(k, d - 1);
      for (int i = nrNodes - 2; i >= nrDescendants; i -= nrDescendants + 1) {
        BigInteger c = combination(i, nrDescendants);
        nrLabeling = nrLabeling.multiply(c).multiply(nrDescendantsLabeling);
      }
    }
    cache.put(kd, nrLabeling);
    return nrLabeling;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextInt()) {
      int k = sc.nextInt();
      if (sc.hasNextInt()) {
        int d = sc.nextInt();
        System.out.println(completeTreeLabeling(k, d));
      }
    }
  }
}

UVa 183 - Bit Maps

Accepted date: 2013-10-27
Language: C++

/*
  UVa 183 - Bit Maps

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

#include <cstdio>

const int rows_max = 200, columns_max = 200;
int bitmap[rows_max][columns_max];
int sums[rows_max][columns_max];
  // sum[i][j] is the sum of bitmap[bi][bj] (0 <= bi <= i, 0 <= bj <= j)
const int nr_chars_max = 50;
int nr_chars;

int zeros_ones(int top, int left, int bottom, int right)
{
  int s = sums[bottom][right];
  if (top && left)
    s += sums[top - 1][left - 1] - sums[top - 1][right] - sums[bottom][left - 1];
  else if (top)
    s -= sums[top - 1][right];
  else if (left)
    s -= sums[bottom][left - 1];
  if (!s)
    return 0; // all zeros
  else if (s == (bottom - top + 1) * (right - left + 1))
    return 1; // all ones
  else
    return -1;
}

void bitmap_putchar(char c)
{
  putchar(c);
  if (++nr_chars == nr_chars_max) {
    nr_chars = 0;
    putchar('\n');
  }
}

void quarters(int top, int left, int bottom, int right)
{
  int zo = zeros_ones(top, left, bottom, right);
  if (zo >= 0) // all zeros or ones
    bitmap_putchar(static_cast<char>(zo + '0'));
  else {
    bitmap_putchar('D');
    int rows = bottom - top + 1, columns = right - left + 1;
    if (rows > 1 && columns > 1) {
      quarters(top, left, top + (rows - 1) / 2, left + (columns - 1) / 2);
      quarters(top, left + (columns + 1) / 2, top + (rows - 1) / 2,  right);
      quarters(top + (rows + 1) / 2, left, bottom, left + (columns - 1) / 2);
      quarters(top + (rows + 1) / 2, left + (columns + 1) / 2, bottom, right);
    }
    else if (rows > 1) {
      quarters(top, left, top + (rows - 1) / 2, right);
      quarters(top + (rows + 1) / 2, left, bottom, right);
    }
    else {
      quarters(top, left, bottom, left + (columns - 1) / 2);
      quarters(top, left + (columns + 1) / 2, bottom,  right);
    }
  }
}

void decomposition(int rows, int columns)
{
  for (int r = 0; r < rows; r++) {
    int ones = 0;
    for (int c = 0; c < columns; c++) {
      char zero_or_one;
      do
        zero_or_one = getchar();
      while (zero_or_one == '\n');
      bitmap[r][c] = zero_or_one - '0';
      ones += bitmap[r][c];
      sums[r][c] = ones;
      if (r)
        sums[r][c] += sums[r - 1][c];
    }
  }
#ifdef DEBUG
  for (int r = 0; r < rows; r++)
    for (int c = 0; c < columns; c++)
      fprintf(stderr, "%4d%c", bitmap[r][c], ((c == columns - 1) ? '\n' : ' '));
  for (int r = 0; r < rows; r++)
    for (int c = 0; c < columns; c++)
      fprintf(stderr, "%4d%c", sums[r][c], ((c == columns - 1) ? '\n' : ' '));
#endif
  quarters(0, 0, rows - 1, columns - 1);
  if (nr_chars)
    putchar('\n');
}

void composition(int top, int left, int bottom, int right)
{
  char c;
  do
    c = getchar();
  while (c == '\n');
  if (c == '0' || c == '1') {
    c -= '0';
    for (int i = top; i <= bottom; i++)
      for (int j = left; j <= right; j++)
        bitmap[i][j] = c;
  }
  else { // 'D'
    int rows = bottom - top + 1, columns = right - left + 1;
    if (rows > 1 && columns > 1) {
      composition(top, left, top + (rows - 1) / 2, left + (columns - 1) / 2);
      composition(top, left + (columns + 1) / 2, top + (rows - 1) / 2,  right);
      composition(top + (rows + 1) / 2, left, bottom, left + (columns - 1) / 2);
      composition(top + (rows + 1) / 2, left + (columns + 1) / 2, bottom, right);
    }
    else if (rows > 1) {
      composition(top, left, top + (rows - 1) / 2, right);
      composition(top + (rows + 1) / 2, left, bottom, right);
    }
    else {
      composition(top, left, bottom, left + (columns - 1) / 2);
      composition(top, left + (columns + 1) / 2, bottom,  right);
    }
  }
}

int main()
{
  while (true) {
    char format[2];
    scanf("%s", format);
    if (format[0] == '#')
      break;
    int rows, columns;
    scanf("%d %d", &rows, &columns);
    nr_chars = 0;
    if (format[0] == 'B') {
      printf("%c%4d%4d\n", 'D', rows, columns);
      decomposition(rows, columns);
    }
    else {
      composition(0, 0, rows - 1, columns - 1);
      printf("%c%4d%4d\n", 'B', rows, columns);
      for (int r = 0; r < rows; r++)
        for (int c = 0; c < columns; c++)
          bitmap_putchar(static_cast<char>(bitmap[r][c] + '0'));
        if (nr_chars)
          putchar('\n');
    }
  }
  return 0;
}

UVa 10043 - Chainsaw Massacre

Accepted date: 2011-05-23
Ranking (as of 2013-10-26): 80 out of 387
Language: C++

/*
  14.7.3 Chainsaw Massacre
  PC/UVa IDs: 111403/10043, Popularity: B, Success rate: low Level: 3

  To build using Visucal Studio 2008:
    cl -EHsc chainsaw_massacre.cpp
*/

/*
  This is an application of maximum (or largest) empty rectangle problem.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

struct point {
  int x, y;

  point() : x(0), y(0) {}
  point(int _x, int _y) : x(_x), y(_y) {}
  point(const point &p) : x(p.x), y(p.y) {}
  bool operator==(const point& p) const {return x == p.x && y == p.y;}
};

bool left_lower_order(const point& p1, const point& p2)
{
  if (p1.x < p2.x)
    return true;
  else if (p1.x > p2.x)
    return false;
  else if (p1.y < p2.y)
    return true;
  else
    return false;
}

bool upper_order(const point& p1, const point& p2)
{
  return p1.y > p2.y;
}

int maximum_empty_rectangle(int l, int w, vector<point>& points)
{
  if (points.empty())
    return l * w;
  sort(points.begin(), points.end(), left_lower_order);
    // sort the points in leftmost-lowest order
  for (vector<point>::iterator i = points.begin();
    i != points.end(); ) { // remove the duplicate points
    vector<point>::iterator j = i;
    j++;
    if (j != points.end() && *i == *j)
      i = points.erase(i);
    else
      i++;
  }
  int n = points.size();
  // get the maximum gap between the x coordinates
  vector<point>::const_iterator i = points.begin();
  int mgap = i->x;
  for (i++; i != points.end(); i++)
    mgap = max(mgap, i->x - (i - 1)->x);
  mgap = max(mgap, l - (i - 1)->x);
  int maxr = mgap * w;
  sort(points.begin(), points.end(), upper_order);
    // sort the points in descending order of y coordinates
  for (vector<point>::const_iterator i = points.begin();
    i != points.end(); i++) {
    int tl = 0, tr = l;
    vector<point>::const_iterator j = i;
    for (j++; j != points.end(); j++)
      if (j->x > tl && j->x < tr) {
        maxr = max(maxr, (tr - tl) * (i->y - j->y));
        if (j->x > i->x)
          tr = j->x;
        else
          tl = j->x;
      }
    maxr = max(maxr, (tr - tl) * i->y);
  }
  for (vector<point>::const_reverse_iterator i = points.rbegin();
    i != points.rend(); i++) {
    int li = 0, ri = l;
    vector<point>::const_reverse_iterator j = i;
    for (j++; j != points.rend(); j++)
      // since points are sorted in descending order of y coordinates,
      // j->y >= i->y
      if (j->y > i->y) {
        if (j->x > i->x)
          ri = min(ri, j->x);
        else
          li = max(li, j->x);
      }
    maxr = max(maxr, (ri - li) * (w - i->y));
  }
  return maxr;
}

int main(int /* argc */, char** /* argv */)
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int nr_scenarios;
  cin >> nr_scenarios;
  while (nr_scenarios--) {
    vector<point> points;
    int l, w;
    cin >> l >> w;
    while (true) {
      int k;
      cin >> k;
      if (!k) // end of a scenario
        break;
      int x, y, dx = 0, dy = 0;
      cin >> x >> y;
      if (k > 1)
        cin >> dx >> dy;
      for ( ; k; k--, x += dx, y += dy)
        points.push_back(point(x, y));
    }
    cout << maximum_empty_rectangle(l, w, points) << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

Uva 10032 - Tug of War

Accepted date: 2011-03-12
Ranking (as of 2013-10-26): 178 out of 817
Language: C++

Used sort of an incomplete Dynamic Programming to get the candidates of solutions and then Applied backtracking for the candidates.

/*
  8.6.5 Tug of War
  PC/UVa IDs: 110805/10032, Popularity: B, Success rate: low Level: 2

  To build using Visucal Studio 2008:
    cl -EHsc tug_of_war.cpp
*/

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

#ifdef DEBUG
void print_pr_people(int sum_of_weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  for (int i = 1; i <= sum_of_weights; i++)
    if (nr_people[i].first)
      cout << i << '(' << static_cast<unsigned int>(nr_people[i].first) << ' ' <<
        static_cast<unsigned int>(nr_people[i].second) << ") ";
  cout << endl;
}
#endif

int generate_nr_people(int n, const vector<int>& weights,
  vector< pair<unsigned char, unsigned char> >& nr_people)
{
/*
  While calculating each realizable team weight, 
  also record the minimum/maximum number of people whose weights are 
  added up to it.
*/
  int sum_of_weights = 0;
  for (int i = 1; i <= n; i++) {
    int w = weights[i];
    for (int j = sum_of_weights; j; j--)
      if (nr_people[j].first) {
        if (nr_people[j + w].first) {
          nr_people[j + w].first = min(nr_people[j + w].first,
            static_cast<unsigned char>(nr_people[j].first + 1));
          nr_people[j + w].second = max(nr_people[j + w].second,
            static_cast<unsigned char>(nr_people[j].second + 1));
        }
        else {
          nr_people[j + w].first = nr_people[j].first + 1;
          nr_people[j + w].second = nr_people[j].second + 1;
        }
      }
    nr_people[w].first = 1;
    if (!nr_people[w].second)
      nr_people[w].second = 1;
    sum_of_weights += w;
  }
#ifdef DEBUG
  print_pr_people(sum_of_weights, nr_people);
#endif
  return sum_of_weights;
}

bool is_valid_team_weight(int nr_one, int nr_other,
  int one_weight, int other_weight, int nr_weights,
  const vector<int>& weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  if (!nr_weights)
    return false;
  int w = one_weight - weights[nr_weights];
  if (!w) {
    if (nr_one == 1)
      return true;
    else if (nr_other > 1 && other_weight == one_weight)
      return false;
    else return is_valid_team_weight(nr_other, nr_one, other_weight, one_weight,
      nr_weights, weights, nr_people);
  }
  else if (w < 0)
    return is_valid_team_weight(nr_other, nr_one, other_weight, one_weight,
      nr_weights, weights, nr_people);
  else if (nr_people[w].first && nr_one - 1 >= nr_people[w].first &&
    nr_one - 1 <= nr_people[w].second &&
    is_valid_team_weight(nr_one - 1, nr_other, w, other_weight,
      nr_weights - 1, weights, nr_people))
    return true;
  else {
    if (!(w = other_weight - weights[nr_weights]))
      return (nr_other == 1) ? true : false;
    else if (w < 0)
      return false;
    else if (nr_people[w].first && nr_other - 1 >= nr_people[w].first &&
      nr_other - 1 <= nr_people[w].second &&
      is_valid_team_weight(nr_one, nr_other - 1, one_weight, w,
        nr_weights - 1, weights, nr_people))
      return true;
    else
      return false;
  }
}

pair<int, int> find_minimum_team_weight_pair(int n, int sum_of_weights,
  const vector<int>& weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  int nr_one_max = n / 2, nr_other_max = 0; // max. number of people for a team
  if (n & 1)
    nr_other_max = nr_one_max + 1;
  int i = sum_of_weights / 2;
  for ( ; ; i--) {
    int nr_one = nr_people[i].first, nr_other =
      nr_people[sum_of_weights - i].first;
    if (nr_one && nr_other) {
      if (n & 1) {
        if (nr_one < nr_other_max && nr_other < nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people) ||
            is_valid_team_weight(nr_other_max, nr_one_max, i, sum_of_weights - i,
              n, weights, nr_people))
              break;
        }
        else if (nr_one == nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, i,
            sum_of_weights - i, n, weights, nr_people))
            break;
        }
        else if (nr_other == nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people))
            break;
        }
      }
      else {
        if (nr_one <= nr_one_max && nr_other <= nr_one_max) {
          if (is_valid_team_weight(nr_one_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people) ||
            is_valid_team_weight(nr_one_max, nr_one_max, i, sum_of_weights - i,
            n, weights, nr_people))
            break;
        }
      }
    }
  }
  return make_pair(i, sum_of_weights - i);
}

int main(int /* argc */, char** /* argv */)
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int cases; // number of test cases
  cin >> cases;
  while (cases--) {
    int n;
    cin >> n; // number of people
    vector<int> weights(n + 1); // vector of weights
    weights[0] = 0;
    for (int i = 1; i <= n; i++)
      cin >> weights[i];
    if (n < 2)
      cout << "0 " << weights[n] << endl;
    else {
      sort(weights.begin() + 1, weights.end());
      int sum_of_weights = 0;
      for (int i = 1; i <= n; i++)
        sum_of_weights += weights[i];
      vector< pair<unsigned char, unsigned char> >
        nr_people(sum_of_weights + 1, make_pair(0, 0));
        //  nr_peoplei].first/second is the minimum/maximum number of people 
        // whose weights are added up to i, or 0 if no weights are added up to i
      generate_nr_people(n, weights, nr_people);
      pair<int, int> weight_pair =
        find_minimum_team_weight_pair(n, sum_of_weights, weights, nr_people);
      cout << weight_pair.first << ' ' << weight_pair.second << endl;
    }
    if (cases)
      cout << endl;
        // the output of each two consecutive cases will be separated 
        // by a blank line
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 10895 - Matrix Transpose

Accepted date: 2013-10-22
Ranking (as of 2013-10-22): 619 out of 722
Language: C++

/*
  UVa 10895 - Matrix Transpose

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

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

const int nr_non_zero_elements_max = 1000;

struct element {
  int row_;
  int column_;
  int value_;
  bool operator<(const element& e) const {
    if (row_ < e.row_)
      return true;
    else if (row_ > e.row_)
      return false;
    else
      return column_ < e.column_;
  }
} elements[nr_non_zero_elements_max];

int main()
{
  int m, n;
  while (scanf("%d %d", &m, &n) != EOF) {
    int r, c, nr_elements = 0;
    for (r = 1; r <= m; r++) {
      int nc;
      scanf("%d", &nc);
      for (c = 0; c < nc; c++) {
        elements[nr_elements + c].column_ = r;
        scanf("%d", &elements[nr_elements + c].row_);
      }
      for (c = 0; c < nc; c++)
        scanf("%d", &elements[nr_elements + c].value_);
      nr_elements += c;
    }
    sort(elements, elements + nr_elements);
    printf("%d %d\n", n, m); 
    int cs = 0, ce = 0;
    for (r = 1; r <= n; r++) {
      for ( ; elements[ce].row_ == r; ce++)
        ;
      int nc = ce - cs;
      printf("%d", nc);
      for (c = 0; c < nc; c++)
        printf(" %d", elements[cs + c].column_);
      putchar('\n');
      for (c = 0; c < nc; c++) {
        if (c)
          putchar(' ');
        printf("%d", elements[cs + c].value_);
      }
      putchar('\n');
      cs = ce;
    }
  }
  return 0;
}

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