UVa 11579 - Triangle Trouble

Accepted date: 2015-01-31
Ranking (as of 2015-01-31): 112 out of 451
Language: C++

/*
  UVa 11579 - Triangle Trouble

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

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

const int N_max = 10000;
double sides[N_max];

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
      scanf("%lf", &sides[i]);
    sort(sides, sides + N);
    double largest = 0.0;
    for (int i = 0; i < N - 2; i++) {
      double a = sides[i], b = sides[i + 1], c = sides[i + 2];
      if (a + b < c || b + c < a || c + a < b)
        continue;
      double s = (a + b + c) / 2.0,
        sa = s * (s - a) * (s - b) * (s - c); // Heron's formula
      largest = max(largest, sa);
    }
    printf("%.2lf\n", ((largest > 0.0) ? sqrt(largest) : largest));
  }
  return 0;
}

UVa 563 - Crimewave

Accepted date: 2015-01-23
Ranking (as of 2015-01-23): 374 out of 780
Language: C++

/*
  UVa 563 - Crimewave

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

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cctype>
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;
}

int main()
{
  int p;
  cin >> p;
  while (p--) {
    int s, a, b;
    cin >> s >> a >> b;
    vector< vector<bool> > crossings(s, vector<bool>(a, false));
    for (int i = 0; i < b; i++) {
      int x, y;
      cin >> x >> y;
      crossings[x - 1][y - 1] = true;
    }
    int nr_crossing_vertices = s * a * 2;
    // indices are:
    // 0 - s * a * 2 - 1: crossing vertices (two vertices per crossing),
    // s * a * 2: source vertex, s * a * 2 + 1: sink vertex
    int nr_vertices = nr_crossing_vertices + 2,
      source = nr_crossing_vertices, sink = nr_crossing_vertices + 1;
    vector< vector<edge> > graph(nr_vertices);
    for (int i = 0; i < s; i++)
      for (int j = 0; j < a; j++) {
        int u = (i * a + j) * 2, v;
        // append edges between the two crossing vertices (u for in, (u + 1) for out)
        graph[u].push_back(edge(u + 1, 1, 1));
        graph[u + 1].push_back(edge(u, 1, 0));
        if (crossings[i][j]) {
          // append edges from the source to the banks
          graph[source].push_back(edge(u, 1, 1));
          graph[u].push_back(edge(source, 1, 0));
        }
        else {
          // append adges from adjacent crosssing vertices
          if (i) {
            v = ((i - 1) * a + j) * 2 + 1;
            graph[v].push_back(edge(u, 1, 1));
            graph[u].push_back(edge(v, 1, 0));
          }
          if (i < s - 1) {
            v = ((i + 1) * a + j) * 2 + 1;
            graph[v].push_back(edge(u, 1, 1));
            graph[u].push_back(edge(v, 1, 0));
          }
          if (j) {
            v = (i * a + j - 1) * 2 + 1;
            graph[v].push_back(edge(u, 1, 1));
            graph[u].push_back(edge(v, 1, 0));
          }
          if (j < a - 1) {
            v = (i * a + j + 1) * 2 + 1;
            graph[v].push_back(edge(u, 1, 1));
            graph[u].push_back(edge(v, 1, 0));
          }
        }
        if (!i || i == s - 1 || !j || j == a - 1) {
          // append edges to sink vertex
          graph[u + 1].push_back(edge(sink, 1, 1));
          graph[sink].push_back(edge(u + 1, 1, 0));
        }
        else {
          // append adges to adjacent crosssing vertices
          v = ((i - 1) * a + j) * 2;
          graph[u + 1].push_back(edge(v, 1, 1));
          graph[v].push_back(edge(u + 1, 1, 0));
          v = ((i + 1) * a + j) * 2;
          graph[u + 1].push_back(edge(v, 1, 1));
          graph[v].push_back(edge(u + 1, 1, 0));
          v = (i * a + j - 1) * 2;
          graph[u + 1].push_back(edge(v, 1, 1));
          graph[v].push_back(edge(u + 1, 1, 0));
          v = (i * a + j + 1) * 2;
          graph[u + 1].push_back(edge(v, 1, 1));
          graph[v].push_back(edge(u + 1, 1, 0));
        }
      }
    netflow(graph, source, sink); // apply Ford-Fulkerson's augmenting path algorithm
    cout << ((total_flow(graph, source) == b) ? "possible\n" : "not possible\n");
  }
  return 0;
}

UVa 10459 - The Tree Root

Accepted date: 2015-01-21
Ranking (as of 2015-01-21): 198 out of 489
Language: C++

/*
  UVa 10459 - The Tree Root

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

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

int bfs(int n, int s, const vector< vector<int> >& edges,
  vector<int>& distances, vector<int>& prevs)
{
  for (int i = 0; i < n; i++)
    distances[i] = prevs[i] = -1;
  queue<int> q;
  distances[s] = 0;
  int furthest = s, d = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    if (distances[u] > d) {
      furthest = u;
      d = distances[u];
    }
    const vector<int>& es = edges[u];
    for (size_t j = 0, je = es.size(); j < je; j++) {
      int v = es[j];
      if (distances[v] == -1) {
        distances[v] = distances[u] + 1;
        prevs[v] = u;
        q.push(v);
      }
    }
  }
  return furthest;
}

int main()
{
  int N;
  while (cin >> N) {
    vector< vector<int> > edges(N + 1);
    for (int i = 1; i <= N; i++) {
      int k;
      cin >> k;
      while (k--) {
        int j;
        cin >> j;
        edges[i].push_back(j);
      }
    }
    vector<int> distances(N + 1), prevs(N + 1);
    int u = bfs(N + 1, 1, edges, distances, prevs);
    int v = bfs(N + 1, u, edges, distances, prevs);
    int diameter = distances[v];
#ifdef DEBUG
    cout << "diameter = " << diameter << endl;
    for (int i = v; i != -1; i = prevs[i])
      cout << i << ':' << distances[i] << ' ';
    cout << endl;
#endif
    int best_0, best_1 = -1;
    vector<int> worsts;
    if (diameter % 2) { // odd
      for (int i = v; ; i = prevs[i]) {
        if (distances[i] == (diameter + 1) / 2)
          best_1 = i;
        else if (distances[i] == diameter / 2) {
          best_0 = i;
          break;
        }
      }
      if (best_0 > best_1)
        swap(best_0, best_1);
    }
    else { // even
      for (int i = v; ; i = prevs[i])
        if (distances[i] == diameter / 2) {
          best_0 = i;
          break;
        }
    }
    v = bfs(N + 1, best_0, edges, distances, prevs);
    for (int i = 1; i <= N; i++)
      if (distances[i] == distances[v])
        worsts.push_back(i);
    if (best_1 != -1) {
      v = bfs(N + 1, best_1, edges, distances, prevs);
      for (int i = 1; i <= N; i++)
        if (distances[i] == distances[v])
          worsts.push_back(i);
    }
    sort(worsts.begin(), worsts.end());
    cout << "Best Roots  : " << best_0;
    if (best_1 != -1)
      cout << ' ' << best_1;
    cout << "\nWorst Roots :";
    for (size_t i = 0, e = worsts.size(); i < e; i++)
      cout << ' ' << worsts[i];
    cout << endl;
  }
  return 0;
}

UVa 434 - Matty's Blocks

Accepted date: 2015-01-12
Ranking (as of 2015-01-12): 272 out of 694
Language: C++

/*
  UVa 434 - Matty's Blocks

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

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

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    const int K_max = 8;
    int K;
    scanf("%d", &K);
    int i, j, f[K_max], sf[K_max], r[K_max], sr[K_max];
    for (i = 0; i < K; i++) {
      scanf("%d", &f[i]);
      sf[i] = f[i];
    }
    for (i = 0; i < K; i++) {
      scanf("%d", &r[i]);
      sr[i] = r[i];
    }
    sort(sf, sf + K, greater<int>());
    sort(sr, sr + K, greater<int>());
    int min_blocks = 0;
    for (i = 0, j = 0; i < K && j < K; ) {
      if (sf[i] == sr[j]) {
        min_blocks += sf[i];
        i++; j++;
      }
      else if (sf[i] < sr[j])
        min_blocks += sr[j++];
      else
        min_blocks += sf[i++];
    }
    if (i < K) {
      for ( ; i < K; i++)
        min_blocks += sf[i];
    }
    else if (j < K) {
      for ( ; j < K; j++)
        min_blocks += sr[j];
    }
    int max_blocks = 0;
    for (i = 0; i < K; i++)
      for (j = 0; j < K; j++)
        max_blocks += min(f[i], r[j]);
    printf("Matty needs at least %d blocks, and can add at most %d extra blocks.\n",
      min_blocks, max_blocks - min_blocks);
  }
  return 0;
}

UVa 10259 - Hippity Hopscotch

Accepted date: 2015-01-09
Language: C++

/*
  UVa 10259 - Hippity Hopscotch

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

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int n_max = 100;
int grid[n_max][n_max], visited[n_max][n_max];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  const int nr_dirs = 4;
  const pair<int, int> dirs[nr_dirs] =
    {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        cin >> grid[i][j];
        visited[i][j] = 0;
      }
    queue< pair<int, int> > q;
    visited[0][0] = grid[0][0];
    int max_nr = 0;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
      pair<int, int> u = q.front(); q.pop();
      int p = grid[u.first][u.second], nr = visited[u.first][u.second];
      max_nr = max(max_nr, nr);
      for (int i = 0; i < nr_dirs; i++)
        for (int j = 1; j <= k; j++) {
          int r = u.first + dirs[i].first * j, c = u.second + dirs[i].second * j;
          if (r >= 0 && r < n && c >= 0 && c < n &&
            grid[r][c] > p && visited[r][c] < grid[r][c] + nr) {
            visited[r][c] = grid[r][c] + nr;
            q.push(make_pair(r, c));
          }
        }
    }
    cout << max_nr << endl;
    if (t)
      cout << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 10660 - Citizen attention offices

Accepted date: 2015-01-07
Ranking (as of 2015-01-07): 164 out of 560
Language: C++

/*
  UVa 10660 - Citizen attention offices

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

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

const int nr_rows = 5, nr_columns = 5,
  nr_areas = nr_rows * nr_columns, nr_offices = 5;

struct area {
  int i_;
  int p_;
};

area areas[nr_areas];
int area_indices[nr_offices], min_d_offices[nr_offices];

int get_distance(int i, int j)
{
  int ri = i / nr_columns, ci = i % nr_columns,
    rj = j / nr_columns, cj = j % nr_columns;
  return abs(ri - rj) + abs(ci - cj);
}

void calculate_distances(int n, int ai, int k, int& min_d)
{
  if (k < nr_offices) {
    for (int i = ai; i < nr_areas; i++) {
      area_indices[k] = i;
      calculate_distances(n, i + 1, k + 1, min_d);
        // recursively generate the combinations of indices from (ai + 1) to (n - 1)
    }
  }
  else {
    int d = 0;
    for (int i = 0; i < n; i++) {
      int min_d_i = numeric_limits<int>::max();
      for (int j = 0; j < nr_offices; j++)
        min_d_i = min(min_d_i,
          get_distance(area_indices[j], areas[i].i_) * areas[i].p_);
      d += min_d_i;
    }
    if (d < min_d) {
      min_d = d;
#ifdef DEBUG
      printf("%d: ", min_d);
#endif
      for (int i = 0; i < nr_offices; i++) {
#ifdef DEBUG
        printf("%d%c", area_indices[i], ((i < nr_offices - 1) ? ' ' : '\n'));
#endif
        min_d_offices[i] = area_indices[i];
      }
    }
  }
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      int r, c;
      scanf("%d %d %d", &r, &c, &areas[i].p_);
      areas[i].i_ = r * nr_columns + c;
    }
    // generate all combinations of n areas taken 5 at a time, 
    // starting with combinations containing 0 in the first position
    int min_d = numeric_limits<int>::max();
    calculate_distances(n, 0, 0, min_d);
    for (int i = 0; i < nr_offices; i++)
      printf("%d%c", min_d_offices[i], ((i < nr_offices - 1) ? ' ' : '\n'));
  }
  return 0;
}

UVa 1586 - Molar mass

Accepted date: 2015-01-05
Language: C++

/*
  UVa 1586 - Molar mass

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

#include <cstdio>
#include <cstdlib>

int main()
{
  const int nr_chars_max = 80;
  const double w_carbon = 12.01,  w_hydrogen = 1.008, w_oxygen = 16.00,
    w_nitrogen = 14.01;
  int T;
  scanf("%d", &T);
  while (T--) {
    char s[nr_chars_max + 1];
    scanf("%s", s);
    int carbon = 0, hydrogen = 0, oxygen = 0, nitrogen = 0;
    for (char* p = s; *p; ) {
      char* pe = p + 1;
      if (*p == 'C' || *p == 'H' || *p == 'O' || *p == 'N') {
        int n = strtol(p + 1, &pe, 10);
        if (!n)
          n = 1;
        switch (*p) {
        case 'C':
          carbon += n; break;
        case 'H':
          hydrogen += n; break;
        case 'O':
          oxygen += n; break;
        case 'N':
          nitrogen += n; break;
        }
      }
      p = pe;
    }
    double w = w_carbon * carbon + w_hydrogen * hydrogen + w_oxygen * oxygen +
      w_nitrogen * nitrogen;
    printf("%.3lf\n", w);
  }
  return 0;
}

UVa 1247 - Interstar Transport

Accepted date: 2015-01-04
Language: C++

/*
  UVa 1247 - Interstar Transport

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

#include <cstdio>

const int s_max = 26, cost_max = 100, infinite = (s_max + 1) * cost_max;
int dists[s_max][s_max], paths[s_max][s_max], nexts[s_max][s_max];

void floyd_warshall_with_path_reconstruction(int n)
{
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (dists[i][k] + dists[k][j] < dists[i][j] ||
          dists[i][k] + dists[k][j] == dists[i][j] &&
          paths[i][k] + paths[k][j] < paths[i][j]) {
          dists[i][j] = dists[i][k] + dists[k][j];
          paths[i][j] = paths[i][k] + paths[k][j];
          nexts[i][j] = nexts[i][k];
        }
}

void print_path(int u, int v)
{
  putchar(u + 'A');
  while (u != v) {
    u = nexts[u][v];
    printf(" %c", u + 'A');
  }
  putchar('\n');
}

int main()
{
  for (int i = 0; i < s_max; i++)
    for (int j = 0; j < s_max; j++) {
      dists[i][j] = infinite;
      paths[i][j] = s_max + 1;
      nexts[i][j] = -1;
    }
  int s, p;
  scanf("%d %d", &s, &p);
  while (p--) {
    char ei[2], ej[2];
    int dij;
    scanf("%s %s %d", ei, ej, &dij);
    int u = ei[0] - 'A', v = ej[0] - 'A';
    dists[u][v] = dists[v][u] = dij;
    paths[u][v] = paths[v][u] = 1;
    nexts[u][v] = v; nexts[v][u] = u;
  }
  floyd_warshall_with_path_reconstruction(s_max);
  int n;
  scanf("%d", &n);
  while (n--) {
    char ek[2], em[2];
    scanf("%s %s", ek, em);
    print_path(ek[0] - 'A', em[0] - 'A');
  }
  return 0;
}