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