UVa 776 - Monkeys in a Regular Forest

Accepted date: 2013-11-18
Ranking (as of 2013-11-18): 147 out of 641
Language: C++

/*
  UVa 776 - Monkeys in a Regular Forest

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

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

void bfs(int nr_rows, int nr_columns, int r, int c, int fn,
  const vector< vector<char> >& forest, vector< vector<int> >& monkeys)
{
  const int nr_dirs = 8;
  const int dirs[nr_dirs][2] =
    {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
  char fc = forest[r][c];
  queue<pair<int, int> > q;
  monkeys[r][c] = fn;
  q.push(make_pair(r, c));
  while (!q.empty()) {
    pair<int, int> rc = q.front();
    q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      r = rc.first + dirs[i][0]; c = rc.second + dirs[i][1];
      if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns &&
        forest[r][c] == fc && !monkeys[r][c]) {
        monkeys[r][c] = fn;
        q.push(make_pair(r, c));
      }
    }
  }
}

int main()
{
  string line;
  while (getline(cin, line)) {
    vector< vector<char> > forest;
    do {
      if (line[0] == '%')
        break;
      forest.push_back(vector<char>());
      istringstream iss(line);
      char c;
      while (iss >> c)
        forest.back().push_back(c);
    } while (getline(cin, line));
    int nr_rows = static_cast<int>(forest.size()),
      nr_columns = static_cast<int>(forest[0].size());
    vector< vector<int> > monkeys(nr_rows, vector<int>(nr_columns, 0));
    for (int r = 0, fn = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        if (!monkeys[r][c])
          bfs(nr_rows, nr_columns, r, c, ++fn, forest, monkeys);
    vector<int> widths(nr_columns, 0);
    for (int c = 0; c < nr_columns; c++) {
      for (int r = 0; r < nr_rows; r++) {
        int fn = monkeys[r][c], w = ((c) ? 1 : 0);
        do {
          fn /= 10;
          w++;
        } while (fn);
        widths[c] = max(widths[c], w);
      }
    }
    cout << setfill(' ');
    for (int r = 0;r < nr_rows; r++) {
      for (int c = 0; c < nr_columns; c++)
        cout << setw(widths[c]) << monkeys[r][c];
      cout << endl;
    }
    cout << "%\n";
  }
  return 0;
}

UVa 296 - Safebreaker

Accepted date: 2013-11-15
Ranking (as of 2013-11-15): 30 out of 639
Language: C++

/*
  UVa 296 - Safebreaker

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

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

const int nr_digits = 4, nr_guesses_max = 10, number_max = 10000;

struct guess {
  char code_[nr_digits + 1];
  int nr_correct_, nr_misplaced_;
};

void get_code(int n, char* code)
{
  for (int i = nr_digits - 1; i >= 0; i--) {
    code[i] = n % 10 + '0';
    n /= 10;
  }
}

bool is_consistent(const char* code, const guess* g)
{
  int nr_correct = 0;
  unsigned char correct = 0;
    // bit i (0 <= i <= 4) is 1 if i-th character is correct
  for (int i = 0, bi = 1; i < nr_digits; i++, bi <<= 1)
    if (code[i] == g->code_[i]) {
      correct |= bi;
      nr_correct++;
    }
  if (nr_correct != g->nr_correct_)
    return false;
  int nr_misplaced = 0;
  unsigned char misplaced = 0;
    // bit i (0 <= i <= 4) is 1 if i-th character is misplaced
  for (int i = 0, bi = 1; i < nr_digits; i++, bi <<= 1)
    if (!(correct & bi)) {
      int j = i + 1;
      if (j == nr_digits)
        j = 0;
      while (j != i) {
        int bj = 1 << j;
        if (!(correct & bj) && !(misplaced & bj) && code[i] == g->code_[j]) {
          misplaced |= bj;
          nr_misplaced++;
          break;
        }
        if (++j == nr_digits)
          j = 0;
      }
    }
  return nr_misplaced == g->nr_misplaced_;
}

int main()
{
  int n;
  cin >> n;
  while (n--) {
    int g;
    cin >> g;
    guess guesses[nr_guesses_max];
    for (int i = 0; i < g; i++) {
      char separator;
      cin >> guesses[i].code_ >> guesses[i].nr_correct_
        >> separator >> guesses[i].nr_misplaced_;
    }
    int nr_consistent = 0;
    char code[nr_digits + 1], secret_code[nr_digits + 1];
    code[nr_digits] = '\0';
    for (int i = 0; i < number_max; i++) {
      get_code(i, code);
      int j;
      for (j = 0; j < g; j++)
        if (!is_consistent(code, &guesses[j]))
          break;
      if (j == g) {
        if (!nr_consistent++)
          strcpy(secret_code, code);
      }
    }
    if (nr_consistent == 1)
      cout << secret_code << endl;
    else if (nr_consistent)
      cout << "indeterminate\n";
    else
      cout << "impossible\n";
  }
  return 0;
}

UVa 10901 - Ferry Loading III

Accepted date: 2013-11-13
Ranking (as of 2013-11-14): 201 out of 669
Language: C++

/*
  UVa 10901 - Ferry Loading III

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

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

const int m_max = 10000;

struct car {
  int at_; // arrival time
  int ut_; // unloaded time
  int ab_; // arrival bank
} cars[m_max];

int cars_at_left_bank[m_max], cars_at_right_bank[m_max];
  // cars_at_left/right_bank[i] is the index to cars[] that arrives at 
  // left/right bank

enum {left, right};

int main()
{
  int c;
  scanf("%d", &c);
  while (c--) {
    int n, t, m;
    scanf("%d %d %d", &n, &t, &m);
    int mlb = 0, mrb = 0; // number of cars that arrives at left/right bank
    for (int i = 0; i < m; i++) {
      char s[8];
      scanf("%d %s", &cars[i].at_, s);
      if (s[0] == 'l') {
        cars[i].ab_ = left;
        cars_at_left_bank[mlb++] = i;
      }
      else {
        cars[i].ab_ = right;
        cars_at_right_bank[mrb++] = i;
      }
    }
    int ft = 0, fb = left;
    for (int ilb = 0, irb = 0; ilb < mlb || irb < mrb; ) {
      int i, b;
      if (ilb < mlb && irb < mrb) {
        int il = cars_at_left_bank[ilb], ir = cars_at_right_bank[irb];
        if (fb == left && cars[il].at_ <= ft)
          i = il;
        else if (fb == right && cars[ir].at_ <= ft)
          i = ir;
        else if (cars[il].at_ < cars[ir].at_)
          i = il;
        else if (cars[il].at_ > cars[ir].at_)
          i = ir;
        else
          i = (fb == left) ? il : ir;
      }
      else if (ilb < mlb)
        i = cars_at_left_bank[ilb];
      else
        i = cars_at_right_bank[irb];
      b = cars[i].ab_;
      if (cars[i].at_ > ft)
        ft += cars[i].at_ - ft;
      if (fb != cars[i].ab_) {
        ft += t;
        fb = cars[i].ab_;
      }
      if (b == left)
        for (int j = 0; ilb < mlb && cars[cars_at_left_bank[ilb]].at_ <= ft
          && j < n; ilb++, j++)
          cars[cars_at_left_bank[ilb]].ut_ = ft + t;
      else
        for (int j = 0; irb < mrb && cars[cars_at_right_bank[irb]].at_ <= ft
          && j < n; irb++, j++)
          cars[cars_at_right_bank[irb]].ut_ = ft + t;
      ft += t;
      fb = (fb == left) ? right : left;
    }
    for (int i = 0; i < m; i++)
      printf("%d\n", cars[i].ut_);
    if (c)
      putchar('\n');
  }
  return 0;
}

UVa 11344 - The Huge One

Accepted date: 2013-11-12
Ranking (as of 2013-11-14): 316 out of 678
Language: C++

/*
  UVa 11344 - The Huge One

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

#include <cstdio>
#include <cstring>

bool is_multiple_of_1(const char* number, int length)
{
  return true;
}

bool is_multiple_of_2(const char* number, int length)
{
  return ((number[length - 1] - '0') % 2) ? false : true;
}

bool is_multiple_of_3(const char* number, int length)
{
  int s = 0;
  for (int i = 0; i < length; i++)
    s += number[i] - '0';
  return (s % 3) ? false : true;
}

bool is_multiple_of_4(const char* number, int length)
{
  int s = number[length - 1] - '0';
  if (length > 1)
    s += (number[length - 2] - '0') * 10;
  return (s % 4) ? false : true;
}

bool is_multiple_of_5(const char* number, int length)
{
  return ((number[length - 1] - '0') % 5) ? false : true;
}

bool is_multiple_of_6(const char* number, int length)
{
  return is_multiple_of_2(number, length) && is_multiple_of_3(number,length);
}

bool is_multiple_of_7(const char* number, int length)
{
  int s = 0;
  for (int i = 0, j = length - 1; j >= 0; i++) {
    int k = number[j--] - '0';
    if (j >= 0)
      k += (number[j--] - '0') * 10;
    if (j >= 0)
      k += (number[j--] - '0') * 100;
    if (i & 1)
      s -= k;
    else
      s += k;
  }
  return (s % 7) ? false : true;
}

bool is_multiple_of_8(const char* number, int length)
{
  int s = number[length - 1] - '0';
  if (length > 1) {
    s += (number[length - 2] - '0') * 10;
    if (length > 2)
      s += (number[length - 3] - '0') * 100;
  }
  return (s % 8) ? false : true;
}

bool is_multiple_of_9(const char* number, int length)
{
  int s = 0;
  for (int i = 0; i < length; i++)
    s += number[i] - '0';
  return (s % 9) ? false : true;
}

bool is_multiple_of_10(const char* number, int length)
{
  return number[length - 1] == '0';
}

bool is_multiple_of_11(const char* number, int length)
{
  int s = 0;
  for (int i = 0, j = length - 1; j >= 0; i++, j--) {
    int k = number[j] - '0';
    if (i & 1)
      s -= k;
    else
      s += k;
  }
  return (s % 11) ? false : true;
}

bool is_multiple_of_12(const char* number, int length)
{
  return is_multiple_of_3(number, length) && is_multiple_of_4(number, length);
}

int main()
{
  typedef bool (*IS_MULTIPLE_OF_N_FUNCTION)(const char* number, int length);
  const IS_MULTIPLE_OF_N_FUNCTION is_multiple_of_n_functions[] = {
    NULL,
    is_multiple_of_1, is_multiple_of_2, is_multiple_of_3,
    is_multiple_of_4, is_multiple_of_5, is_multiple_of_6,
    is_multiple_of_7, is_multiple_of_8, is_multiple_of_9,
    is_multiple_of_10, is_multiple_of_11, is_multiple_of_12
  };

  int N;
  scanf("%d", &N);
  while (N--) {
    const int M_digits_max = 1001;
    char M[M_digits_max + 1];
    scanf("%s", M);
    int length = strlen(M), S;
    scanf("%d", &S);
    bool wonderful = true;
    while (S--) {
      int number;
      scanf("%d", &number);
      if (wonderful && !is_multiple_of_n_functions[number](M, length))
        wonderful = false;
    }
    printf("%s - %s.\n", M, ((wonderful) ? "Wonderful" : "Simple"));
  }
  return 0;
}

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