UVa 11572 - Unique Snowflakes

Accepted date: 2014-05-25
Ranking (as of 2014-05-25): 89 out of 609
Language: C++

/*
  UVa 11572 - Unique Snowflakes

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

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

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int ci = 0, pi = 0, max_sf = 0;
    map<int, int> sf;
    for ( ; ci < n; ci++) {
      int s;
      scanf("%d", &s);
      pair<map<int, int>::iterator, bool> result = sf.insert(make_pair(s, ci));
      if (!result.second) {
        if (result.first->second >= pi) {
          max_sf = max(max_sf, ci - pi);
          pi = result.first->second + 1;
        }
        result.first->second = ci;
      }
    }
    max_sf = max(max_sf, ci - pi);
    printf("%d\n", max_sf);
  }
  return 0;
}

UVa 246 - 10-20-30

Accepted date: 2014-05-24
Ranking (as of 2014-05-24): 95 out of 308
Language: C++

/*
  UVa 246 - 10-20-30

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_246_10-20-30.cpp
*/

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

const int nr_cards = 52, nr_piles = 7;

struct state {
  char cards_[nr_cards + nr_piles + 1 + 1];
  bool operator<(const state& s) const {return strcmp(cards_, s.cards_) < 0;}
};

void play(deque<int>& pile, deque<int>& cards)
{
  pile.push_back(cards.front()); cards.pop_front();
  while (true) {
    size_t s = pile.size();
    if (s < 3)
      break;
    if (!((pile[0] + pile[1] + pile[s - 1]) % 10)) {
      // the first two and last one
      cards.push_back(pile[0]);
      cards.push_back(pile[1]);
      cards.push_back(pile[s - 1]);
      pile.pop_front();
      pile.pop_front();
      pile.pop_back();
    }
    else if (!((pile[0] + pile[s - 2] + pile[s - 1]) % 10)) {
      // the first one and the last two
      cards.push_back(pile[0]);
      cards.push_back(pile[s - 2]);
      cards.push_back(pile[s - 1]);
      pile.pop_front();
      pile.pop_back();
      pile.pop_back();
    }
    else if (!((pile[s - 3] + pile[s - 2] + pile[s - 1]) % 10)) {
      // the last three cards
      cards.push_back(pile[s - 3]);
      cards.push_back(pile[s - 2]);
      cards.push_back(pile[s - 1]);
      pile.pop_back();
      pile.pop_back();
      pile.pop_back();
    }
    else
      break;
  }
}

int insert_state(const deque<int> piles[], const deque<int>& cards,
  set<state>& states)
{
  if (cards.empty())
    return 1; // loose
  state s;
  int si = 0;
  bool win = true;
  for (int pi = 0; pi < nr_piles; pi++) {
    const deque<int>& p = piles[pi];
    if (!p.empty()) {
      win = false;
      for (size_t ci = 0, ce = p.size(); ci < ce; ci++, si++)
        s.cards_[si] = p[ci] + '0';
    }
    s.cards_[si++] = '0'; // terminator
  }
  if (win)
    return 2; // win
  for (size_t ci = 0, ce = cards.size(); ci < ce; ci++, si++)
    s.cards_[si] = cards[ci] + '0';
  s.cards_[si++] = '0'; // terminator
  s.cards_[si] = '\0';
  pair<set<state>::iterator, bool> result = states.insert(s);
  return (result.second) ? -1 : 0 /* draw */;
}

int main()
{
  while (true) {
    int c;
    cin >> c;
    if (!c)
      break;
    deque<int> cards;
    deque<int> piles[nr_piles];
    piles[0].push_back(c);
    int i;
    for (i = 1; i < nr_piles; i++) {
      cin >> c;
      piles[i].push_back(c);
    }
    for ( ; i < nr_cards; i++) {
      cin >> c;
      cards.push_back(c);
    }
    int nr_dealt = nr_piles, pi = 0, npi, result;
    set<state> states;
    insert_state(piles, cards, states);
    while (true) {
      nr_dealt++;
      play(piles[pi], cards);
      if ((result = insert_state(piles, cards, states)) != -1)
        break;
      for (pi = (pi + 1) % nr_piles; piles[pi].empty(); pi = (pi + 1) % nr_piles)
        ; // locate the next pile where the next card will be played
    }
    switch (result) {
    case 0:
      cout << "Draw: "; break;
    case 1:
      cout << "Loss: "; break;
    case 2:
      cout << "Win : "; break;
    }
    cout << nr_dealt << endl;
  }
  return 0;
}

UVa 10588 - Queuing at the doctors

Accepted date: 2014-05-23
Ranking (as of 2014-05-24): 38 out of 85
Language: C++

/*
  UVa 10588 - Queuing at the doctors

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

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

const int n_max = 1000, m_max = 1000;

struct member { // ICORE member
  int t_; // arrival time
  int k_; // number of doctor's offices to visit
  int ki_; // next doctor's office to visit
  vector<int> offices_; // doctor's offices to visit
} members[n_max];

struct visitor_comparator {
  bool operator() (const int& i, const int& j) {
    const member& mi = members[i]; const member& mj = members[j];
    // in ascending order of arrival time or 
    // in ascending order of member's number
    if (mi.t_ > mj.t_)
      return true;
    else if (mi.t_ < mj.t_)
      return false;
    else
      return i > j;
  }
};

priority_queue<int, vector<int>, visitor_comparator> arrivals, leaves;
priority_queue<int, vector<int>, visitor_comparator> offices[m_max];
  // offices[i] is the queue at the i-th doctor's office, 
  // items of which are indices to members[i]

int main()
{
  int c;
  cin >> c;
  while (c--) {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
      member& m = members[i];
      cin >> m.t_ >> m.k_;
      m.ki_ = 0;
      m.offices_.resize(m.k_);
      for (int j = 0; j < m.k_; j++) {
        cin >> m.offices_[j];
        m.offices_[j]--;
      }
      arrivals.push(i);
    }
    int t = 0;
    size_t remained = arrivals.size();
    while (true) {
      while (!arrivals.empty()) {
        int i = arrivals.top();
        member& m = members[i];
        if (m.t_ < t)
          break;
        arrivals.pop();
        if (m.ki_ < m.k_)
          offices[m.offices_[m.ki_++]].push(i);
        else
          leaves.push(i);
      }
      for (int i = 0; i < m; i++) {
        priority_queue<int, vector<int>, visitor_comparator>& office =
          offices[i];
        if (!office.empty()) {
          int j = office.top();
          member& m = members[j];
          if (m.t_ <= t) {
            office.pop();
            m.t_ = t + 1;
            if (m.ki_ < m.k_)
              offices[m.offices_[m.ki_++]].push(j);
            else
              leaves.push(j);
          }
        }
      }
      while (!leaves.empty()) {
        int i = leaves.top();
        member& m = members[i];
        if (m.t_ > t)
          break;
        leaves.pop();
        remained--;
      }
      if (!remained)
        break;
      t++;
    }
    cout << t << endl;
  }
  return 0;
}

UVa 11228 - Transportation system

Accepted date: 2014-05-20
Ranking (as of 2014-05-20): 21 out of 817
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 11228 - Transportation system

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

#include <iostream>
#include <iomanip>
#include <limits>
#include <utility>
#include <cstdlib>
#include <cmath>
using namespace std;

#ifdef  __cplusplus
extern "C" {
#endif

/** priority data type */
typedef double 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

const int n_max = 1000;
pair<double, double> cities[n_max];
double city_distances[n_max][n_max];
  // city_distances[i][j] is the distnace between city i and city j

struct vertex_distance
{
  int vertex; // vertex
  double distance; // distance
  size_t pqueue_pos; // used internally by libpqueue

  vertex_distance() : vertex(0), distance(0.0), pqueue_pos(-1) {}
  vertex_distance(int v, double d) : vertex(v), distance(d), pqueue_pos(-1) {}

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

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

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

int vertex_distance::compare_distance(double next, double 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;
}

int mst_prim(int n, int r, double& road_distance, double& railroad_distance)
{
  for (int i = 0; i < n; i++)
    vertex_distances[i] = vertex_distance(i,
      ((i) ? numeric_limits<double>::max() : 0.0));
  // queue items (vertex_distance instances) are arranged 
  // in ascending order of their distances from the first vertex
  pqueue_t* queue = pqueue_init(n,
    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 < n; i++)
    pqueue_insert(queue, &vertex_distances[i]);

  road_distance = railroad_distance = 0.0;
  int nr_states = 1;
  while (pqueue_size(queue)) {
    vertex_distance* vd = reinterpret_cast<vertex_distance*>(pqueue_pop(queue));
    vd->pqueue_pos = -1;
    int u = vd->vertex;
    if (vertex_distances[u].distance == numeric_limits<double>::max())
      break;
    if (vertex_distances[u].distance > r) {
      railroad_distance += vertex_distances[u].distance;
      nr_states++;
    }
    else
      road_distance += vertex_distances[u].distance;
    for (int v = 0; v < n; v++) {
      if (vertex_distances[v].pqueue_pos != -1 &&
        // a vertex_distance instance for v is still in queue
        city_distances[u][v] < vertex_distances[v].distance)
        pqueue_change_priority(queue,
          city_distances[u][v], &vertex_distances[v]);
    }
  }
  pqueue_free(queue);
  return nr_states;
}

double euclidean_distance(const pair<double, double>& p,
  const pair<double, double>& q)
{
  double dx = p.first - q.first, dy = p.second - q.second;
  return sqrt(dx * dx + dy * dy);
}

int main()
{
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    int n, r;
    cin >> n >> r;
    for (int i = 0; i < n; i++)
      cin >> cities[i].first >> cities[i].second;
    for (int i = 0; i < n; i++) {
      city_distances[i][i] = numeric_limits<double>::max();
      for (int j = i + 1; j < n; j++)
        city_distances[i][j] = city_distances[j][i] =
          euclidean_distance(cities[i], cities[j]);
    }
    double road_distance, railroad_distance;
    int nr_states = mst_prim(n, r, road_distance, railroad_distance);
    cout << "Case #" << t << ": " << nr_states << ' ' <<
      fixed << setprecision(0) << road_distance << ' ' <<
      setprecision(0) << railroad_distance << endl;
  }
  return 0;
}