UVa 471 - Magic Numbers

Accepted date: 2014-07-26
Ranking (as of 2014-07-26): 237 out of 1017
Language: C++

/*
  UVa 471 - Magic Numbers

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

#include <iostream>
using namespace std;
 
bool is_digits_repeated(long long n)
{
  unsigned int digits = 0; // i-th bit is '1' if digit of i (0 - 9) exists in n
  do {
    int d = 1 << static_cast<int>(n % 10);
    if (digits & d)
      return true;
    n /= 10;
    digits |= d;
  } while (n);
  return false;
}

int main()
{
  const long long s1_max = 9876543210LL;
  int t;
  cin >> t;
  while (t--) {
    long long N;
    cin >> N;
    for (long long s2 = 1, s2_max = s1_max / N; s2 <= s2_max; s2++)
      if (!is_digits_repeated(s2)) {
        long long s1 = s2 * N;
        if (!is_digits_repeated(s1))
          cout << s1 << " / " << s2 << " = " << N << endl;
      }
    if (t)
      cout << endl;
  }
  return 0;
}

UVa 703 - Triple Ties: The Organizer's Nightmare

Accepted date: 2014-07-24
Ranking (as of 2014-07-24): 260 out of 696
Language: C++

/*
  UVa 703 - Triple Ties: The Organizer's Nightmare

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

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

const int n_max = 100;
int tournaments[n_max + 1][n_max + 1];

struct triple_tie {
  int i_, j_, k_;

  triple_tie(int i, int j, int k) : i_(i), j_(j), k_(k) {}
  bool operator<(const triple_tie& tt) const {
    if (i_ != tt.i_)
      return i_ < tt.i_;
    else if (j_ != tt.j_)
      return j_ < tt.j_;
    else
      return k_ < tt.k_;
  }
};

int get_result(int i, int j)
{
  if (tournaments[i][j] /* > tournaments[j][i] */)
    return 1; // i beats j
  else if (/* tournaments[i][j] < */ tournaments[j][i])
    return -1; // j beats i
  else
    return 0; // draw

}

int main()
{
  int n;
  while (cin >> n) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        cin >> tournaments[i][j];

    vector<triple_tie> triple_ties;
    for (int i = 1; i <= n - 2; i++)
      for (int j = i + 1; j <= n - 1; j++)
        for (int k = j + 1; k <= n; k++) {
          int rij = get_result(i, j), rjk = get_result(j, k),
            rki = get_result(k, i);
          if (rij == 0 && rjk == 0 && rki == 0 || // draws
            rij == 1 && rjk == 1 && rki == 1)
            // i beats j, j beats k, k beats i
            triple_ties.push_back(triple_tie(i, j, k));
          else if (get_result(k, j) == 1 && get_result(j, i) == 1 &&
            get_result(i, k) == 1)
            // k beats j, j beats i, i beats k
            triple_ties.push_back(triple_tie(k, j, i));
        }
    sort(triple_ties.begin(), triple_ties.end());
    cout << triple_ties.size() << endl;
    for (vector<triple_tie>::const_iterator ti = triple_ties.begin(),
      te = triple_ties.end(); ti != te; ++ti)
      cout << ti->i_ << ' ' << ti->j_ << ' ' << ti->k_ << endl;
  }
  return 0;
}

UVa 11565 - Simple Equations

Accepted date: 2014-07-20
Ranking (as of 2014-07-20): 199 out of 757
Language: C++

/*
  UVa 11565 - Simple Equations

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

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

const int ABC_max = 10000;
int nr_factors, factors[ABC_max];

bool satisfy_equation(int A, int B, int C, int x, int y, int& z)
{
  int k = x * y;
  if (!(B % k)) {
    z = B / k;
    if (x != z && y != z && x + y + z == A && x * x + y * y + z * z == C)
      return true;
  }
  return false;
}

bool solve_equation(int A, int B, int C, int& x, int& y, int& z)
{
  int i, j;
  for (i = nr_factors - 1; i > 0; i--) {
    x = -factors[i];
    for (j = i - 1; j >= 0; j--) {
      y = -factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
    for (j = 0; j < i; j++) {
      y = factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
  }
  for (int i = 0; i < nr_factors - 1; i++) {
    x = factors[i];
    for (int j = nr_factors - 1; j > i; j--) {
      y = -factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
    for (int j = i + 1; j < nr_factors; j++) {
      y = factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
  }

  return false;
}

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    nr_factors = 0;
    for (int i = 1, j = static_cast<int>(sqrt(static_cast<double>(B)));
      i <= j; i++)
      if (!(B % i)) {
        factors[nr_factors++] = i;
        if (i < B / i)
          factors[nr_factors++] = B / i;
      }
    sort(factors, factors + nr_factors);
    int x, y, z;
    if (solve_equation(A, B, C, x, y, z))
      printf("%d %d %d\n", x, y, z);
    else
      puts("No solution.");
  }
  return 0;
}

UVa 10858 - Unique Factorization

Accepted date: 2014-07-16
Ranking (as of 2014-07-16): 123 out of 385
Language: C++

/*
  UVa 10858 - Unique Factorization

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

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

void unique_factorization(int m, int n, vector<int>& factors,
  vector< vector<int> >& factorizations)
{
  for (int i = m, j = static_cast<int>(sqrt(static_cast<double>(n)));
    i <= j; i++)
    if (!(n % i)) {
      factors.push_back(i);
      unique_factorization(i, n / i, factors, factorizations);
      factors.pop_back();
    }
  if (!factors.empty()) {
    factorizations.push_back(factors);
    factorizations.back().push_back(n);
  }
}

int main()
{
  while (true) {
    int n;
    cin >> n;
    if (!n)
      break;
    vector<int> factors;
    vector< vector<int> > factorizations;
    unique_factorization(2, n, factors, factorizations);
    cout << factorizations.size() << endl;
    for (size_t i = 0; i < factorizations.size(); i++) {
      const vector<int>& f = factorizations[i];
      for (size_t j = 0; j < f.size(); j++) {
        if (j)
          cout << ' ';
        cout << f[j];
      }
      cout << endl;
    }
  }
  return 0;
}

UVa 732 - Anagrams by Stack

Accepted date: 2014-07-14
Ranking (as of 2014-07-14): 229 out of 615
Language: C++

/*
  UVa 732 - Anagrams by Stack

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

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

void anagram(size_t oi, size_t on, stack<char>& sst, stack<char>& tst,
  vector<char>& wv, const vector<char>& twv, vector<char>& ov)
{
  if (oi == on) {
    if (wv.size() == twv.size()) {
      for (size_t i = 0; i < on; i++) {
        if (i)
          cout << ' ';
        cout << ov[i];
      }
      cout << endl;
    }
  }
  else {
    if (!sst.empty()) {
      char c = sst.top();
      sst.pop();
      tst.push(c);
      ov[oi] = 'i';
      anagram(oi + 1, on, sst, tst, wv, twv, ov);
      sst.push(c);
      tst.pop();
    }
    if (!tst.empty() && tst.top() == twv[wv.size()]) {
      char c = tst.top();
      tst.pop();
      wv.push_back(c);
      ov[oi] = 'o';
      anagram(oi + 1, on, sst, tst, wv, twv, ov);
      tst.push(c);
      wv.pop_back();
    }
  }
}

int main()
{
  string sw, tw;
  while (cin >> sw >> tw) {
    cout << "[\n";
    size_t length = sw.length();
    if (length == tw.length()) {
      stack<char> sst, tst; // source stack, taget stack
      vector<char> wv, twv(length), // word, target word
        ov(length * 2); // vector of operations
      for (size_t i = 0; i < length; i++) {
        sst.push(sw[length - i - 1]);
        twv[i] = tw[i];
      }
      anagram(0, length * 2, sst, tst, wv, twv, ov);
    }
    cout << "]\n";
  }
  return 0;
}

UVa 547 - DDF

Accepted date: 2014-07-14
Ranking (as of 2014-07-14): 14 out of 651
Language: C++

/*
  UVa 547 - DDF

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

#include <algorithm>
#include <cstdio>
#include <cmath>
#ifndef ONLINE_JUDGE
#include <cassert>
#endif
using namespace std;

const int DDF_max = 3000;

struct DDF {
  int nr_seqs_; // number of integers comprising a DDF sequence
  int next_; // next integer of a DDF sequence
} DDFs[DDF_max + 1];

int sum_of_digits(int n)
{
  int s = 0;
  do {
    s += n % 10;
    n /= 10;
  } while (n);
  return s;
}

int sum_of_digits_of_factors(int n)
{
  int s = 0;
  for (int i = 1; i <= static_cast<int>(sqrt(static_cast<double>(n))); i++)
    if (!(n % i)) {
      s += sum_of_digits(i);
      if (n / i > i)
        s += sum_of_digits(n / i);
    }
#ifndef ONLINE_JUDGE
  assert(s < 1000);
#endif
  return s;
}

int follow_DDF(int n)
{
  int s = sum_of_digits_of_factors(n);
  DDFs[n].next_ = s;
  if (s == n)
    return 0;
  if (DDFs[s].nr_seqs_)
    DDFs[n].nr_seqs_ = DDFs[s].nr_seqs_ + 1;
  else
    DDFs[n].nr_seqs_ = follow_DDF(s) + 1;
  return DDFs[n].nr_seqs_;
}

void print_DDF(int n)
{
  while (true) {
    printf(" %d", n);
    if (DDFs[n].next_ == n)
      break;
    n = DDFs[n].next_;
  }
  putchar('\n');
}

int main()
{
  for (int i = 1; i <= DDF_max; i++) {
    if (!DDFs[i].nr_seqs_)
      follow_DDF(i);
#ifdef DEBUG
    print_DDF(i);
#endif
  }
  for (int i = 1; ; i++) {
    int m, n;
    if (scanf("%d %d", &m, &n) == EOF)
      break;
    int j_max, nr_seqs_max = -1;
    for (int j = min(m, n), k = max(m, n); j <= k; j++)
      if (DDFs[j].nr_seqs_ > nr_seqs_max) {
        j_max = j;
        nr_seqs_max = DDFs[j].nr_seqs_;
      }
    printf("Input%d: %d %d\n", i, m, n);
    printf("Output%d:", i);
    print_DDF(j_max);
  }
  return 0;
}

UVa 467 - Synching Signals

Accepted date: 2014-07-09
Ranking (as of 2014-07-09): 84 out of 451
Language: C++

/*
  UVa 467 - Synching Signals

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

#include <iostream>
#include <string>
#include <sstream>
#include <cstring>
using namespace std;

const int nr_signals_max = 10, nr_seconds_max = 3600;
int signals[nr_signals_max];
bool seconds[nr_seconds_max + 1];

int main()
{
  for (int ds = 1; ; ds++) {
    string line;
    if (!getline(cin, line))
      break;
    istringstream iss(line);
    int nr_signals = 0, s;
    while (iss >> s)
      signals[nr_signals++] = s;
    memset(seconds, 0, sizeof(seconds));
    for (int i = 0; i < nr_signals; i++) {
      int c = signals[i] * 2, g = signals[i] - 5;
      for (s = c; s <= nr_seconds_max; s += c)
        for (int j = s; j < s + g && j <= nr_seconds_max; j++)
          seconds[j] = true;
    }
    for (s = 0; s <= nr_seconds_max; s++)
      if (seconds[s]) {
        int i;
        for (i = 0; i < nr_signals; i++) {
          int j = s / signals[i];
          if (!(j & 1) && s >= signals[i] * j &&
            s < signals[i] * (j + 1) - 5)
            ;
          else
            break;
        }
        if (i == nr_signals)
          break;
      }
    if (s <= nr_seconds_max)
      cout << "Set " << ds << " synchs again at " <<
        s / 60 << " minute(s) and " << s % 60 <<
          " second(s) after all turning green.\n";
    else
      cout << "Set " << ds << "is unable to synch after one hour.\n";
  }
  return 0;
}

UVa 758 - The Same Game

Accepted date: 2014-07-08
Ranking (as of 2014-07-08): 48 out of 181
Language: C++

/*
  UVa 758 - The Same Game

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_758_The_Same_Game.cpp

  This problem is similar to UVa 339 - SameGame Simulation.
*/

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

const int nr_rows = 10, nr_columns = 15;
char board[nr_rows][nr_columns + 1];
bool visited[nr_rows][nr_columns];

struct cluster {
  int sr_, sc_; // start row and column
  int nr_balls_; // number of balls

  bool operator<(const cluster& c) const {
    if (nr_balls_ != c.nr_balls_)
      return nr_balls_ > c.nr_balls_;
    else if (sc_ != c.sc_)
      return sc_ < c.sc_;
    else
      return sr_ < c.sr_;
  }
} clusters[nr_rows * nr_columns];

int bfs(int sr, int sc, bool remove)
{
  const int nr_dirs = 4;
  const pair<int, int> dirs[nr_dirs] =
    {make_pair(-1, 0), make_pair(1, 0), make_pair(0, 1), make_pair(0, -1)};
  char b = board[sr][sc];
  int nr_removed = 0;
  queue< pair<int, int> > q;
  if (remove)
    board[sr][sc] = 0;
  else
    visited[sr][sc] = true;
  q.push(make_pair(sr, sc));
  while (!q.empty()) {
    pair<int, int> i = q.front();
    q.pop();
    for (int j = 0; j < nr_dirs; j++) {
      int r = i.first + dirs[j].first, c = i.second + dirs[j].second;
      if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns &&
        board[r][c] == b &&
        (remove && board[r][c] || !remove && !visited[r][c])) {
        nr_removed++;
        if (remove)
          board[r][c] = 0;
        else
          visited[r][c] = true;
        q.push(make_pair(r, c));
      }
    }
  }
  if (nr_removed)
    return nr_removed + 1;
  else
    return 0;
}

void remove_balls()
{
  for (int j = 0; j < nr_columns; j++) { // remove cells for each column
    for (int i = 0, k = 1; k < nr_rows; ) {
      if (board[i][j]) {
        if (++i == k)
          k++;
      }
      else {
        for ( ; k < nr_rows; k++)
          if (board[k][j])
            break;
        if (k < nr_rows) {
          board[i][j] = board[k][j];
          board[k][j] = 0;
          i++; k++;
        }
      }
    }
  }
  for (int j = 0, k = 1; k < nr_columns; ) { // remove columns
    if (board[0][j]) {
      if (++j == k)
        k++;
    }
    else {
      for ( ; k < nr_columns; k++)
        if (board[0][k])
          break;
      if (k < nr_columns) {
        for (int i = 0; i < nr_rows; i++) {
          board[i][j] = board[i][k];
          board[i][k] = 0;
        }
        j++; k++;
      }
    }
  }
}

int main()
{
  int ng;
  scanf("%d", &ng);
  for (int g = 1; g <= ng; g++) {
    for (int i = nr_rows - 1; i >= 0; i--)
      scanf("%s", &board[i]);
    printf("Game %d:\n\n", g);
    int score = 0, nr_balls = nr_rows * nr_columns;
    for (int m = 1; ; m++) {
      int nr_clusters = 0;
      memset(visited, 0, sizeof(visited));
      for (int j = 0; j < nr_columns; j++)
        for (int i = 0; i < nr_rows; i++)
          if (board[i][j] && !visited[i][j] &&
            (clusters[nr_clusters].nr_balls_ = bfs(i, j, false)) != 0) {
            clusters[nr_clusters].sr_ = i; clusters[nr_clusters].sc_ = j;
            nr_clusters++;
          }
      if (!nr_clusters)
        break;
      sort(clusters, clusters + nr_clusters);
      int sr = clusters[0].sr_, sc = clusters[0].sc_;
      char b = board[sr][sc];
      int nr = bfs(sr, sc, true), s = (nr - 2) * (nr - 2);
     printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
        m, sr + 1, sc + 1, nr, b, s);
      remove_balls();
      nr_balls -= nr; score += s;
    }
    if (!nr_balls)
      score += 1000;
    printf("Final score: %d, with %d balls remaining.\n", score, nr_balls);
    if (g < ng)
      putchar('\n');
  }
  return 0;
}

UVa 220 - Othello

Accepted date: 2014-07-06
Ranking (as of 2014-07-08): 467 out of 503

Re-judged and accepted date: 2016-02-07
Run Time: 0.000
Ranking (as of 2016-02-07): 392 out of 586

Language: C++

/*
  UVa 220 - Othello

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

#include <cstdio>

const int nr_squares = 8;
char board[nr_squares][nr_squares + 1];

bool is_other_disk(char disk, int r, int c)
{
  if (r < 0 || r >= nr_squares || c < 0 || c >= nr_squares)
    return false;
  return board[r][c] != '-' && disk != board[r][c];
}

bool is_leagal_move(char disk, int r, int c)
{
  if (is_other_disk(disk, r - 1, c)) // above squares
    for (int i = r - 2; i >= 0; i--) {
      if (board[i][c] == disk)
        return true;
      else if (board[i][c] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c)) // below squares
    for (int i = r + 2; i < nr_squares; i++) {
      if (board[i][c] == disk)
        return true;
      else if (board[i][c] == '-')
        break;
    }
  if (is_other_disk(disk, r, c - 1)) // left squares
    for (int j = c - 2; j >= 0; j--) {
      if (board[r][j] == disk)
        return true;
      else if (board[r][j] == '-')
        break;
    }
  if (is_other_disk(disk, r, c + 1)) // rigtht squares
    for (int j = c + 2; j < nr_squares; j++) {
      if (board[r][j] == disk)
        return true;
      else if (board[r][j] == '-')
        break;
    }
  if (is_other_disk(disk, r - 1, c - 1)) // diagonally upper left squares
    for (int i = r - 2, j = c - 2; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == disk)
        return true;
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c - 1)) // diagonally lower left squares
    for (int i = r + 2, j = c - 2; i < nr_squares && j >= 0; i++, j--) {
      if (board[i][j] == disk)
        return true;
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r - 1, c + 1)) // diagonally upper rigtht squares
    for (int i = r - 2, j = c + 2; i >= 0 && j < nr_squares; i--, j++) {
      if (board[i][j] == disk)
        return true;
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c + 1)) // diagonally lower right squares
    for (int i = r + 2, j = c + 2; i < nr_squares && j < nr_squares; i++, j++) {
      if (board[i][j] == disk)
        return true;
      else if (board[i][j] == '-')
        break;
    }
  return false;
}

bool print_leagal_moves(char disk)
{
  bool leagal = false;
  for (int r = 0; r < nr_squares; r++)
    for (int c = 0; c < nr_squares; c++)
      if (board[r][c] == '-' && is_leagal_move(disk, r, c)) {
        if (leagal)
          putchar(' ');
        leagal = true;
        printf("(%d,%d)", r + 1, c + 1);
      }
  if (leagal)
    putchar('\n');
  else
    puts("No legal move.");
  return leagal;
}

void move(char disk, int r, int c, int& nr_white, int& nr_black)
{
  board[r][c] = disk;
  int nr_changed = 0;
  if (is_other_disk(disk, r - 1, c)) // above squares
    for (int i = r - 2; i >= 0; i--) {
      if (board[i][c] == disk) {
        for (i++; i < r; i++, nr_changed++)
          board[i][c] = disk;
        break;
      }
      else if (board[i][c] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c)) // below squares
    for (int i = r + 2; i < nr_squares; i++) {
      if (board[i][c] == disk) {
        for (i--; i > r; i--, nr_changed++)
          board[i][c] = disk;
        break;
      }
      else if (board[i][c] == '-')
        break;
    }
  if (is_other_disk(disk, r, c - 1)) // left squares
    for (int j = c - 2; j >= 0; j--) {
      if (board[r][j] == disk) {
        for (j++; j < c; j++, nr_changed++)
          board[r][j] = disk;
        break;
      }
      else if (board[r][j] == '-')
        break;
    }
  if (is_other_disk(disk, r, c + 1)) // rigtht squares
    for (int j = c + 2; j < nr_squares; j++) {
      if (board[r][j] == disk) {
        for (j--; j > c; j--, nr_changed++)
          board[r][j] = disk;
        break;
      }
      else if (board[r][j] == '-')
        break;
    }
  if (is_other_disk(disk, r - 1, c - 1)) // diagonally upper left squares
    for (int i = r - 2, j = c - 2; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == disk) {
        for (i++, j++; i < r && j < c; i++, j++, nr_changed++)
          board[i][j] = disk;
        break;
      }
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c - 1)) // diagonally lower left squares
    for (int i = r + 2, j = c - 2; i < nr_squares && j >= 0; i++, j--) {
      if (board[i][j] == disk) {
        for (i--, j++; i > r && j < c; i--, j++, nr_changed++)
          board[i][j] = disk;
        break;
      }
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r - 1, c + 1)) // diagonally upper rigtht squares
    for (int i = r - 2, j = c + 2; i >= 0 && j < nr_squares; i--, j++) {
      if (board[i][j] == disk) {
        for (i++, j--; i < r && j > c; i++, j--, nr_changed++)
          board[i][j] = disk;
        break;
      }
      else if (board[i][j] == '-')
        break;
    }
  if (is_other_disk(disk, r + 1, c + 1)) // diagonally lower right squares
    for (int i = r + 2, j = c + 2; i < nr_squares && j < nr_squares; i++, j++) {
      if (board[i][j] == disk) {
        for (i--, j--; i > r && j > c; i--, j--, nr_changed++)
          board[i][j] = disk;
        break;
      }
      else if (board[i][j] == '-')
        break;
    }

  if (disk == 'W') {
    nr_white += nr_changed + 1; nr_black -= nr_changed;
  }
  else {
    nr_white -= nr_changed; nr_black += nr_changed + 1;
  }
}

int main()
{
  int nr_games;
  scanf("%d", &nr_games);
  while (nr_games--) {
    for (int i = 0; i < nr_squares; i++)
      scanf("%s", board[i]);
    int nr_white = 0, nr_black = 0;
    for (int r = 0; r < nr_squares; r++)
      for (int c = 0; c < nr_squares; c++) {
        if (board[r][c] == 'W')
          nr_white++;
        else if (board[r][c] == 'B')
          nr_black++;
      }
    char command[4];
    scanf("%s", command);
    char disk = command[0];
    bool quit = false;
    while (!quit) {
      scanf("%s", command);
      switch (command[0]) {
      case 'L':
        if (!print_leagal_moves(disk))
          disk = (disk == 'W') ? 'B' : 'W';
        break;
      case 'M':
        move(disk, command[1] - '1', command[2] - '1', nr_white, nr_black);
        printf("Black - %2d White - %2d\n", nr_black, nr_white);
        disk = (disk == 'W') ? 'B' : 'W';
        break;
      default:
        quit = true;
        for (int i = 0; i < nr_squares; i++)
          puts(board[i]);
        break;
      }
    }
    if (nr_games)
      putchar('\n');
  }
  return 0;
}

UVa 10855 - Rotated square

Accepted date: 2014-07-04
Ranking (as of 2014-07-04): 97 out of 689
Language: C++

/*
  UVa 10855 - Rotated square

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

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

void rotate_square(const vector< vector<char> >& s,
  vector< vector<char> >& t) // rotate clockwise by 90 degrees
{
  size_t n = s.size();
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < n; j++)
      t[i][j] = s[n - j - 1][i];
#ifdef DEBUG
  for (size_t i = 0; i < n; i++)
    printf("%s\n", &t[i][0]);
#endif
}

int count_squares(const vector< vector<char> >&big_square,
  const vector< vector<char> >&small_square)
{
  int count = 0;
  size_t N = big_square.size(), n = small_square.size();
  for (size_t i = 0; i < N - n + 1; i++)
    for (size_t j = 0; j < N - n + 1; j++) {
      size_t k, l;
      for (k = 0; k < n; k++) {
        for (l = 0; l < n; l++)
          if (big_square[i + k][j + l] != small_square[k][l])
            break;
        if (l < n)
          break;
      }
      if (k == n && l == n)
        count++;
    }
  return count;
}

int main()
{
  while (true) {
    int N, n;
    scanf("%d %d", &N, &n);
    if (!N && !n)
      break;
    vector< vector<char> > big_square(N, vector<char>(N + 1)),
      small_square(n, vector<char>(n + 1));
    for (int i = 0; i < N; i++)
      scanf("%s", &big_square[i][0]);
    for (int i = 0; i < n; i++)
      scanf("%s", &small_square[i][0]);
    int counts[4];
    counts[0] = count_squares(big_square, small_square);
    vector< vector<char> > rotated_square(n, vector<char>(n + 1));
    rotate_square(small_square, rotated_square);
    counts[1] = count_squares(big_square, rotated_square);
    rotate_square(rotated_square, small_square);
    counts[2] = count_squares(big_square, small_square);
    rotate_square(small_square, rotated_square);
    counts[3] = count_squares(big_square, rotated_square);
    printf("%d %d %d %d\n", counts[0], counts[1], counts[2], counts[3]);
  }
  return 0;
}

UVa 10017 - The Never Ending Towers of Hanoi

Accepted date: 2014-07-01
Ranking (as of 2014-07-03): 260 out of 654
Language: C++

/*
  UVa 10017 - The Never Ending Towers of Hanoi

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

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

void print_peg(char p, const list<int>& l)
{
  cout << p << "=>";
  if (!l.empty()) {
    cout << "  ";
    for (list<int>::const_iterator i = l.begin(), e = l.end(); i != e; ++i)
      cout << ' ' << *i;
  }
  cout << endl;
}

void print_pegs(const list<int>& a, const list<int>& b, const list<int>& c)
{
  print_peg('A', a);
  print_peg('B', b);
  print_peg('C', c);
  cout << endl;
}

void move_between_pegs(list<int>& i, list<int>& j)
{
  if (i.empty()) {
    i.push_back(j.back()); j.pop_back();
  }
  else if (j.empty()) {
    j.push_back(i.back()); i.pop_back();
  }
  else if (i.back() > j.back()) {
    i.push_back(j.back()); j.pop_back();
  }
  else {
    j.push_back(i.back()); i.pop_back();
  }
}

void tower_of_hanoi_even_disks(list<int>& a, list<int>& b, list<int>& c, int m)
{
  while (true) {
    if (m--) {
      move_between_pegs(a, b); // make the legal move between pegs A and B
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(a, c); // make the legal move between pegs A and C
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(b, c); // make the legal move between pegs B and C
      print_pegs(a, b, c);
    }
    else
      break;
  }
}

void tower_of_hanoi_odd_disks(list<int>& a, list<int>& b, list<int>& c, int m)
{
  while (true) {
    if (m--) {
      move_between_pegs(a, c); // make the legal move between pegs A and C
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(a, b); // make the legal move between pegs A and B
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(b, c); // make the legal move between pegs C and B
      print_pegs(a, b, c);
    }
    else
      break;
  }
}

int main()
{
  for (int p = 1; ; p++) {
    int n, m;
    cin >> n >> m;
    if (!n && !m)
      break;
    cout << "Problem #" << p << endl << endl;
    list<int> a, b, c;
    for (int i = 1; i <= n; i++)
      a.push_front(i);
    print_pegs(a, b, c);
    if (n & 1)
      tower_of_hanoi_odd_disks(a, b, c, m);
    else
      tower_of_hanoi_even_disks(a, b, c, m);
  }
  return 0;
}

UVa 775 - Hamiltonian Cycle

Accepted date: 2014-06-30
Ranking (as of 2014-07-01): 45 out of 272
Language: C++

/*
  UVa 775 - Hamiltonian Cycle

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

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

const int n_max = 256;

vector<int> edges[n_max + 1];
bool visited[n_max + 1];
int path[n_max + 1];

bool hamiltonian_cycle(int n, int ni, int vi)
{
  if (ni == n) {
    const vector<int>& e = edges[path[ni - 1]];
    for (size_t i = 0; i < e.size(); i++)
      if (e[i] == 1) {
        path[ni] = 1;
        return true;
      }
    return false;
  }
  else {
    const vector<int>& e = edges[vi];
    for (size_t i = 0; i < e.size(); i++)
      if (!visited[e[i]]) {
        path[ni] = e[i];
        visited[e[i]] = true;
        if (hamiltonian_cycle(n, ni + 1, e[i]))
          return true;
        visited[e[i]] = false;
      }
    return false;
  }
}

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    getchar();
    for (int i = 1; i <= n; i++) {
      edges[i].clear();
      visited[i] = false;
    }
    char c;
    while ((c = getchar()) != '%') {
      ungetc(c, stdin);
      int u, v;
      scanf("%d %d", &u, &v);
      edges[u].push_back(v);
      edges[v].push_back(u);
      getchar();
    }
    path[0] = 1;
    visited[1] = true;
    if (hamiltonian_cycle(n, 1, 1)) {
      for (int i = 0; i <= n; i++)
        printf("%d%c", path[i], ((i < n) ? ' ' : '\n'));
    }
    else
      puts("N");
  }
  return 0;
}