UVa 10719 - Quotient Polynomial

Accepted date: 2012-02-25
Ranking (as of 2013-06-08): 366 out of 1072
Language: C++

/*
  UVa 10719 - Quotient Polynomial

  To build using Visual Studio 2008:
    cl -EHsc -O2 quotient_polynomial.cpp
*/

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

const int n_max = 10000;
int a[n_max + 1];

int main()
{
  string line;
  istringstream iss;
  while (getline(cin, line)) {
    iss.str(line);
    int k;
    iss >> k;
    iss.clear();
    getline(cin, line);
    iss.str(line);
    int n = 0;
    while (iss >> a[n])
      n++;
    iss.clear();
    if (n == 1) {
      cout << "q(x):\nr = " << a[0] << endl << endl;
    }
    else {
      int b = a[0];
      cout << "q(x): " << b;
      for (int i = 1; i < n - 1; i++) {
        b = a[i] + k * b;
        cout << ' ' << b;
      }
      cout << endl;
      cout << "r = " << a[n - 1] + k * b << endl << endl;
    }
  }
  return 0;
}

UVa 11111 - Generalized Matrioshkas

Accepted date: 2012-03-10
Ranking (as of 2013-06-08): 518 out of 920
Language: C++

/*
  UVa 11111 - Generalized Matrioshkas

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

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <utility>
#include <cstdlib>
using namespace std;

int main(int /* argc */, char** /* argv */)
{
  string line;
  while (getline(cin, line)) {
    istringstream iss(line);
    stack< pair<int, int> > st;
      // first is the original capacity, second is the remaining capacity
    bool toys = false, valid = true;
    int n;
    while (iss >> n && valid) {
      toys = true;
      if (n < 0) { // start of a new toy
        n = labs(n);
        if (!st.empty()) {
          if (st.top().second <= n)
            valid = false;
          else
            st.top().second -= n;
        }
        st.push(make_pair(n, n));
      }
      else { // end of the toy
        if (st.empty() || st.top().first != n)
          valid = false;
        else
          st.pop();
      }
    }
    if (!toys || !st.empty())
      valid = false;
    cout << ((valid) ? ":-) Matrioshka!\n" : ":-( Try again.\n");
  }
  return 0;
}

UVa 699 - The Falling Leaves

Accepted date: 2012-03-13
Ranking (as of 2013-06-08): 444 out of 1351
Language: C++

/*
  UVa 699 - The Falling Leaves

  To build using Visual Studio 2008:
    cl -EHsc -O2 the_falling_leaves.cpp
*/

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

struct Tree
{
  int nr_leaves_;
  int pos_;
  Tree* left_;
  Tree* right_;
  Tree(int nr_leaves, int pos) :
    nr_leaves_(nr_leaves), pos_(pos), left_(NULL), right_(NULL) {}
  ~Tree() {delete left_; delete right_;}
};

void build_tree(Tree* t, int& min_pos, int& max_pos)
{
  min_pos = min(min_pos, t->pos_);
  max_pos = max(max_pos, t->pos_);
  int nr_leaves;
  cin >> nr_leaves;
  if (nr_leaves != -1) {
    t->left_ = new Tree(nr_leaves, t->pos_ - 1);
    build_tree(t->left_, min_pos, max_pos);
  }
  cin >> nr_leaves;
  if (nr_leaves != -1) {
    t->right_ = new Tree(nr_leaves, t->pos_ + 1);
    build_tree(t->right_, min_pos, max_pos);
  }
}

void collect_leaves(Tree* t, int pos, vector<int>& piles)
{
  piles[pos + t->pos_] += t->nr_leaves_;
  if (t->left_)
    collect_leaves(t->left_, pos, piles);
  if (t->right_)
    collect_leaves(t->right_, pos, piles);
}

int main()
{
  for (int c = 1; ; c++) {
    int min_pos = 0, max_pos = 0;
    int nr_leaves;
    cin >> nr_leaves;
    if (nr_leaves == -1)
      break;
    Tree* root = new Tree(nr_leaves, 0);
    build_tree(root, min_pos, max_pos);
    vector<int> piles(max_pos - min_pos + 1, 0);
    collect_leaves(root, -min_pos, piles);
    delete root;
    cout << "Case " << c << ":\n";
    for (size_t i = 0, e = piles.size(); i < e; i++)
      cout << piles[i] << ((i == e - 1) ? '\n' : ' ');
    cout << endl;
  }
  return 0;
}

UVa 839 - Not so Mobile

Accepted date: 2012-03-15
Ranking (as of 2013-06-08): 384 out of 1166
Language: C++

/*
  UVa 839 - Not so Mobile

  To build using Visual Studio 2008:
    cl -EHsc -O2 not_so_mobile.cpp
*/

#include <iostream>
using namespace std;

struct Tree
{
  int left_distance_, right_distance_;
  int left_weight_, right_weight_;
  Tree* left_;
  Tree* right_;
  Tree(int left_distance, int right_distance, int left_weight, int right_weight)
    : left_distance_(left_distance), right_distance_(right_distance),
    left_weight_(left_weight), right_weight_(right_weight), left_(NULL),
    right_(NULL) {}
  ~Tree() {delete left_; delete right_;}
};

Tree* build_tree()
{
  int left_distance, right_distance, left_weight, right_weight;
  cin >> left_weight >> left_distance >> right_weight >>
    right_distance;
  Tree* t = new Tree(left_distance, right_distance, left_weight, right_weight);
  if (!left_weight)
    t->left_ = build_tree();
  if (!right_weight)
    t->right_ = build_tree();
  return t;
}

int calculate_tree_weight(Tree* t)
{
  if (t->left_ && (t->left_weight_ = calculate_tree_weight(t->left_)) == -1)
    return -1;
  if (t->right_ && (t->right_weight_ = calculate_tree_weight(t->right_)) == -1)
    return -1;
  return (t->left_weight_ * t->left_distance_ ==
    t->right_weight_ * t->right_distance_) ?
    t->left_weight_ + t->right_weight_ : -1;
}

int main()
{
  int nr_cases;
  cin >> nr_cases;
  while (nr_cases--) {
    Tree* root = build_tree();
    cout << ((calculate_tree_weight(root) == -1) ? "NO\n" : "YES\n");
    delete root;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 10562 - Undraw the Trees

Accepted date: 2012-03-17
Ranking (as of 2013-06-08): 319 out of 551
Language: C++

/*
  UVa 10562 - Undraw the Trees

  To build using Visual Studio 2008:
    cl -EHsc -O2 undraw_the_trees.cpp
*/

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

const int nr_lines_max = 200, nr_chrs_max = 200;
string prof_tree[nr_lines_max + 1];

void print_tree(int nr_lines, int i, int j)
{
  if (i == nr_lines)
    cout << "()";
  else {
    const string& pt = prof_tree[i];
    if (j >= pt.length())
      cout << "()";
    else if (pt[j] == ' ')
      cout << "()";
    else if (pt[j] == '|')
      print_tree(nr_lines, i + 1, j);
    else if (pt[j] == '-') {
      while (j && pt[j - 1] == '-')
        j--;
      cout << '(';
      for ( ; pt[j] == '-'; j++) {
        if (j < prof_tree[i + 1].length() && prof_tree[i + 1][j] != ' ')
          print_tree(nr_lines, i + 1, j);
      }
      cout << ')';
    }
    else {
      cout << pt[j];
      print_tree(nr_lines, i + 1, j);
    }
  }
}

int main()
{
  string s;
  getline(cin, s);
  istringstream iss(s);
  int t;
  iss >> t;
  while (t--) {
    int nr_lines = 0;
    while (true) {
      getline(cin, prof_tree[nr_lines]);
      if (prof_tree[nr_lines][0] == '#')
        break;
      nr_lines++;
    }
    cout << '(';
    if (nr_lines) {
      const string& pt = prof_tree[0];
      for (int j = 0, e = pt.length(); j < e; j++)
        if (pt[j] != ' ') {
          cout << pt[j];
          print_tree(nr_lines, 1, j);
        }
    }
    cout << ")\n";
  }
  return 0;
}

UVa 10557 - XYZZY

Accepted date: 2012-03-21
Ranking (as of 2013-06-08): 287 out of 802
Language: C++

/*
  UVa 10557 - XYZZY

  To build using Visual Studio 20&08:
    cl -EHsc -O2 xyzzy.cpp
*/

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
#include <algorithm>
using namespace std;

bool bfs(int n, int s, int e, const vector< vector<int> >& rooms)
{
  vector<bool> visited(n, false);
  queue<int> q;
  visited[s] = true;
  q.push(s);
  while (!q.empty()) {
    int i = q.front(); q.pop();
    if (i == e)
      return true;
    for (vector<int>::const_iterator j = rooms[i].begin(), k = rooms[i].end();
      j != k; ++j)
      if (!visited[*j]) {
        visited[*j] = true;
        q.push(*j);
      }
  }
  return false;
}

bool bellman_ford(int n,
  const vector<int>& energies, const vector< pair<int, int> >& doors,
  const vector< vector<int> >& rooms)
{
  if (n == 1)
    return true;
  // initialize the graph
  vector<long long> distances(n, numeric_limits<int>::max());
  distances[0] = -100;
  // relax the edges repeatedly
  for (int i = 0; i < n - 1; i++) {
    for (size_t j = 0, e = doors.size(); j < e; j++) {
      const pair<int, int>& d = doors[j];
      if (distances[d.first] + energies[d.first] < min(0LL, distances[d.second]))
        distances[d.second] = distances[d.first] + energies[d.first];
    }
    if (distances[n - 1] < 0)
      return true;
  }
  // check for negative-weight cycles
  for (size_t i = 0, e = doors.size(); i < e; i++) {
    const pair<int, int>& d = doors[i];
    if (distances[d.first] + energies[d.first] < min(0LL, distances[d.second]) &&
      bfs(n, 0, d.first, rooms) && bfs(n, d.second, n - 1, rooms))
        // cycle is reachable both from start and to finish
      return true;
  }
  return false;
}

int main()
{
  while (true) {
    int n;
    cin >> n;
    if (n == -1)
      break;
    vector<int> energies(n); // energies[i] is the energy of i-th room
    vector< pair<int, int> > doors(n);
      // there is a one-way door form doors[].first to doors[].second
    vector< vector<int> > rooms(n);
    for (int i = 0; i < n; i++) {
      int e;
      cin >> e;
      energies[i] = -e;
      int j;
      cin >> j;
      for (int k = 0; k < j; k++) {
        int l;
        cin >> l;
        doors.push_back(make_pair(i, l - 1));
        rooms[i].push_back(l - 1);
      }
    }
    cout << (bellman_ford(n, energies, doors, rooms) ?
      "winnable\n" : "hopeless\n");
  }
  return 0;
}

UVa 10047 - The Monocycle

Accepted date: 2012-03-24
Ranking (as of 2013-06-08): 707 out of 1044
Language: C++

The priority queue implementation (the functions prefixed with "pqueue" and their associated definitions, etc. that are surrounded by the below 'extern "C"' block) is based on the code from https://github.com/vy/libpqueue and is licensed under the Apache 2.0 license:
  Copyright 2010 Volkan Yazici
  Copyright 2006-2010 The Apache Software Foundation

/*
  UVa 10047 - The Monocycle

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

#include <iostream>
#include <vector>
#include <limits>
#include <cstdlib>
using namespace std;

#ifdef  __cplusplus
extern "C" {
#endif

/** priority data type */
typedef int pqueue_pri_t;

/** callback functions to get/set/compare the priority of an element */
typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a);
typedef void (*pqueue_set_pri_f)(void *a, pqueue_pri_t pri);
typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr);

/** callback functions to get/set the position of an element */
typedef size_t (*pqueue_get_pos_f)(void *a);
typedef void (*pqueue_set_pos_f)(void *a, size_t pos);

/** debug callback function to print a entry */
typedef void (*pqueue_print_entry_f)(FILE *out, void *a);

/** the priority queue handle */
typedef struct pqueue_t
{
    size_t size;
    size_t avail;
    size_t step;
    pqueue_cmp_pri_f cmppri;
    pqueue_get_pri_f getpri;
    pqueue_set_pri_f setpri;
    pqueue_get_pos_f getpos;
    pqueue_set_pos_f setpos;
    void **d;
} pqueue_t;

#define left(i)   ((i) << 1)
#define right(i)  (((i) << 1) + 1)
#define parent(i) ((i) >> 1)

pqueue_t *
pqueue_init(size_t n,
            pqueue_cmp_pri_f cmppri,
            pqueue_get_pri_f getpri,
            pqueue_set_pri_f setpri,
            pqueue_get_pos_f getpos,
            pqueue_set_pos_f setpos)
{
    pqueue_t *q;

    if (!(q = (pqueue_t *)malloc(sizeof(pqueue_t))))
        return NULL;

    /* Need to allocate n+1 elements since element 0 isn't used. */
    if (!(q->d = (void **)(malloc((n + 1) * sizeof(void *))))) {
        free(q);
        return NULL;
    }

    q->size = 1;
    q->avail = q->step = (n+1);  /* see comment above about n+1 */
    q->cmppri = cmppri;
    q->setpri = setpri;
    q->getpri = getpri;
    q->getpos = getpos;
    q->setpos = setpos;

    return q;
}

void
pqueue_free(pqueue_t *q)
{
    free(q->d);
    free(q);
}

size_t
pqueue_size(pqueue_t *q)
{
    /* queue element 0 exists but doesn't count since it isn't used. */
    return (q->size - 1);
}

static void
bubble_up(pqueue_t *q, size_t i)
{
    size_t parent_node;
    void *moving_node = q->d[i];
    pqueue_pri_t moving_pri = q->getpri(moving_node);

    for (parent_node = parent(i);
         ((i > 1) && q->cmppri(q->getpri(q->d[parent_node]), moving_pri));
         i = parent_node, parent_node = parent(i))
    {
        q->d[i] = q->d[parent_node];
        q->setpos(q->d[i], i);
    }

    q->d[i] = moving_node;
    q->setpos(moving_node, i);
}

static size_t
maxchild(pqueue_t *q, size_t i)
{
    size_t child_node = left(i);

    if (child_node >= q->size)
        return 0;

    if ((child_node+1) < q->size &&
        q->cmppri(q->getpri(q->d[child_node]), q->getpri(q->d[child_node+1])))
        child_node++; /* use right child instead of left */

    return child_node;
}

static void
percolate_down(pqueue_t *q, size_t i)
{
    size_t child_node;
    void *moving_node = q->d[i];
    pqueue_pri_t moving_pri = q->getpri(moving_node);

    while ((child_node = maxchild(q, i)) &&
           q->cmppri(moving_pri, q->getpri(q->d[child_node])))
    {
        q->d[i] = q->d[child_node];
        q->setpos(q->d[i], i);
        i = child_node;
    }

    q->d[i] = moving_node;
    q->setpos(moving_node, i);
}

int
pqueue_insert(pqueue_t *q, void *d)
{
    void *tmp;
    size_t i;
    size_t newsize;

    if (!q) return 1;

    /* allocate more memory if necessary */
    if (q->size >= q->avail) {
        newsize = q->size + q->step;
        if (!(tmp = realloc(q->d, sizeof(void *) * newsize)))
            return 1;
        q->d = (void **)tmp;
        q->avail = newsize;
    }

    /* insert item */
    i = q->size++;
    q->d[i] = d;
    bubble_up(q, i);

    return 0;
}

void
pqueue_change_priority(pqueue_t *q,
                       pqueue_pri_t new_pri,
                       void *d)
{
    size_t posn;
    pqueue_pri_t old_pri = q->getpri(d);

    q->setpri(d, new_pri);
    posn = q->getpos(d);
    if (q->cmppri(old_pri, new_pri))
        bubble_up(q, posn);
    else
        percolate_down(q, posn);
}

void *
pqueue_pop(pqueue_t *q)
{
    void *head;

    if (!q || q->size == 1)
        return NULL;

    head = q->d[1];
    q->d[1] = q->d[--q->size];
    percolate_down(q, 1);

    return head;
}

#ifdef  __cplusplus
}
#endif

enum {dir_unknown = -1, dir_north, dir_south, dir_west, dir_east};
enum {clr_red, clr_black, clr_green, clr_white, clr_blue};
const int nr_dirs = dir_east - dir_north + 1, nr_colors = clr_blue - clr_red + 1;

struct vertex_distance
{
  int v_; // vertex
  int distance_; // distance
  int direction_, color_;
  size_t pqueue_pos_; // used internally by libpqueue

  vertex_distance() : v_(-1), distance_(-1), pqueue_pos_(-1) {}
  vertex_distance(int v, int distance, int direction, int color)
    : v_(v), distance_(distance), direction_(direction), color_(color),
    pqueue_pos_(-1) {}

  static int get_distance(void* vd);
  static void set_distance(void* vd, int d);
  static int compare_distance(int next, int current);
  static size_t get_position(void* vd);
  static void set_position(void *vd, size_t position);
};

int vertex_distance::get_distance(void* vd)
{
  return reinterpret_cast<vertex_distance*>(vd)->distance_;
}

void vertex_distance::set_distance(void* vd, int d)
{
  reinterpret_cast<vertex_distance*>(vd)->distance_ = d;
}

int vertex_distance::compare_distance(int next, int current)
{
  return current < next;
}

size_t vertex_distance::get_position(void* vd)
{
  return reinterpret_cast<vertex_distance*>(vd)->pqueue_pos_;
}

void vertex_distance::set_position(void *vd, size_t position)
{
  reinterpret_cast<vertex_distance*>(vd)->pqueue_pos_ = position;
}

bool relax_distance(int m, int n, const vector< vector<char> >& squares,
  int next_dir, int di, vector<vertex_distance>& distances, pqueue_t* queue)
{
  int i = di / (n * nr_dirs * nr_colors);
  int j = (di - i * (n * nr_dirs * nr_colors)) / (nr_dirs * nr_colors);
  switch (next_dir) {
  case dir_north:
    i--; break;
  case dir_south:
    i++; break;
  case dir_west:
    j--; break;
  case dir_east:
    j++; break;
  }
  if (i < 0 || i >= m || j < 0 || j >= n || squares[i][j] == '#')
    return false;
  int next_color = (distances[di].color_ + 1) % nr_colors;
  int k = i * (n * nr_dirs * nr_colors) + j * nr_dirs * nr_colors +
    next_dir * nr_colors + next_color;
  if (distances[k].pqueue_pos_ == -1) 
    // an vertex_distance instance is not in the queue
    return false;
  const int ds[nr_dirs][nr_dirs] = {
    {1, 3, 2, 2}, // from north
    {3, 1, 2, 2}, // from south
    {2, 2, 1, 3}, // from east
    {2, 2, 3, 1} // from west
  };
  int d = distances[di].distance_ + ds[distances[di].direction_][next_dir];
  if (d < distances[k].distance_) {
    pqueue_change_priority(queue, d, &distances[k]);
    return true;
  }
  else
    return false;
}

int shortest_path(int m, int n, int start, int end,
  const vector< vector<char> >& squares)
{
  int nr_vertices = m * n * nr_dirs * nr_colors;
  vector<vertex_distance> distances(nr_vertices);
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      for (int d = 0; d < nr_dirs; d++)
        for (int c = 0; c < nr_colors; c++) {
          int l = i * (n * nr_dirs * nr_colors) + j * nr_dirs * nr_colors +
            d * nr_colors + c;
          if (i * n + j == start && d == dir_north && c == clr_green)
            distances[l] = vertex_distance(l, 0, d, c);
          else
            distances[l] = vertex_distance(l, numeric_limits<int>::max(), d, c);
        }
  // queue items (vertex_distance instances) are arranged in ascending order of 
  // their distances from the start vertex
  pqueue_t* queue = pqueue_init(distances.size(),
    vertex_distance::compare_distance, vertex_distance::get_distance,
    vertex_distance::set_distance, vertex_distance::get_position,
    vertex_distance::set_position);
  for (int i = 0; i < nr_vertices; i++)
    pqueue_insert(queue, &distances[i]);
  while (pqueue_size(queue)) {
    vertex_distance* vd = reinterpret_cast<vertex_distance*>(pqueue_pop(queue));
    vd->pqueue_pos_ = -1;
    int i = vd->v_ / (n * nr_dirs * nr_colors);
    int j = (vd->v_ - i * (n * nr_dirs * nr_colors)) / (nr_dirs * nr_colors);
    int d = vd->distance_;
    if (d == numeric_limits<int>::max())
      break;
#ifdef DEBUG
    cout << i << ' ' << j << ' ' << d << endl;
#endif
    if (i * n + j == end && vd->color_ == clr_green)
      return vd->distance_;
    relax_distance(m, n, squares, dir_north, vd->v_, distances, queue);
    relax_distance(m, n, squares, dir_south, vd->v_, distances, queue);
    relax_distance(m, n, squares, dir_west, vd->v_, distances, queue);
    relax_distance(m, n, squares, dir_east, vd->v_, distances, queue);
  }
  return -1;
}

int main()
{
  for (int c = 1; ; c++) {
    int m, n;
    cin >> m >> n;
    if (!m && !n)
      break;
    if (c > 1)
      cout << endl; // print a blank line between two successive test cases
    vector< vector<char> > squares(m, vector<char>(n));
    int s, t;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        cin >> squares[i][j];
        if (squares[i][j] == 'S')
          s = i * n + j;
        else if (squares[i][j] == 'T')
          t = i * n + j;
      }
    int min_path = shortest_path(m, n, s, t, squares);
    cout << "Case #" << c << endl;
    if (min_path == -1)
      cout << "destination not reachable\n";
    else
      cout << "minimum time = " << min_path << " sec\n";
  }
  return 0;
}