UVa 11960 - Divisor Game

Accepted date: 2016-04-30
Run Time: 0.040
Ranking (as of 2016-04-29): 32 out of 462
Language: C++

/*
  UVa 11960 - Divisor Game

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

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

const int N_max = 1000000;
int nr_of_divisors[N_max + 1], most_divisors[N_max + 1];

int main()
{
  for (int i = 1; i <= N_max; i++)
    for (int j = i; j <= N_max; j += i)
      nr_of_divisors[j]++;
  for (int i = 1, most = 0, most_i = 0; i <= N_max; i++) {
    if (most <= nr_of_divisors[i]) {
      most = nr_of_divisors[i];
      most_i = i;
    }
    most_divisors[i] = most_i;
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    printf("%d\n", most_divisors[n]);
  }
  return 0;
}

UVa 1644 - Prime Gap

Accepted date: 2016-04-29
Run Time: 0.000
Ranking (as of 2016-04-29): 9 out of 446
Language: C++

/*
  UVa 1644 - Prime Gap

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

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

const int n_max = 1299709, nr_primes = 100000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int primes[nr_primes];

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

int main()
{
  sieve_of_eratosthenes();
  for (int i = 2, j = 0; i <= n_max; i++)
    if (!not_primes[i])
      primes[j++] = i;
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    int gap = 0;
    if (not_primes[n]) {
      int i = upper_bound(primes, primes + nr_primes, n) - primes;
      gap = primes[i] - primes[i - 1];
    }
    printf("%d\n", gap);
  }
  return 0;
}

UVa 11513 - 9 Puzzle

Accepted date: 2016-04-28
Run Time: 0.270
Ranking (as of 2016-04-28): 29 out of 471
Language: C++

/*
  UVa 11513 - 9 Puzzle

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

#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int nr_squares = 9;
const int nr_paths_max = 362880; // 9!

enum {m_h1, m_h2, m_h3, m_v1, m_v2, m_v3};
const int nr_moves = m_v3 - m_h1 + 1;
const char* original_configuration = "123456789";
const char *moves[] = {"H1", "H2", "H3", "V1", "V2", "V3"};

struct path {
  char squares_[nr_squares];
  int next_;
  int move_;
  int s_;
} paths[nr_paths_max];

int compare_path(const void* i, const void* j)
{
  const path *pi = reinterpret_cast<const path*>(i), *pj = reinterpret_cast<const path*>(j);
  return strcmp(pi->squares_, pj->squares_);
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  char s[nr_squares + 1];
  strcpy(s, original_configuration);
  int nr_paths = 0;
  do {
    strcpy(paths[nr_paths].squares_, s);
    nr_paths++;
  } while (next_permutation(s, s + nr_squares));
#ifdef DEBUG
  printf("%d\n", nr_paths);
#endif
  // starting from the original configuration, mark the reachables configurations 
  // by moving in the reverse directions
  path p;
  strcpy(p.squares_, original_configuration);
  paths[0].next_ = 0, paths[0].s_ = 0;
  for (int i = 1; i < nr_paths_max; i++)
    paths[i].next_ = -1;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int pi = q.front();
    q.pop();
#ifdef DEBUG
//    printf("%d: %s %d\n", pi, paths[pi].squares_, paths[pi].next_);
#endif
    int ns = paths[pi].s_ + 1;
    for (int i = 0; i < nr_moves; i++) {
      int j;
      char c;
      path np;
      strcpy(np.squares_, paths[pi].squares_);
      if (i < m_v1) { // horizontal left moves
        j = i * 3;
        c = np.squares_[j], np.squares_[j] = np.squares_[j + 1],
          np.squares_[j + 1] = np.squares_[j + 2], np.squares_[j + 2] = c;
      }
      else { // vertical down moves
        j = i - m_v1;
        c = np.squares_[6 + j], np.squares_[6 + j] = np.squares_[3 + j],
          np.squares_[3 + j] = np.squares_[j], np.squares_[j] = c;
      }
      int npi = reinterpret_cast<path*>(bsearch (&np, paths, nr_paths_max, sizeof(path), compare_path)) - paths;
      if (paths[npi].next_ == -1) {
#ifdef DEBUG
//        printf("  %d: %s\n", npi, paths[npi].squares_);
#endif
        paths[npi].next_ = pi, paths[npi].move_ = i, paths[npi].s_ = ns;
        q.push(npi);
      }
    }
  }
  while (true) {
    int n, i = 0;
    scanf("%d", &n);
    if (!n)
      break;
    p.squares_[i++] = n + '0';
    for ( ; i < nr_squares; i++) {
      scanf("%d", &n);
      p.squares_[i] = n + '0';
    }
    int pi = reinterpret_cast<path*>(bsearch (&p, paths, nr_paths_max, sizeof(path), compare_path)) - paths;
    if (paths[pi].next_ != -1) {
      printf(((pi) ? "%d " : "%d"), paths[pi].s_);
      for ( ; pi; pi = paths[pi].next_)
        printf("%s", moves[paths[pi].move_]);
      putchar('\n');
    }
    else
      puts("Not solvable");
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 10097 - The Color Game

Accepted date: 2016-04-25
Run Time: 0.030
Ranking (as of 2016-04-25): 3 out of 479
Language: C++

/*
  UVa 10097 - The Color Game

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

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

const int N_max = 100;

int matrix[N_max + 1][N_max + 1], visited[N_max + 1][N_max + 1];

int main()
{
  for (int g = 1; ; g++) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    for (int i = 1; i <= N; i++)
      for (int j= 1; j <= N; j++) {
        int k;
        scanf("%d", &k);
        matrix[i][j] = k;
        visited[i][j] = -1;
      }
    int N1, N2, N3;
    scanf("%d %d %d", &N1, &N2, &N3);
    int min_moves = -1;
    queue< pair<int, int> > q;
    visited[N1][N2] = 0;
    q.push(make_pair(N1, N2));
    while (!q.empty()) {
      pair<int, int> p = q.front();
      q.pop();
      N1 = p.first, N2 = p.second;
      int m = visited[N1][N2];
#ifdef DEBUG
      printf("%d %d %d\n", N1, N2, m);
#endif
      if (N1 == N3 || N2 == N3) {
        min_moves = m;
        break;
      }
      if (N1 != N3) {
        if (matrix[N1][N2] && visited[matrix[N1][N2]][N2] == -1) {
#ifdef DEBUG
          printf("  %d %d %d\n", matrix[N1][N2], N2, m + 1);
#endif
          visited[matrix[N1][N2]][N2] = m + 1;
          q.push(make_pair(matrix[N1][N2], N2));
        }
      }
      if (N2 != N3) {
        if (matrix[N2][N1] && visited[matrix[N2][N1]][N1] == -1) {
#ifdef DEBUG
          printf("    %d %d %d\n", matrix[N2][N1], N1, m + 1);
#endif
          visited[matrix[N2][N1]][N1] = m + 1;
          q.push(make_pair(matrix[N2][N1], N1));
        }
      }
    }
    printf("Game #%d\n", g);
    if (min_moves != -1)
      printf("Minimum Number of Moves = %d\n\n", min_moves);
    else
      printf("Destination is Not Reachable !\n\n");
  }
  return 0;
}

UVa 10269 - Adventure of Super Mario

Accepted date: 2016-04-24
Run Time: 0.000
Ranking (as of 2016-04-24): 6 out of 642
Language: C++

/*
  UVa 10269 - Adventure of Super Mario

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

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

const int A_max = 50, B_max = 50, n_max = A_max + B_max, L_max = 500, K_max = 10;

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

int matrix[n_max + 1][n_max + 1];
bool visited[n_max + 1], dvisited[n_max + 1][K_max + 1];
vector<edge> edges[n_max + 1];
int distances[n_max + 1][K_max + 1];
  // distances[i][j] is the min. time to vertex i using super-runs j times

struct distance_comparator {
  bool operator() (const pair<int, int>& i, const pair<int, int>& j) const
  {
    int di = distances[i.first][i.second], dj = distances[j.first][j.second];
    if (di != dj)
      return di < dj;
    return (i.second != j.second) ? i.second < j.second : i.first < j.first;
  }
};

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int A, B, M, L, K;
    scanf("%d %d %d %d %d", &A, &B, &M, &L, &K);
    int n = A + B;
    for (int i = 1; i <= n; i++) {
      edges[i].clear();
      for (int j = 1; j <= n; j++)
        matrix[i][j] = numeric_limits<int>::max();
      for (int j = 0; j <= K; j++) {
        dvisited[i][j] = false;
        distances[i][j] = numeric_limits<int>::max();
      }
    }
    while (M--) {
      int Xi, Yi, Li;
      scanf("%d %d %d", &Xi, &Yi, &Li);
      matrix[Xi][Yi] = matrix[Yi][Xi] = Li;
      edges[Xi].push_back(edge(Yi, Li));
      edges[Yi].push_back(edge(Xi, Li));
    }

    // apply the Floyd-Warshall algorithm
    for (int k = 1; k <= A; k++)
      for (int i = 1; i <= n; i++)
        if (matrix[i][k] != numeric_limits<int>::max())
          for (int j = 1; j <= n; j++)
          if (matrix[k][j] != numeric_limits<int>::max())
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);

    // add the edges where super-running can be used
    for (int i = 1; i <= n - 1; i++)
      for (int j = i + 1; j <= n; j++)
        if (matrix[i][j] <= L) {
#ifdef DEBUG
          printf("s %d %d %d\n", i, j, matrix[i][j]);
#endif
          edges[i].push_back(edge(j, 0));
          edges[j].push_back(edge(i, 0));
        }

    // apply the Dijkstra's shortest path algorithm
    set<pair<int, int>, distance_comparator> pq; // priority queue
    distances[n][0] = 0;
    pq.insert(make_pair(n, 0));
    int min_t = numeric_limits<int>::max();
    while(!pq.empty()) {
      pair<int, int> p = *pq.begin();
      pq.erase(pq.begin());
      int u = p.first, k = p.second, t = distances[u][k];
      dvisited[u][k] = true;
#ifdef DEBUG
      printf("%d %d %d\n", u, k, t);
#endif
      if (u == 1) {
        min_t = t;
        break;
      }
      const vector<edge>& es = edges[u];
      for (size_t i = 0, j = es.size(); i < j; i++) {
        int v = es[i].v_, w = es[i].w_;
        if (w && !dvisited[v][k] && t + w < distances[v][k]) {
          // a walk edge
          pair<int, int> q = make_pair(v, k);
          pq.erase(q);
          distances[v][k] = t + w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, k, distances[v][k]);
#endif
          pq.insert(q);
        }
        if (!w && k < K && !dvisited[v][k + 1] && t < distances[v][k + 1]) {
          // a super-running edge
          pair<int, int> q = make_pair(v, k + 1);
          pq.erase(q);
          distances[v][k + 1] = t;
#ifdef DEBUG
          printf("  %d %d %d\n", v, k + 1, distances[v][k + 1]);
#endif
          pq.insert(q);
        }
      }
    }
    printf("%d\n", min_t);
  }
  return 0;
}

UVa 11635 - Hotel booking

Accepted date: 2016-04-23
Run Time: 0.430
Ranking (as of 2016-04-23): 23 out of 464
Language: C++

/*
  UVa 11635 - Hotel booking

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

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

const int n_max = 10000, h_max = 100, minutes_max = 10 * 60;

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

bool hotels[n_max + 1], visited[n_max + 1][h_max + 1];
vector<edge> edges[n_max + 1];

struct distance_comparator {
  vector< vector<int> >& distances_;

  distance_comparator(vector< vector<int> >& distances) : distances_(distances) {}
  bool operator() (const pair<int, int>& i, const pair<int, int>& j) const
  {
    if (i.second != j.second)
      return i.second < j.second;
    int di = distances_[i.first][i.second], dj = distances_[j.first][j.second];
    return (di != dj) ? di < dj : i.first < j.first;
  }
};

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    int h;
    scanf("%d", &h);
    for (int i = 1; i <= n; i++) {
      hotels[i] = false;
      edges[i].clear();
      for (int j = 0; j <= h; j++)
        visited[i][j] = false;
    }
    for (int i = 0; i < h; i++) {
      int c;
      scanf("%d", &c);
      hotels[c] = true;
    }
    int m;
    scanf("%d", &m);
    while (m--) {
      int a, b, t;
      scanf("%d %d %d", &a, &b, &t);
      edges[a].push_back(edge(b, t));
      edges[b].push_back(edge(a, t));
    }
    // apply the Dijkstra's shortest path algorithm
    vector< vector<int> > distances(n + 1, vector<int>(h + 1, numeric_limits<int>::max()));
    set<pair<int, int>, distance_comparator> pq(distances); // priority queue
    distances[1][0] = 0;
    pq.insert(make_pair(1, 0));
    int min_d = -1;
    while(!pq.empty()) {
      pair<int, int> p = *pq.begin();
      pq.erase(pq.begin());
      int u = p.first, d = p.second, t = distances[u][d];
      visited[u][d] = true;
#ifdef DEBUG
      printf("%d %d %d\n", u, d, t);
#endif
      if (u == n) {
        min_d = d;
        break;
      }
      const vector<edge>& es = edges[u];
      for (size_t i = 0, j = es.size(); i < j; i++) {
        int v = es[i].v_, w = es[i].w_;
        if (t + w <= minutes_max &&
          !visited[v][d] && t + w < distances[v][d]) {
          pair<int, int> q = make_pair(v, d);
          pq.erase(q);
          distances[v][d] = t + w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, d, distances[v][d]);
#endif
          pq.insert(q);
        }
        if (hotels[u] && d < h && w <= minutes_max &&
          !visited[v][d + 1] && w < distances[v][d + 1]) {
          pair<int, int> q = make_pair(v, d + 1);
          pq.erase(q);
          distances[v][d + 1] = w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, d + 1, distances[v][d + 1]);
#endif
          pq.insert(q);
        }
      }
    }
    printf("%d\n", min_d);
  }
  return 0;
}

UVa 11377 - Airport Setup

Accepted date: 2016-04-21
Run Time: 0.030
Ranking (as of 2016-04-21): 56 out of 531
Language: C++

/*
  UVa 11377 - Airport Setup

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

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

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

struct distance_comparator {
  const vector<int>& distances_;

  distance_comparator(const vector<int>& distances) : distances_(distances) {}
  bool operator() (int i, int j) const
  {
    return (distances_[i] != distances_[j]) ? distances_[i] < distances_[j] : i < j;
  }
};

int dijkstra_shortest_path(int n, int start, int end, const vector< vector<edge> >& edges)
{
  vector<int> distances(n, numeric_limits<int>::max());
  vector<bool> visited(n, false);
  set<int, distance_comparator> pq(distances); // priority queue
  distances[start] = 0;
  pq.insert(start);
  while(!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    if (u == end)
      break;
    int d = distances[u];
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_, w = es[i].w_;
      if (!visited[v] && distances[v] > d + w) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = d + w;
        pq.insert(v);
      }
    }
  }
  return (distances[end] != numeric_limits<int>::max()) ? distances[end] : -1;
}

int main()
{
  int X;
  scanf("%d", &X);
  for (int x = 1; x <= X; x++) {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vector<int> airports(N, 1);
    while (K--) {
      int i;
      scanf("%d", &i);
      airports[i - 1] = 0;
    }
    vector< vector<edge> > edges(N);
    while (M--) {
      int u, v;
      scanf("%d %d", &u, &v);
      u--; v--;
      edges[u].push_back(edge(v, airports[v]));
      edges[v].push_back(edge(u, airports[u]));
    }
    int Q;
    scanf("%d", &Q);
    printf("Case %d:\n", x);
    while (Q--) {
      int x, y;
      scanf("%d %d", &x, &y);
      int d = dijkstra_shortest_path(N, x - 1, y - 1, edges);
      if (d != -1 && x != y)
        d += airports[x - 1];
      printf("%d\n", d);
    }
    putchar('\n');
  }
  return 0;
}

UVa 663 - Sorting Slides

Accepted date: 2016-04-17
Run Time: 0.000
Ranking (as of 2016-04-17): 58 out of 452
Language: C++

/*
  UVa 663 - Sorting Slides

  To build using Visucal Studio 2012:
    cl -EHsc UVa_663_Sorting_Slides.cpp
*/

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

struct edge {
  int v; // neighboring vertex
  int capacity; // capacity of edge
  int flow; // flow through edge
  int residual; // residual capacity of edge

  edge(int _v, int _capacity, int _residual) : 
    v(_v), capacity(_capacity), flow(0), residual(_residual) {}
};

struct vertex_state {
  bool discovered;
  int parent;

  vertex_state() : discovered(false), parent(-1) {}
};

void bfs(const vector< vector<edge> >& graph, int start,
  vector<vertex_state>& states)
{
  queue<int> q;
  states[start].discovered = true;
  q.push(start);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 0; i < graph[u].size(); i++) {
      const edge& e = graph[u][i];
      if (e.residual > 0 && !states[e.v].discovered) {
        states[e.v].discovered = true;
        states[e.v].parent = u;
        q.push(e.v);
      }
    }
  }
}

edge& find_edge(vector< vector<edge> >& graph, int u, int v)
{
  int i;
  for (i = 0; i < graph[u].size(); i++)
    if (graph[u][i].v == v)
      break;
  return graph[u][i];
}

int path_volume(vector< vector<edge> >& graph, int start, int end,
  const vector<vertex_state>& states)
{
  if (states[end].parent == -1)
    return 0;
  edge& e = find_edge(graph, states[end].parent, end);
  if (start == states[end].parent)
    return e.residual;
  else
    return min(path_volume(graph, start, states[end].parent, states), e.residual);
}

void augment_path(vector< vector<edge> >& graph, int start, int end,
  const vector<vertex_state>& states, int volume)
{
  if (start == end)
    return;
  edge& e = find_edge(graph, states[end].parent, end);
  if (e.flow < e.capacity)
    e.flow += volume;
  if (e.residual)
    e.residual -= volume;
  edge& r= find_edge(graph, end, states[end].parent);
  if (r.flow)
    r.flow -= volume;
  if (r.residual < r.capacity)
    r.residual += volume;
  augment_path(graph, start, states[end].parent, states, volume);
}

void netflow(vector< vector<edge> >& graph, int source, int sink)
{
  while (true) {
    vector<vertex_state> states(graph.size());
    bfs(graph, source, states);
    int volume = path_volume(graph, source, sink, states);
      // calculate the volume of augmenting path
    if (volume > 0)
      augment_path(graph, source, sink, states, volume);
    else
      break;
  }
}

int total_flow(const vector< vector<edge> >& graph, int source)
{
  int flow = 0;
  const vector<edge>& edges = graph[source];
  for (int i = 0, e = edges.size(); i < e; i++)
    flow += edges[i].flow;
  return flow;
}

struct slide {
  int x_min_, x_max_, y_min_, y_max_;
};

struct number {
  int x_, y_;
};

void add_edge(int i, int j, vector< vector<edge> >& graph) // add an edge from i to j
{
  graph[i].push_back(edge(j, 1, 1));
  graph[j].push_back(edge(i, 1, 0));
}

bool number_in_slide(const slide& s, const number& n)
{
  return n.x_ > s.x_min_ && n.x_ < s.x_max_ && n.y_ > s.y_min_ && n.y_ < s.y_max_;
}

int maximum_bipertite_matching(int n, int esi, int eni, const vector<slide>& slides,
  const vector<number>& numbers)
{
  int nr_vertices = n * 2 + 2;
  vector< vector<edge> > graph(nr_vertices);
  // indices are:
  //  0 - (n - 1): slide vertices, n - (n * 2 - 1): number vertices,
  //  n * 2: source vertex, (n * 2 + 1): sink vertex
  int source = n * 2, sink = n * 2 + 1;
  for (int i = 0; i < n; i++) // add the edges between slide vertices and number vertices
    if (i != esi) // exclude esi-th slide
      for (int j = 0; j < n; j++)
        if (j != eni && // exclude eni-th number
          number_in_slide(slides[i], numbers[j]))
          add_edge(i, n + j, graph);
  for (int i = 0; i < n; i++) {
    add_edge(source, i, graph); // add an edge from the source vertex to a slide vertex
    add_edge(n + i, sink, graph); // add an edge from a number vertex to sink vertex
  }
  netflow(graph, source, sink); // apply Ford-Fulkerson's augmenting path algorithm
  return total_flow(graph, source);
}

int main()
{
  for (int heap_nr = 1; ; heap_nr++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    vector<slide> slides(n);
    for (int i = 0; i < n; i++)
      scanf("%d %d %d %d",
        &slides[i].x_min_, &slides[i].x_max_, &slides[i].y_min_, &slides[i].y_max_);
    vector<number> numbers(n);
    for (int i = 0; i < n; i++)
      scanf("%d %d", &numbers[i].x_, &numbers[i].y_);
    vector<int> unique_matchings(n, -1);
    for (int i = 0; i < n; i++) // for each slide
      for (int j = 0; j < n; j++) // for each number
        if (number_in_slide(slides[i], numbers[j]) &&
          maximum_bipertite_matching(n, i, j, slides, numbers) == n - 1) {
          // perfect matching
          if (unique_matchings[i] == -1)
            unique_matchings[i] = j;
          else { // not unique
            unique_matchings[i] = -1;
            break;
          }
        }
    printf("Heap %d\n", heap_nr);
    bool none = true;
    for (int i = 0; i < n; i++)
      if (unique_matchings[i] != -1) {
        if (none)
          none = false;
        else
          putchar(' ');
        printf("(%c,%d)", 'A' + i, unique_matchings[i] + 1);
      }
    if (none)
      printf("none\n\n");
    else
      printf("\n\n");
  }
  return 0;
}

UVa 1103 - Ancient Messages

Accepted date: 2016-04-15
Run Time: 0.010
Ranking (as of 2016-04-15): 24 out of 591
Language: C++

/*
  UVa 1103 - Ancient Messages

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

#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <utility>
#include <cstdio>
#include <cctype>
using namespace std;

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)};
const char hieroglyph_characters[] = {0, 'W', 'A', 'K', 'J', 'S', 'D'};

const int H_max = 200, W_max = 50;
int image[H_max + 2][W_max * 4 + 2];

void bfs_black_pixels(int rows, int columns, int sr, int sc, int nr)
{
  image[sr][sc] = nr;
  queue< pair<int, int> > q;
  q.push(make_pair(sr, sc));
  while (!q.empty()) {
    pair<int, int> u = q.front();
    q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int r = u.first + dirs[i].first, c = u.second + dirs[i].second;
      if (r >= 0 && r < rows && c >= 0 && c < columns && image[r][c] == 1) {
        image[r][c] = nr;
        q.push(make_pair(r, c));
      }
    }
  }
}

void bfs_white_pixels(int rows, int columns, int sr, int sc, int nr,
  vector< set<int> >& hieroglyphs)
{
  image[sr][sc] = nr;
  queue< pair<int, int> > q;
  q.push(make_pair(sr, sc));
  while (!q.empty()) {
    pair<int, int> u = q.front();
    q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int r = u.first + dirs[i].first, c = u.second + dirs[i].second;
      if (r >= 0 && r < rows && c >= 0 && c < columns) {
        if (image[r][c] == 0) {
          image[r][c] = nr;
          q.push(make_pair(r, c));
        }
        else if (image[r][c] > 0)
          hieroglyphs[image[r][c] - 2].insert(nr);
      }
    }
  }
}

int main()
{
  const int nr_pixels = 4;
  for (int case_nr = 1; ; case_nr++) {
    int H, W;
    scanf("%d %d", &H, &W);
    if (!H)
      break;
    for (int i = 1; i <= H; i++) {
      char s[W_max + 1];
      scanf("%s", s);
      image[i][0] = 0;
      for (int j = 0, k = 1; j < W; j++, k += nr_pixels) {
        int p = (isdigit(s[j])) ? s[j] - '0' : s[j] - 'a' + 10;
        for (int l = 0, b = 8; l < nr_pixels; l++, b >>= 1)
          image[i][k + l] = (p & b) ? 1 : 0;
      }
      image[i][W * nr_pixels + 1] = 0;
    }
    W = W * nr_pixels + 2;
    for (int j = 0; j < W; j++)
      image[0][j] = image[H + 1][j] = 0;
    H += 2;
#ifdef DEBUG
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++)
        printf("%d", image[i][j]);
      putchar('\n');
    }
#endif
    int nr_hieroglyphs = 0;
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        if (image[i][j] == 1) {
          bfs_black_pixels(H, W, i, j, nr_hieroglyphs + 2);
          nr_hieroglyphs++;
        }
    int nr_white_areas = 0;
    vector< set<int> > hieroglyphs(nr_hieroglyphs);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        if (image[i][j] == 0) {
          bfs_white_pixels(H, W, i, j, -(nr_white_areas + 1), hieroglyphs);
          nr_white_areas++;
        }
#ifdef DEBUG
    printf("hieroglyphs: %d\n", nr_hieroglyphs);
    for (int i = 0; i < nr_hieroglyphs; i++)
      printf("  %d: %u\n", i, hieroglyphs[i].size());
    printf("white areas: %d\n", nr_white_areas);
#endif
    vector<char> codes;
    for (int i = 0; i < nr_hieroglyphs; i++)
      codes.push_back(hieroglyph_characters[hieroglyphs[i].size()]);
    sort(codes.begin(), codes.end());
    printf("Case %d: ", case_nr);
    for (int i = 0; i < codes.size(); i++)
      putchar(codes[i]);
    putchar('\n');
  }
  return 0;
}

UVa 523 - Minimum Transport Cost

Accepted date: 2016-04-14
Run Time: 0.040
Ranking (as of 2016-04-14): 40 out of 596
Language: C++

/*
  UVa 523 - Minimum Transport Cost

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <limits>
using namespace std;

int main()
{
  string line;
  getline(cin, line);
  istringstream iss(line);
  int M;
  iss >> M;
  iss.clear();
  getline(cin, line);
  while (M--) {
    vector< vector<int> > matrix;
    getline(cin, line);
    iss.str(line);
    matrix.push_back(vector<int>());
    int n = 0, c;
    while (iss >> c) {
      matrix[0].push_back((c != -1) ? c : numeric_limits<int>::max());
      n++;
    }
    iss.clear();
    for (int i = 1; i < n; i++) {
      matrix.push_back(vector<int>());
      getline(cin, line);
      iss.str(line);
      while (iss >> c)
        matrix[i].push_back((c != -1) ? c : numeric_limits<int>::max());
      iss.clear();
    }
    vector<int> taxes(n);
    getline(cin, line);
    iss.str(line);
    for (int i = 0; i < n; i++) {
      iss >> c;
      taxes[i] = c;
    }
    iss.clear();
    vector< vector<int> > nexts(n, vector<int>(n));
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        nexts[i][j] = j;
    // apply the Floyd-Warshall algorithm
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        if (matrix[i][k] != numeric_limits<int>::max())
          for (int j = 0; j < n; j++)
            if (matrix[k][j] != numeric_limits<int>::max() &&
              matrix[i][j] > matrix[i][k] + taxes[k] + matrix[k][j]) {
              matrix[i][j] = matrix[i][k] + taxes[k] + matrix[k][j];
              nexts[i][j] = nexts[i][k];
            }
    bool printed = false;
    while (getline(cin, line) && !line.empty()) {
      iss.str(line);
      int s, e;
      iss >> s >> e;
      iss.clear();
      if (printed)
        cout << endl;
      else
        printed = true;
      cout << "From " << s << " to " << e << " :\n";
      s--, e--;
      cout << "Path: " << s + 1;
//      if (s != e) {
        int u = s;
        do {
          u = nexts[u][e];
          cout << "-->" << u + 1;
        } while (u != e);
//      }
      cout << endl;
      cout << "Total cost : " << matrix[s][e] << endl;
    }
    if (M)
      cout << endl;
  }
  return 0;
}

UVa 12673 - Football

Accepted date: 2016-04-13
Run Time: 0.060
Ranking (as of 2016-04-13): 13 out of 457
Language: C++

/*
  UVa 12673 - Football

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

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

const int N_max = 100000, G_max = 1000000;

int loses[N_max];

int main()
{
  int N, G;
  while (scanf("%d %d", &N, &G) != EOF) {
    int nr_draws = 0, nr_loses = 0, points = 0;
    while (N--) {
      int S, R;
      scanf("%d %d", &S, &R);
      if (S > R)
        points += 3;
      else if (S == R)
        nr_draws++;
      else
        loses[nr_loses++] = R - S;
    }
    sort(loses, loses + nr_loses);
    if (G > nr_draws) {
      points += nr_draws * 3;
      G -= nr_draws, nr_draws = 0;
    }
    else {
      points += G * 3;
      nr_draws -= G, G = 0;
      points += nr_draws;
    }
    for (int i = 0; i < nr_loses; i++) {
      if (G < loses[i])
        break;
      if (G > loses[i]) {
        points += 3;
        G -= loses[i] + 1;
      }
      else {
        points++;
        G -= loses[i];
      }
    }
    printf("%d\n", points);
  }
  return 0;
}

UVa 373 - Romulan Spelling

Accepted date: 2016-04-10
Run Time: 0.020
Ranking (as of 2016-04-10): 2 out of 141
Language: C++

/*
  UVa 373 - Romulan Spelling

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

/*
  'g' should be before 'p', except "epg" and "pguk"
*/

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

const int nr_chars_max = 70;

int main()
{
  char s[nr_chars_max + 1];
  while (gets(s)) {
    for (int i = 0, length = strlen(s); i < length; i++) {
      if (tolower(s[i]) == 'g') {
        if (i && tolower(s[i - 1]) == 'p') {
          if (i < length - 1 && tolower(s[i + 1]) == 'u' && tolower(s[i + 2]) == 'k')
            ;
          else {
            int j = i;
            do {
              if (j > 1 && tolower(s[j - 2]) == 'e')
                break;
              swap(s[j - 1], s[j]);
              j--;
            }
            while (j && tolower(s[j - 1]) == 'p');
          }
        }
      }
      if (tolower(s[i]) == 'g') {
        if (i < length && tolower(s[i + 1]) == 'p') {
          if (i && tolower(s[i - 1]) == 'e')
            swap(s[i], s[i + 1]);
          else if (i < length - 2 && tolower(s[i + 2]) == 'u' && tolower(s[i + 3]) == 'k') {
            swap(s[i], s[i + 1]);
            if (i > 1 && tolower(s[i - 1]) == 'g' && tolower(s[i - 2]) == 'e')
              swap(s[i - 1], s[i]);
          }
        }
      }
    }
    puts(s);
  }
  return 0;
}

UVa 613 - Numbers That Count

Accepted date: 2016-04-01
Run Time: 0.026
Ranking (as of 2016-04-01): 44 out of 404
Language: C++

/*
  UVa 613 - Numbers That Count

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

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

const int nr_digits = '9' - '0' + 1, iterations_max = 15;

int main()
{
  while (true) {
    string inventory;
    cin >> inventory;
    if (inventory == "-1")
      break;
    string ps = inventory;
    map<string, int> inventories;
    int iterations;
    for (iterations = 0; iterations < iterations_max; iterations++) {
      int freqs[nr_digits];
      memset(freqs, 0, sizeof(freqs));
      for (const char* p = ps.c_str(); *p; p++)
        freqs[*p - '0']++;
      ostringstream oss;
      for (int i = 0; i < nr_digits; i++)
        if (freqs[i])
          oss << freqs[i] << i;
      string s = oss.str();
#ifdef DEBUG
      cout << iterations << ": " << s << endl;
#endif
      if (s == ps) {
        if (iterations)
          cout << inventory << " is self-inventorying after " << iterations << " steps\n";
        else
          cout << inventory << " is self-inventorying\n";
        break;
      }
      pair<map<string, int>::iterator, bool> result =
        inventories.insert(make_pair(s, iterations));
      if (!result.second) {
        cout << inventory << " enters an inventory loop of length " <<
          iterations - result.first->second << endl;
        break;
      }
      ps = s;
    }
    if (iterations == iterations_max)
      cout << inventory << " can not be classified after 15 iterations\n";
  }
  return 0;
}