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