UVa 346 - Getting Chorded

Accepted date: 2014-12-27
Ranking (as of 2014-12-27): 33 out of 406
Language: C++

/*
  UVa 346 - Getting Chorded

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

#include <cstdio>
#include <cstring>
#include <cctype>

#ifdef ONLINE_JUDGE
#define _stricmp strcasecmp
#endif

const int nr_chars_max = 3, nr_notes = 3, index_max = 12;

struct note {
  char s_[nr_chars_max + 1];
  int ci_, i_;
};

const note chromatic_notes[] = {
  {"A", 0}, {"A#", 1}, {"Bb", 1}, {"B", 2}, {"Cb", 2}, {"B#", 3},
  {"C", 3},{"C#", 4}, {"Db", 4}, {"D", 5}, {"D#", 6},
  {"Eb", 6}, {"E", 7}, {"Fb", 7}, {"E#", 8}, {"F", 8}, {"F#", 9},
  {"Gb", 9}, {"G", 10}, {"G#", 11}, {"Ab", 11}
};

void get_index(note& n)
{
  int i;
  for (i = 0; i < sizeof(chromatic_notes) / sizeof(note); i++)
    if (!_stricmp(n.s_, chromatic_notes[i].s_))
      break;
  n.ci_ = chromatic_notes[i].ci_; n.i_ = i;
}

const char* get_key(const note& n)
{
  int i = n.i_;
  if (n.s_[1] == 'b')
    i--;
  else if (n.s_[1] == '#') {
    if (chromatic_notes[i].s_[0] == 'B' || chromatic_notes[i].s_[0] == 'E')
      i++;
  }
  return chromatic_notes[i].s_;
}

int main()
{
  const int perms[][nr_notes] = {
    {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}
  };

  note notes[nr_notes];
  while (scanf("%s %s %s", notes[0].s_, notes[1].s_, notes[2].s_) != EOF) {
    for (int i = 0; i < nr_notes; i++)
      get_index(notes[i]);
    bool recognized = false;
    for (size_t i = 0; i < sizeof(perms) / sizeof(perms[0]); i++) {
      int third = notes[perms[i][1]].ci_ - notes[perms[i][0]].ci_,
        fifth = notes[perms[i][2]].ci_ - notes[perms[i][0]].ci_;
      char key[nr_chars_max + 1];
      if (third < 0)
        third += index_max;
      if (fifth < 0)
        fifth += index_max;
      if (third == 4 && fifth == 7) {
        recognized = true;
        printf("%s %s %s is a %s Major chord.\n",
          notes[0].s_, notes[1].s_, notes[2].s_, get_key(notes[perms[i][0]]));
        break;
      }
      else if (third == 3 && fifth == 7) {
        recognized = true;
        printf("%s %s %s is a %s Minor chord.\n",
          notes[0].s_, notes[1].s_, notes[2].s_, get_key(notes[perms[i][0]]));
        break;
      }
    }
    if (!recognized)
      printf("%s %s %s is unrecognized.\n", notes[0].s_, notes[1].s_, notes[2].s_);
  }
  return 0;
}

UVa 1174 - IP-TV

Accepted date: 2014-12-22
Language: C++

/*
  UVa 1174 - IP-TV

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

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

const int nr_chars_max = 15;

struct city {
  char s_[nr_chars_max + 1];

  city() {}
  city(const char* s) {strcpy(s_, s);}
  bool operator<(const city& c) const {return strcmp(s_, c.s_) < 0;}
};

int register_city(const char* s, map<city, int>& cities)
{
  pair<map<city, int>::iterator, bool> result =
    cities.insert(make_pair(city(s), static_cast<int>(cities.size())));
  return result.first->second;
}

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 mst_prim(int n, const vector< vector<edge> >& edges)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[0] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  pq.insert(0);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += 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] && w < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = w;
        pq.insert(v);
      }
    }
  }
  return mst_distance;
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int M, N;
    scanf("%d %d", &M, &N);
    map<city, int> cities;
    vector< vector<edge> > edges(M);
    while (N--) {
      char B[nr_chars_max + 1], E[nr_chars_max + 1];
      int C;
      scanf("%s %s %d", B, E, &C);
      int u = register_city(B, cities), v = register_city(E, cities);
      edges[u].push_back(edge(v, C));
      edges[v].push_back(edge(u, C));
    }
    printf("%d\n", mst_prim(M, edges));
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}

UVa 1235 - Anti Brute Force Lock

Accepted date: 2014-12-17
Ranking (as of 2014-12-17): 29 out of 408
Language: C++

/*
  UVa 1235 - Anti Brute Force Lock

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

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

const int nr_digits = 4, N_max = 500;
int keys[N_max + 1][nr_digits], edges[N_max + 1][N_max + 1];

int get_number_of_rolls(const int* ki, const int* kj)
{
  int d = 0;
  for (int k = 0; k < nr_digits; k++, ki++, kj++) {
    int i = *ki, j = *kj;
    if (i < j)
      swap(i, j);
    d += min(i - j, j + 10 - i);
  }
  return d;
}

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 mst_prim(int n, int s)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[s] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  if (!s) { // zero key (0000) is not in the unlock key list
    int u = 0, d = numeric_limits<int>::max();
    for (int v = 1; v < n; v++)
      if (edges[s][v] < d) {
        u = v; d = edges[s][v];
      }
    distances[u] = d;
    pq.insert(u);
  }
  else
    pq.insert(s);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += distances[u];
    for (int v = 1; v < n; v++)
      if (!visited[v] && edges[u][v] < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = edges[u][v];
        pq.insert(v);
      }
  }
  return mst_distance;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int zero_key = 0;
    for (int i = 1; i <= N; i++) {
      char s[nr_digits + 1];
      scanf("%s", s);
      int k = 0;
      for (int j = 0; j < nr_digits; j++) {
        keys[i][j] = s[j] - '0';
        k += keys[i][j];
      }
      if (!k)
        zero_key = i;
    }
    for (int i = 0; i < N; i++)
      for (int j = i + 1; j <= N; j++)
        edges[i][j] = edges[j][i] = get_number_of_rolls(keys[i], keys[j]);
    // apply Prim's minimum spanning tree algorithm
    printf("%d\n", mst_prim(N + 1, zero_key));
  }
  return 0;
}

UVa 614 - Mapping the Route

Accepted date: 2014-12-16
Language: C++

/*
  UVa 614 - Mapping the Route

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

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

const int nr_rows_max = 12, nr_columns_max = 12;
int nr_rows, nr_columns;
int walls[nr_rows_max][nr_columns_max];
bool visited[nr_rows_max][nr_columns_max];
pair<int, int> paths[nr_rows_max][nr_columns_max];
int cells[nr_rows_max][nr_columns_max];

bool dfs(const pair<int, int>& u, const pair<int, int>& g)
{
  const int nr_dirs = 4;
  pair<int, int> dirs[nr_dirs] =
    {make_pair(0, -1), make_pair(-1, 0), make_pair(0, 1), make_pair(1, 0)};

#ifdef DEBUG
  printf("%d %d\n", u.first, u.second);
#endif
  visited[u.first][u.second] = true;
  if (u == g)
    return true;
  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 >= nr_rows || c < 0 || c >= nr_columns)
      continue;
    if (i == 0 && walls[r][c] & 1 || i == 2 && walls[r][c - 1] & 1 || // eastern wall
      i == 1 && walls[r][c] & 2 || i == 3 && walls[r - 1][c] & 2) // southern wall
      continue;
    if (!visited[r][c]) {
      paths[r][c] = u;
      if (dfs(make_pair(r, c), g))
        return true;
    }
  }
  return false;
}

int follow_paths(const pair<int, int>& s, const pair<int, int>& u)
{
  if (u == s)
    return cells[u.first][u.second] = 1;
  else
    return cells[u.first][u.second] = follow_paths(s, paths[u.first][u.second]) + 1;
}

int main()
{
  for (int maze_nr = 1; ; maze_nr++) {
    pair<int, int> s, g;
    scanf("%d %d %d %d %d %d",
      &nr_rows, &nr_columns, &s.first, &s.second, &g.first, &g.second);
    s.first--; s.second--; g.first--; g.second--;
    if (!nr_rows)
      break;
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        scanf("%d", &walls[r][c]);

    memset(visited, 0, sizeof(visited));
    memset(cells, 0, sizeof(cells));
    if (dfs(s, g))
      follow_paths(s, g);
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        if (visited[r][c] && !cells[r][c])
          cells[r][c] = -1;
    printf("Maze %d\n\n", maze_nr);
    putchar('+');
    for (int c = 0; c < nr_columns; c++)
      printf("---+");
    putchar('\n');
    for (int r = 0; r < nr_rows; r++) {
      putchar('|');
      for (int c = 0; c < nr_columns; c++) {
        if (cells[r][c] > 0)
          printf("%3d", cells[r][c]);
        else if (cells[r][c] < 0)
          printf("???");
        else
          printf("   ");
        putchar((walls[r][c] & 1 || c == nr_columns - 1) ? '|' : ' ');
      }
      putchar('\n');
      if (r < nr_rows - 1) {
        putchar('+');
        for (int c = 0; c < nr_columns; c++)
          if (walls[r][c] & 2)
            printf("---+");
          else
            printf("   +");
        printf("\n");
      }
    }
    putchar('+');
    for (int c = 0; c < nr_columns; c++)
      printf("---+");
    printf("\n\n\n");
  }
  return 0;
}

UVa 928 - Eternal Truths

Accepted date: 2014-12-14
Ranking (as of 2014-12-14): 73 out of 444
Language: C++

/*
  UVa 928 - Eternal Truths

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

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

const int R_max = 300, C_max = 300, nr_steps = 3;
char maze[R_max][C_max + 1];
bool visited[R_max][C_max][nr_steps + 1];

int bfs(int R, int C, const pair<int, int>& s, const pair<int, int>& e)
{
  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)};
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      for (int s = 1; s <= nr_steps; s++)
        visited[r][c][s] = false;
  queue< pair<pair<int, int>, int> > q;
  q.push(make_pair(s, 0));
  while (!q.empty()) {
    pair<pair<int, int>, int> p = q.front(); q.pop();
    if (p.first == e)
      return p.second;
    int s = (p.second + 1) % nr_steps;
    if (!s)
      s = nr_steps;
    for (int i = 0; i < nr_dirs; i++)
      for (int j = 1; j <= s; j++) {
        int r = p.first.first + j * dirs[i].first,
          c = p.first.second + j * dirs[i].second;
        if (r < 0 || r >= R || c < 0 || c >= C || maze[r][c] == '#')
          break;
        if (j == s && !visited[r][c][s]) {
#ifdef DEBUG
          printf("%d %d %d %d\n", r, c, s, p.second + 1);
#endif
          visited[r][c][s] = true;
          q.push(make_pair(make_pair(r, c), p.second + 1));
        }
      }
  }
  return -1;
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int R, C;
    scanf("%d %d", &R, &C);
    getchar();
    pair<int, int> s, e;
    s.first = e.first = -1;
    for (int r = 0; r < R; r++) {
      gets(maze[r]);
      for (int c = 0; c < C; c++)
        if (s.first == -1 && maze[r][c] == 'S')
          s = make_pair(r, c);
        else if (e.first == -1 && maze[r][c] == 'E')
          e = make_pair(r, c);
    }
    int nr_moves = bfs(R, C, s, e);
    if (nr_moves != -1)
      printf("%d\n", nr_moves);
    else
      puts("NO");
  }
  return 0;
}

UVa 11945 - Financial Management

Accepted date: 2014-12-11
Language: JAVA

// UVa 11945 - Financial Management

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int n = 1; n <= N; n++) {
      double s = 0.0;
      for (int i = 0; i < 12; i++)
        s += sc.nextDouble();
      System.out.printf("%d $%,.2f\n", n, s / 12.0);
    }
  }
}

UVa 10917 - A Walk Through the Forest

Accepted date: 2014-12-07
Ranking (as of 2014-12-07): 254 out of 674
Language: C++

/*
  UVa 10917 - A Walk Through the Forest

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

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <limits>
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)
{
  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];
}

void bfs(int n, int start, const vector< vector<edge> >& edges,
  const vector<int>& distances, vector<int>& routes)
{
  routes[start] = 1;
  vector<bool> visited(n, false);
  priority_queue<int, vector<int>, distance_comparator> pq(distances);
  visited[start] = true;
  pq.push(start);
  while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_;
      if (distances[u] > distances[v]) {
        if (visited[v])
          routes[v] += routes[u];
        else {
          visited[v] = true;
          routes[v] = routes[u];
          pq.push(v);
        }
      }
    }
  }
}

int main()
{
  while (true) {
    int n, m;
    cin >> n;
    if (!n)
      break;
    cin >> m;
    vector< vector<edge> > edges(n);
    while (m--) {
      int u, v, d;
      cin >> u >> v >> d;
      u--; v--;
      edges[u].push_back(edge(v, d));
      edges[v].push_back(edge(u, d));
    }
    vector<int> distances(n, numeric_limits<int>::max());
    dijkstra_shortest_path(n, 1, 0, edges, distances);
    vector<int> routes(n, 0);
    bfs(n, 0, edges, distances, routes);
    cout << routes[1] << endl;
  }
  return 0;
}

UVa 10307 - Killing Aliens in Borg Maze

Accepted date: 2014-12-03
Ranking (as of 2014-12-03): 138 out of 821
Language: C++

/*
  UVa 10307 - Killing Aliens in Borg Maze

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

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

const int x_max = 50, y_max = 50;
char maze[y_max][x_max + 1];

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

void bfs(int x, int y, int u, const pair<int, int>& p, vector<int>& sa_distances)
{
  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)};

  vector< vector<int> > distances(y, vector<int>(x, -1));
  queue< pair<int, int> > q;
  distances[p.first][p.second] = 0;
  sa_distances[u] = 0;
  q.push(p);
  while (!q.empty()) {
    pair<int, int> pu = q.front(); q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int j = pu.first + dirs[i].first, k = pu.second + dirs[i].second;
      if (maze[j][k] != '#' && distances[j][k] == -1) {
        distances[j][k] = distances[pu.first][pu.second] + 1;
        if (maze[j][k] != ' ')
          sa_distances[-maze[j][k]] = distances[j][k];
        q.push(make_pair(j, k));
      }
    }
  }
}

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 mst_prim(int n, const vector< vector<edge> >& edges)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[0] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  pq.insert(0);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += 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] && w < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = w;
        pq.insert(v);
      }
    }
  }
  return mst_distance;
}

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int x, y;
    scanf("%d %d", &x, &y);
    getchar(); // skip '\n'
    int s = 0, n = 0; // total number of the start and the aliens
    vector< pair<int, int> > points; // positions of the start and the aliens
    for (int i = 0; i < y; i++) {
      gets(maze[i]);
      for (int j = 0; j < x; j++)
        if (maze[i][j] == 'S') {
          points.insert(points.begin(), make_pair(i, j));
          s++;
          maze[i][j] = 0;
        }
        else if (maze[i][j] == 'A') {
          points.push_back(make_pair(i, j));
          n++;
          maze[i][j] = -n;
        }
    }
    if (!s || !n) {
      puts("0"); continue;
    }
    n++; // n += s
    vector< vector<edge> > edges(n);
    // calculate the distances between the start and the aliens
    for (int i = 0; i < n; i++) {
      vector<int> distances(n, -1);
      bfs(x, y, i, points[i], distances);
      vector<edge>& es = edges[i];
      for (int j = 0; j < n; j++)
        if (i != j && distances[j] != -1)
          es.push_back(edge(j, distances[j]));
#ifdef DEBUG
      printf("%d: [%d %d] ", i, points[i].first, points[i].second);
      for (size_t j = 0; j < es.size(); j++)
        printf("%d: %d%c", es[j].v_, es[j].w_, ((j < es.size() - 1) ? ' ' : '\n'));
#endif
    }
    // apply Prim's minimum spanning tree algorithm
    printf("%d\n", mst_prim(n, edges));
  }
  return 0;
}

UVa 12247 - Jollo

Accepted date: 2014-12-02
Language: C++

/*
  UVa 12247 - Jollo

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

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

const int nr_cards = 52, nr_rounds = 3;

int main()
{
  while (true) {
    vector<int> princess(nr_rounds), prince(nr_rounds - 1);
    cin >> princess[0] >> princess[1] >> princess[2] >> prince[0] >> prince[1];
    if (!princess[0])
      break;
    sort(princess.begin(), princess.end()); // sort in ascending order
    if (prince[0] < prince[1])
      swap(prince[0], prince[1]); // sort in descending order
    vector<bool> discards(nr_cards + 1, false);

    // 1st round
    // Prince loses with the pair of cards that has the minimum positive difference.
    int min_diff = nr_cards, min_i, min_j;
    for (int i = 0; i < nr_rounds; i++)
      for (int j = 0; j < nr_rounds - 1; j++) {
        int diff = princess[i] - prince[j];
        if (diff > 0 && diff < min_diff) {
          min_diff = diff;
          min_i = i; min_j = j;
        }
      }
    if (min_diff == nr_cards) {
      // Prince will win two rounds with the current set of cards
      for (int i = 0; i < nr_rounds; i++)
        discards[princess[i]] = true;
      for (int i = 0; i < nr_rounds - 1; i++)
        discards[prince[i]] = true;
      for (int i = 1; i <= nr_cards; i++)
        if (!discards[i]) {
          cout << i << endl;
          break;
        }
      continue;
    }
#ifdef DEBUG
    cout << princess[min_i] << ' ' << prince[min_j] << endl;
#endif
    discards[princess[min_i]] = discards[prince[min_j]] = true;
    princess.erase(princess.begin() + min_i); prince.erase(prince.begin() + min_j);

    // 2nd round
    // Prince wins with the pair of remaining cards that has 
    // the maximum negative difference.
    min_diff = 0;
    for (int i = 0; i < nr_rounds - 1; i++) {
      int diff = princess[i] - prince[0];
      if (diff > 0) {
        min_diff = 0; break;
      }
      else if (diff < min_diff) {
        min_diff = diff;
        min_i = i;
      }
    }
    if (!min_diff) { // Prince will lose two rounds with the current set of cards
      cout << -1 << endl;
      continue;
    }

#ifdef DEBUG
    cout << princess[min_i] << ' ' << prince[0] << endl;
#endif
    discards[princess[min_i]] = discards[prince[0]] = true;
    princess.erase(princess.begin() + min_i);

    // 3rd round
    // Prince wins with a card that is greater than the Princess's remaining card, 
    // excluding the ones that have already been discarded.
    int p = princess[0] + 1;
    for ( ; p <= nr_cards; p++)
      if (!discards[p])
        break;
    cout << ((p <= nr_cards) ? p : -1) << endl;
  }
  return 0;
}

UVa 12650 - Dangerous Dive

Accepted date: 2014-11-30
Ranking (as of 2014-11-30): 58 out of 509
Language: C++

/*
  UVa 12650 - Dangerous Dive

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

#include <cstdio>

const int N_max = 10000, R_max = 10000;

bool volunteers[N_max + 1];

int main()
{
  int N, R;
  while (scanf("%d %d", &N, &R) != EOF) {
    if (R < N)
      for (int i = 1; i <= N; i++)
        volunteers[i] = false;
    for (int i = 0; i < R; i++) {
      int j;
      scanf("%d", &j);
      volunteers[j] = true;
    }
    if (R < N) {
      N -= R;
      for (int i = 1; N; i++)
        if (!volunteers[i]) {
          N--;
          printf("%d ", i);
        }
      putchar('\n');
    }
    else
      puts("*");
  }
  return 0;
}

UVa 11902 - Dominator

Accepted date: 2014-11-30
Ranking (as of 2014-11-30): 151 out of 524
Language: C++

/*
  UVa 11902 - Dominator

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

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

void dfs(int i, int excluded, const vector< vector<int> >& edges,
  vector<bool>& visited)
{
  if (i != excluded) {
    visited[i] = true;
    const vector<int>& es = edges[i];
    for (size_t j = 0, k = es.size(); j < k; j++)
      if (!visited[es[j]])
        dfs(es[j], excluded, edges, visited);
  }
}

int main()
{
  int t;
  cin >> t;
  for (int case_nr = 1; case_nr <= t; case_nr++) {
    int n;
    cin >> n;
    vector< vector<int> > edges(n);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        int k;
        cin >> k;
        if (k)
          edges[i].push_back(j);
      }
    vector<bool> visited_from_start(n, false);
    dfs(0, -1, edges, visited_from_start);
    vector< vector<bool> > relationships(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++)
      if (visited_from_start[i]) {
        vector<bool> visited(n, false);
        dfs(0, i, edges, visited);
        for (int j = 0; j < n; j++)
          if (visited_from_start[j] && !visited[j])
            relationships[i][j] = true;
      }
    cout << "Case " << case_nr << ":\n";
    string separator = '+' + string(2 * n - 1, '-') + "+\n";
    cout << separator;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++)
        cout << '|' << ((relationships[i][j]) ? 'Y' : 'N');
      cout << "|\n" << separator;
    }
  }
  return 0;
}

UVa 10977 - Enchanted Forest

Accepted date: 2014-11-28
Ranking (as of 2014-11-30): 74 out of 517
Language: C++

/*
  UVa 10977 - Enchanted Forest

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

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

const int R_max = 200, C_max = 200;
bool grid[R_max + 1][C_max + 1];
bool visited[R_max + 1][C_max + 1];

const int nr_dirs = 4;
pair<int, int> dirs[nr_dirs] =
  {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};

int main()
{
  while (true) {
    int R, C;
    cin >> R >> C;
    if (!R && !C)
      break;

    for (int r = 1; r <= R; r++)
      for (int c = 1; c <= C; c++) {
        grid[r][c] = true;
        visited[r][c] = false;
      }
    int m;
    cin >> m;
    while (m--) {
      int r, c;
      cin >> r >> c;
      grid[r][c] = false;
    }
    int n;
    cin >> n;
    while (n--) {
      int r, c, L;
      cin >> r >> c >> L;
      if (!L) // L should be greater than zero
        continue;
      int rs = max(r - L, 1), re = min(r + L, R),
        cs = max(c - L, 1), ce = min(c + L, C), ls = L * L;
      for (int i = rs; i <= re; i++)
        for (int j = cs; j <= ce; j++)
          if ((i - r) * (i - r) + (j - c) * (j - c) <= ls)
            grid[i][j] = false;
    }

#ifdef DEBUG
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++)
        cout << grid[r][c] << ' ';
      cout << endl;
    }
#endif
/*
    if (R == 1 && C == 1) { // already left the forest
      cout << 0 << endl;
      continue;
    }
*/
    // breadth-first search
    queue< pair< pair<int, int>, int> > q;
    bool impossible = true;
    int path = 0;
    if (grid[1][1]) {
      visited[1][1] = true;
      q.push(make_pair(make_pair(1, 1), path));
    }
    while (!q.empty()) {
      pair< pair<int, int>, int> p = q.front(); q.pop();
      path = p.second;
      if (p.first.first == R && p.first.second == C) {
        impossible = false;
        break;
      }
      path++;
      for (int i = 0; i < nr_dirs; i++) {
        int r = p.first.first + dirs[i].first, c = p.first.second + dirs[i].second;
        if (r >= 1 && r <= R && c >= 1 && c <= C && grid[r][c] && !visited[r][c]) {
          visited[r][c] = true;
          q.push(make_pair(make_pair(r, c), path));
        }
      }
    }
    if (impossible)
      cout << "Impossible.\n";
    else
      cout << path << endl;
  }
  return 0;
}

UVa 397 - Equation Elation

Accepted date: 2014-11-23
Language: C++

/*
  UVa 397 - Equation Elation

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

#include <iostream>
#include <sstream>
#include <string>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;

enum {type_operator, type_operand};
enum {multiply, divide, add, subtract};

struct op {
  int type_;
  int value_;

  op() {}
  op(int type, int value) : type_(type), value_(value) {}

  string to_string() const {
    ostringstream oss;
    if (type_ == type_operator) {
      switch (value_) {
      case multiply:
        oss << '*'; break;
      case divide:
        oss << '/'; break;
      case add:
        oss << '+'; break;
      case subtract:
        oss << '-'; break;
      }
    }
    else
      oss << value_;
    return oss.str();
  }

#ifdef DEBUG
  void print() const {
    if (type_ == type_operator) {
      switch (value_) {
      case multiply:
        cout << '*'; break;
      case divide:
        cout << '/'; break;
      case add:
        cout << '+'; break;
      case subtract:
        cout << '-'; break;
      }
    }
    else
      cout << value_;
  }
#endif
};

int read_integer()
{
  int i = 0;
  while (true) {
    char c;
    cin >> c;
    if (!isdigit(c)) {
      cin.unget();
      break;
    }
    i *= 10;
    i += c - '0';
  }
  return i;
}

bool read_equation(deque<op>& infix_ops, string& variable, int& nr_muldiv)
{
  nr_muldiv = 0;
  char c = 0;
  while (cin >> c) {
    if (c == '=') {
      cin >> variable;
      return true;
    }
    if (c == '+' || c == '-') {
      if (infix_ops.empty() || infix_ops.back().type_ == type_operator) {
        // unary operator
        int sign = (c == '-') ? -1 : 1;
        infix_ops.push_back(op(type_operand, sign * read_integer()));
      }
      else
        infix_ops.push_back(op(type_operator, ((c == '-') ? subtract : add)));
    }
    else if (c == '*') {
      nr_muldiv++;
      infix_ops.push_back(op(type_operator, multiply));
    }
    else if (c == '/') {
      nr_muldiv++;
      infix_ops.push_back(op(type_operator, divide));
    }
    else {
      cin.unget();
      infix_ops.push_back(op(type_operand, read_integer()));
    }
  }
  return false;
}

#ifdef DEBUG
void print_equation(const deque<op>& infix_ops, const string& variable)
{
  for (deque<op>::const_iterator i = infix_ops.begin(), e = infix_ops.end();
    i != e; ++i) {
    i->print();
    cout <<  ' ';
  }
  cout << "= " << variable << endl;
}
#endif

void infix_to_postfix(const deque<op>& infix_ops, deque<op>& postfix_ops)
{
  stack<op> st;
  for (deque<op>::const_iterator i = infix_ops.begin(), e = infix_ops.end();
    i != e; ++i) {
    if (i->type_ == type_operand)
      postfix_ops.push_back(*i);
    else {
      while (!st.empty()) {
        if ((st.top().value_ == multiply || st.top().value_ == divide) ||
          (i->value_ == add || i->value_ == subtract)) {
          // stack top operator has equal or higher precedence
          postfix_ops.push_back(st.top());
          st.pop();
        }
        else
          break;
      }
      st.push(*i);
    }
  }
  while (!st.empty()) {
    postfix_ops.push_back(st.top());
    st.pop();
  }
}

void print_infix_equation(const deque<op>& postfix_ops, const string& variable)
{
  stack<string> st;
  for (deque<op>::const_iterator i = postfix_ops.begin(), e = postfix_ops.end();
    i != e; ++i) {
    if (i->type_ == type_operand)
      st.push(i->to_string());
    else {
      string sj = st.top(); st.pop();
      string si = st.top(); st.pop();
      st.push(si + " " + i->to_string() + " " + sj);
    }
  }
  cout << st.top() << " = " + variable << endl;
}

void calculate(deque<op>& postfix_ops, int& nr_muldiv)
{
  stack<op> st;
  while (!postfix_ops.empty()) {
    op o = postfix_ops.front();
    postfix_ops.pop_front();
    if (o.type_ == type_operand)
      st.push(o);
    else if (nr_muldiv && (o.value_ == add || o.value_ == subtract))
      st.push(o);
    else {
      op oj = st.top();
      st.pop();
      op oi = st.top();
      st.pop();
      int v;
      switch (o.value_) {
      case multiply:
        nr_muldiv--;
        v = oi.value_ * oj.value_; break;
      case divide:
        nr_muldiv--;
        v = oi.value_ / oj.value_; break;
      case add:
        v = oi.value_ + oj.value_; break;
      case subtract:
        v = oi.value_ - oj.value_; break;
      }
      postfix_ops.push_front(op(type_operand, v));
      break;
    }
  }
  while (!st.empty()) {
    postfix_ops.push_front(st.top());
    st.pop();
  }
}

int main()
{
  while (true) {
    deque<op> infix_ops;
    string variable;
    int nr_muldiv;
    if (!read_equation(infix_ops, variable, nr_muldiv))
      break;
    deque<op> postfix_ops;
    infix_to_postfix(infix_ops, postfix_ops);
    print_infix_equation(postfix_ops, variable);
    do {
      calculate(postfix_ops, nr_muldiv);
#ifdef DEBUG
      print_equation(postfix_ops, variable);
#endif
      print_infix_equation(postfix_ops, variable);
    } while (postfix_ops.size() > 1);
    cout << endl;
  }
  return 0;
}

UVa 586 - Instant Complexity

Accepted date: 2014-11-22
Language: C++

/*
  UVa 586 - Instant Complexity

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

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
using namespace std;

const int nr_coefficients_max = 10;
enum tree_node_types {program, op, loop_nr, loop};

struct tree_node {
  tree_node* parent_;
  tree_node* child_or_sibling_;
  int type_;
  int value_; // for op or loop_nr
  int coefficients_[nr_coefficients_max + 1];

  tree_node(tree_node* parent)
    : parent_(parent), child_or_sibling_(NULL), type_(program)
  {
    memset(coefficients_, 0, sizeof(coefficients_));
  }

  ~tree_node()
  {
    delete child_or_sibling_;
  }

  tree_node* insert_node(int type, int value) {
    tree_node* tn = new tree_node(this);
    if (!child_or_sibling_) // first child
      child_or_sibling_ = tn;
    else {
      tree_node* stn = child_or_sibling_;
      while (stn->child_or_sibling_)
        stn = stn->child_or_sibling_;
      stn->child_or_sibling_ = tn;
    }
    tn->type_ = type; tn->value_ = value;
    if (tn->type_ == op)
      tn->coefficients_[0] = value;
    return tn;
  }

  void calculate_complexity() {
    for (tree_node* tn = child_or_sibling_; tn; tn = tn->child_or_sibling_)
      for (int i = 0; i <= nr_coefficients_max; i++)
        coefficients_[i] += tn->coefficients_[i];
    if (type_ == loop_nr)
      for (int i = 0; i <= nr_coefficients_max; i++)
        coefficients_[i] *= value_;
    else if (type_ == loop) {
      for (int i = nr_coefficients_max; i; i--)
        coefficients_[i] = coefficients_[i - 1];
      coefficients_[0] = 0;
    }
    delete child_or_sibling_;
    child_or_sibling_ = NULL;
  }

  void print_complexity() {
    bool printed = false;
    for (int i = nr_coefficients_max; i >= 0; i--)
      if (coefficients_[i]) {
        if (coefficients_[i] < 0)
          cout << '-';
        else if (printed)
          cout << '+';
        if (i) {
          if (abs(coefficients_[i]) > 1)
            cout << abs(coefficients_[i]) << '*';
          cout << 'n';
          if (i > 1)
            cout << '^' << i;
        }
        else
          cout << abs(coefficients_[i]);
        printed = true;
      }
    if (!printed)
      cout << 0;
  }
};

int main()
{
  int k;
  cin >> k;
  for (int program_nr = 1; program_nr <= k; program_nr++) {
    string s;
    cin >> s; // "BEGIN"
    tree_node* parent = new tree_node(NULL);
    while (true) {
      cin >> s;
      if (s == "LOOP") {
        cin >> s;
        parent = (s == "n") ? parent->insert_node(loop, -1) : 
          parent->insert_node(loop_nr, atoi(s.c_str()));
      }
      else if (s == "OP") {
        cin >> s;
        parent->insert_node(op, atoi(s.c_str()));
      }
      else { // "END"
        parent->calculate_complexity();
        if (!parent->parent_)
          break;
#ifdef DEBUG
        parent->print_complexity();
        cout << endl;
#endif
        parent = parent->parent_;
      }
    }
    cout << "Program #" << program_nr << "\nRuntime = ";
    parent->print_complexity();
    cout << "\n\n";
    delete parent;
  }
  return 0;
}

UVa 10742 - The New Rule in Euphomia

Accepted date: 2014-11-20
Ranking (as of 2014-11-20): 106 out of 537
Language: C++

/*
  UVa 10742 - The New Rule in Euphomia

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

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

const int n_max = 1000000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int nr_primes, primes[n_max]; // primes[i] is the i-th prime number
long long nr_ways[n_max + 1];
  // nr_ways[primes[i]] is the number of ways for prime number i

void sieve_of_eratosthenes()
{
  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();
  long long m = 0, s = 0;
  for (int i = 2; i <= n_max; i++)
    if (!not_primes[i]) {
      primes[nr_primes++] = i;
      s += m++;
      nr_ways[i] = s;
    }
  primes[nr_primes++] = n_max; // sentinel
#ifdef DEBUG
  printf("%d %d %lld\n",
    nr_primes, primes[nr_primes - 1], nr_ways[primes[nr_primes - 1]]);
  for (int i = 0; primes[i] < 100; i++)
    printf("%d %lld\n", primes[i], nr_ways[primes[i]]);
#endif
  for (int case_nr = 1; ; case_nr++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    long long nr = 0;
    // locate the largest prime that is less than (n - 1)
    int i = distance(primes, lower_bound(primes, primes + nr_primes, n - 2));
    if (primes[i] > n - 2)
      i--;
    for ( ; i > 0 && n - primes[i] < primes[i - 1]; i--) {
      // locate the largest prime that is equal to or less than (n - primes[i])
      int j = distance(primes,
        lower_bound(primes, primes + nr_primes, n - primes[i]));
      if (primes[j] > n - primes[i])
        j--;
      if (j > 0)
        nr += nr_ways[primes[j]] - nr_ways[primes[j - 1]] + 1;
      else if (j == 0)
        nr++;
#ifdef DEBUG
      if (j >= 0)
        printf("%d %d, %lld\n", primes[i], primes[j], nr);
      else
        printf("%d, %lld\n", primes[i], nr);
#endif
    }
    if (i > 0)
      nr += nr_ways[primes[i]];
    printf("Case %d: %lld\n", case_nr, nr);
  }
  return 0;
}

UVa 10554 - Calories from Fat

Accepted date: 2014-11-15
Ranking (as of 2014-11-15): 109 out of 525
Language: C++

/*
  UVa 10554 - Calories from Fat

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

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

int main()
{
  const int nr_nutritions = 5;
  const int calories_per_g[nr_nutritions] = {9, 4, 4, 4, 7};

  while (true) {
    string s;
    getline(cin, s);
    if (s[0] == '-')
      break;
    double fat = 0.0, total = 0.0, calories[nr_nutritions];
    while (true) {
      istringstream iss(s);
      double p = 100.0, c = 0.0;
      for (int i = 0; i < nr_nutritions; i++) {
        int q;
        char u;
        iss >> q >> u;
        switch (u) {
        case 'g':
          calories[i] = q * calories_per_g[i];
          c += calories[i];
          break;
        case 'C':
          calories[i] = q;
          c += q;
          break;
        case '%':
          calories[i] = -q;
          p -= q;
          break;
        }
      }
      double t = 0.0;
      if (p < 100.0) { // some are represented by %
        t = 100.0 * c / p; // total calories
        for (int i = 0; i < nr_nutritions; i++) {
          if (calories[i] < 0.0)
            calories[i] = t * (-calories[i]) /100.0;
#ifdef DEBUG
          cout << calories[i] << ' ';
#endif
        }
#ifdef DEBUG
        cout << t << endl;
#endif
      }
      else {
        for (int i = 0; i < nr_nutritions; i++) {
#ifdef DEBUG
          cout << calories[i] << ' ';
#endif
          t += calories[i];
        }
#ifdef DEBUG
        cout << t << endl;
#endif
      }
      fat += calories[0];
      total += t;
      getline(cin, s);
      if (s[0] == '-')
        break;
    }
    cout << fixed << setprecision(0) << fat * 100.0 / total << "%\n";
  }
  return 0;
}

UVa 10616 - Divisible Group Sums

Accepted date: 2014-11-11
Ranking (as of 2014-11-11): 84 out of 1192
Language: C++

/*
  UVa 10616 - Divisible Group Sums

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

#include <cstdio>

const int N_max = 200, D_max = 20, M_max = 10;
int integers[N_max + 1];
long long nr_ways[N_max + 1][M_max + 1][D_max];
  // nr_ways[i][j][k] is the number of ways 
  // where sum of j integers out of i has the modulo value of k
  // 1 <= i <= N, 1 <= j <= M, 0 <= k < D

int main()
{
  for (int s = 1; ; s++) {
    int N, Q;
    scanf("%d %d", &N, &Q);
    if (!N && !Q)
      break;
    for (int i = 1; i <= N; i++)
      scanf("%d", &integers[i]);
    printf("SET %d:\n", s);
    for (int q = 1; q <= Q; q++) {
      int D, M;
      scanf("%d %d", &D, &M);

      for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
          for (int k = 0; k < D; k++)
            nr_ways[i][j][k] = 0;
      for (int i = 1; i <= N; i++) {
        for (int k = 0; k < D; k++)
          nr_ways[i][1][k] = nr_ways[i - 1][1][k];
        int r = integers[i] % D;
        if (r < 0)
          r += D;
        nr_ways[i][1][r]++;
        for (int j = 2; j <= N && j <= M; j++)
          for (int k = 0; k < D; k++)
            nr_ways[i][j][(r + k) % D] = nr_ways[i - 1][j][(r + k) % D] +
              nr_ways[i - 1][j - 1][k];
#ifdef DEBUG
        for (int j = 1; j <= N && j <= M; j++)
          for (int k = 0; k < D; k++)
            printf("[%d][%d][%d]: %lld%c", i, j, k,
              nr_ways[i][j][k], ((k < D - 1) ? ' ' : '\n'));
#endif
      }
      printf("QUERY %d: %lld\n", q, nr_ways[N][M][0]);
    }
  }
  return 0;
}

UVa 662 - Fast Food

Accepted date: 2014-11-08
Ranking (as of 2014-11-08): 236 out of 630
Language: C++

/*
  UVa 662 - Fast Food

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

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

const int n_max = 200, k_max = 30;

int distances[n_max + 1];

struct cost { // shopping cost
  int c_; // cost
  int di_; // index of the depot

  cost() {}
  cost(int c, int di) : c_(c), di_(di) {}
  cost& operator=(const cost& c) {c_ = c.c_; di_ = c.di_; return *this;}
};

cost costs[n_max + 1][n_max + 1];
  // costs[i][j]j is the shopping cost for restaurants i and j
cost min_costs[n_max + 1][n_max + 1][k_max + 1];
  // min_cost[i][j][k] is the min. shopping cost for restaurants i and j with k depots

#ifdef DEBUG
void print_costs(int n)
{
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      printf("{%d %d}%c", costs[i][j].c_, costs[i][j].di_, ((j < n) ? ' ' : '\n'));
  putchar('\n');
}
#endif

void calculate_costs(int n)
{
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
      cost& c = costs[i][j];
      c.di_ = (i + j) / 2; // median
      int d = distances[c.di_];
      c.c_ = 0;
      for (int x = i; x <= j; x++)
        c.c_ += abs(distances[x] - d);
    }
}

#ifdef DEBUG
void print_min_costs(int n, int k)
{
  printf("k: %d\n", k);
  for (int i = 1; i <= n; i++)
    printf("{%d %d}%c",min_costs[i][n][k].c_, min_costs[i][n][k].di_,
      ((i < n) ? ' ' : '\n'));
  putchar('\n');
}
#endif

void partition(int n, int k)
{
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      min_costs[i][j][1] = costs[i][j];
  for (int j = 1; j <= n; j++)
    min_costs[1][j][1] = costs[1][j];
#ifdef DEBUG
  print_min_costs(n, 1);
#endif
  for (int x = 2; x <= k; x++) {
    for (int i = 1; i <= n - x; i++) {
      int c = numeric_limits<int>::max(), di;
      for (int j = i; j <= n - x + 1; j++) {
#ifdef DEBUG
        printf("{%d-%d: %d} ", i, j, costs[i][j].c_ + min_costs[j + 1][n][x - 1].c_);
#endif
        if (costs[i][j].c_ + min_costs[j + 1][n][x - 1].c_ < c) {
          c = costs[i][j].c_ + min_costs[j + 1][n][x - 1].c_;
          di = j;
        }
      }
      min_costs[i][n][x] = cost(c, di);
#ifdef DEBUG
      printf("{%d %d}\n", min_costs[i][n][x].c_, min_costs[i][n][x].di_);
#endif
    }
    min_costs[n - x + 1][n][x] = cost(0, n - x + 1);
#ifdef DEBUG
    print_min_costs(n, x);
#endif
  }
}

void print_partition(int x, int i, int j, int di)
{
  if (i != j)
    printf("Depot %d at restaurant %d serves restaurants %d to %d\n", x, di, i, j);
  else
    printf("Depot %d at restaurant %d serves restaurant %d\n", x, di, i);
}

void print_partitions(int n, int i, int k, int x)
{
  int j = min_costs[i][n][k - x + 1].di_;
  if (x < k) {
    print_partition(x, i, j, costs[i][j].di_);
    print_partitions(n, j + 1, k, x + 1);
  }
  else
    print_partition(x, i, n, j);
}

int main()
{
  for (int chain_nr = 1; ; chain_nr++) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (!n && !k)
      break;
    for (int i = 1; i <= n; i++)
      scanf("%d", &distances[i]);
    printf("Chain %d\n", chain_nr);
    if (k == n) {
      for (int i = 1; i <= n; i++)
        print_partition(i, i, i, i);
      puts("Total distance sum = 0");
    }
    else {
      calculate_costs(n);
#ifdef DEBUG
      print_costs(n);
#endif
      if (k == 1) {
        print_partition(k, 1, n, costs[1][n].di_);
        printf("Total distance sum = %d\n", costs[1][n].c_);
      }
      else {
        partition(n, k);
        print_partitions(n, 1, k, 1);
        printf("Total distance sum = %d\n", min_costs[1][n][k].c_);
      }
    }
    putchar('\n');
  }
  return 0;
}

UVa 10913 - Walking on a Grid

Accepted date: 2014-11-05
Ranking (as of 2014-11-05): 30 out of 594
Language: C++

/*
  UVa 10913 - Walking on a Grid

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

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

const int infinite = numeric_limits<int>::min();
const int N_max = 75, k_max = 5;
int grid[N_max][N_max];
int paths[N_max][N_max][k_max + 1];
  // paths[i][j][k] is the max. sum of integers to square (i, j) with 
  // k negative integers, or infinite if it is impossible to reach the square
int paths_from_left[N_max][k_max + 1], paths_from_right[N_max][k_max + 1];

#ifdef DEBUG

void print_paths(int N, int k, int r)
{
  for (int c = 0; c < N; c++) {
    cout << '[';
    for (int i = 0; i <= k; i++)
      cout << paths[r][c][i] << ((i < k) ? " " : "] ");
  }
  cout << endl;
}

void print_paths(int N, int k, int p[N_max][k_max + 1])
{
  for (int c = 0; c < N; c++) {
    cout << '[';
    for (int i = 0; i <= k; i++)
      cout << p[c][i] << ((i < k) ? " " : "] ");
  }
  cout << endl;
}

#endif

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int N, k;
    cin >> N >> k;
    if (!N && !k)
      break;
    for (int r = 0; r < N; r++)
      for (int c = 0; c < N; c++) {
        cin >> grid[r][c];
        for (int i = 0; i <= k; i++)
          paths[r][c][i] = infinite;
      }

    for (int i = 0, j = (grid[0][0] < 0) ? 1 : 0; i + j <= k; i++)
      paths[0][0][i + j] = grid[0][0];
    for (int c = 1; c < N; c++) // the first row
      for (int i = 0, j = (grid[0][c] < 0) ? 1 : 0; i + j <= k; i++)
        if (paths[0][c - 1][i] != infinite)
          paths[0][c][i + j] = paths[0][c - 1][i] + grid[0][c];
#ifdef DEBUG
    print_paths(N, k, 0);
#endif
    for (int r = 1; r < N; r++) { // between the second and the last row
      for (int c = 0; c < N; c++)
        for (int i = 0; i <= k; i++)
          paths_from_left[c][i] = paths_from_right[c][i] = infinite;
      for (int c = 0; c < N; c++)
        for (int i = 0, j = (grid[r][c] < 0) ? 1 : 0; i + j <= k; i++) {
          int p = infinite;
          if (r)
            p = max(p, paths[r - 1][c][i]);
          if (c)
            p = max(p, paths_from_left[c - 1][i]);
          if (p != infinite)
            paths_from_left[c][i + j] = p + grid[r][c];
        }
      for (int c = N - 1; c >= 0; c--)
        for (int i = 0, j = (grid[r][c] < 0) ? 1 : 0; i + j <= k; i++) {
          int p = infinite;
          if (r)
            p = max(p, paths[r - 1][c][i]);
          if (c < N - 1)
            p = max(p, paths_from_right[c + 1][i]);
          if (p != infinite)
            paths_from_right[c][i + j] = p + grid[r][c];
        }
#ifdef DEBUG
        print_paths(N, k, paths_from_left);
        print_paths(N, k, paths_from_right);
#endif
      for (int c = 0; c < N; c++)
        for (int i = 0; i <= k; i++)
          paths[r][c][i] = max(paths_from_left[c][i], paths_from_right[c][i]);
#ifdef DEBUG
      print_paths(N, k, r);
#endif
    }
    int max_path = infinite;
    for (int i = 0; i <= k; i++)
      max_path = max(max_path, paths[N - 1][N - 1][i]);
    cout << "Case " << case_nr << ": ";
    if (max_path != infinite)
      cout << max_path << endl;
    else
      cout << "impossible\n";
  }
  return 0;
}

UVa 604 - The Boggle Game

Accepted date: 2014-10-27
Ranking (as of 2014-10-27): 27 out of 445
Language: C++

/*
  UVa 604 - The Boggle Game

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

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

const int nr_rows = 4, nr_columns = 4;
const int nr_letters = 4;

char first_board[nr_rows][nr_columns], second_board[nr_rows][nr_columns];
bool visited[nr_rows][nr_columns];

struct pigewu {
  char s_[nr_letters + 1];

  bool operator<(const pigewu& p) const {return strcmp(s_, p.s_) < 0;}
};

inline bool is_vowel(char c)
{
  return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'Y';
}

void boggle(int r, int c, int l, int vl, pigewu& p, char board[nr_rows][nr_columns],
  set<pigewu>& pigewus)
{
  const int nr_dirs = 8;
  const int dirs[nr_dirs][2] =
    {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

  p.s_[l++] = board[r][c];
  if (is_vowel(p.s_[l - 1]))
    vl++;
  visited[r][c] = true;
  if (l == nr_letters) {
    p.s_[nr_letters] = '\0';
    pigewus.insert(p);
  }
  else {
    for (int i = 0; i < nr_dirs; i++) {
      int nr = r + dirs[i][0], nc = c + dirs[i][1];
      if (nr < 0 || nr >= nr_rows || nc < 0 || nc >= nr_columns || visited[nr][nc])
        continue;
      bool vowel = is_vowel(board[nr][nc]);
      if (vl == 2 && vowel || l == 2 && vl == 0 && !vowel ||
        l == 3 && vl == 1 && !vowel)
        continue;
      boggle(nr, nc, l, vl, p, board, pigewus);
    }
  }
  visited[r][c] = false;
}

int main()
{
  bool printed = false;
  while (true) {
    char c;
    cin >> c;
    if (c == '#')
      break;
    cin.unget();
    if (printed)
      cout << endl;
    else
      printed = true;
    for (int r = 0; r < nr_rows; r++) {
      for (int c = 0; c < nr_columns; c++)
        cin >> first_board[r][c];
      for (int c = 0; c < nr_columns; c++)
        cin >> second_board[r][c];
    }
    pigewu p;
    set<pigewu> first_pigewus, second_pigewus;
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++) {
        memset(visited, 0, sizeof(visited));
        boggle(r, c, 0, 0, p, first_board, first_pigewus);
        memset(visited, 0, sizeof(visited));
        boggle(r, c, 0, 0, p, second_board, second_pigewus);
      }

    size_t nr_first_pigewus = first_pigewus.size(),
      nr_secont_pigewus = second_pigewus.size();
    bool found = false;
    if (nr_first_pigewus && nr_secont_pigewus) {
      if (nr_first_pigewus > nr_secont_pigewus) {
        for (set<pigewu>::const_iterator i = second_pigewus.begin(),
          e = second_pigewus.end(); i != e; ++i)
          if (first_pigewus.find(*i) != first_pigewus.end()) {
            found = true;
            cout << i->s_ << endl;
          }
      }
      else {
        for (set<pigewu>::const_iterator i = first_pigewus.begin(),
          e = first_pigewus.end(); i != e; ++i)
          if (second_pigewus.find(*i) != second_pigewus.end()) {
            found = true;
            cout << i->s_ << endl;
          }
      }
    }
    if (!found)
      cout << "There are no common words for this pair of boggle boards.\n";
  }
  return 0;
}

UVa 726 - Decode

Accepted date: 2014-10-24
Ranking (as of 2014-10-24): 101 out of 271
Language: C++

/*
  UVa 726 - Decode

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

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

const int nr_letters = 26;

struct letter {
  int i_, f_;

  letter() {}

  bool operator<(const letter& l) {return (f_ != l.f_) ? f_ > l.f_ : i_ < l.i_;}
};

#ifdef DEBUG
void print_letter_freqs(const vector<letter>& freqs)
{
  for (int i = 0; i < nr_letters; i++)
    if (freqs[i].f_)
      cout << static_cast<char>(freqs[i].i_ + 'a') << ' ';
  cout << endl;
}
#endif

int main()
{
  vector<letter> known_freqs(nr_letters);
  vector<letter> encoded_freqs(nr_letters);
  for (int i = 0; i < nr_letters; i++) {
    known_freqs[i].i_ = encoded_freqs[i].i_ = i;
    known_freqs[i].f_ = encoded_freqs[i].f_ = 0;
  }
  vector<string> known;
  string s;
  while (true) {
    getline(cin, s);
    if (s.empty())
      break;
    known.push_back(s);
    for (const char* p = s.c_str(); *p; p++)
      if (isalpha(*p))
        known_freqs[tolower(*p) - 'a'].f_++;
  }
  vector<string> encoded;
  while (getline(cin, s)) {
    encoded.push_back(s);
    for (const char* p = s.c_str(); *p; p++)
      if (isalpha(*p))
        encoded_freqs[tolower(*p) - 'a'].f_++;
  }
  sort(known_freqs.begin(), known_freqs.end());
  sort(encoded_freqs.begin(), encoded_freqs.end());
#ifdef DEBUG
  print_letter_freqs(known_freqs);
  print_letter_freqs(encoded_freqs);
#endif
  vector<char> mappings(nr_letters);
  for (int i = 0; i < nr_letters; i++)
    mappings[encoded_freqs[i].i_] = 'a' + known_freqs[i].i_;
  for (size_t i = 0, n = encoded.size(); i < n; i++) {
    ostringstream oss;
    for (const char* p = encoded[i].c_str(); *p; p++)
      if (isupper(*p))
        oss << static_cast<char>(toupper(mappings[*p - 'A']));
      else if (islower(*p))
        oss << mappings[*p - 'a'];
      else
        oss << *p;
    cout << oss.str() << endl;
  }
  return 0;
}

UVa 962 - Taxicab Numbers

Accepted date: 2014-10-21
Ranking (as of 2014-10-21): 143 out of 358
Language: C++

/*
  UVa 962 - Taxicab Numbers

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

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

int main()
{
  const int nr_cubes_max = 1000;
  const int n1_max = 1000000000, rg_max = 100000;
  vector<int> cubes(nr_cubes_max);
  for (int i = 1; i <= nr_cubes_max; i++)
    cubes[i - 1] = i * i * i;
  map<int, int> sums_of_cubes;
  for (int i = 0; i < nr_cubes_max; i++)
    for (int j = i; j < nr_cubes_max; j++) {
      int s = cubes[i] + cubes[j];
      if (s <= n1_max + rg_max) {
        pair<map<int, int>::iterator, bool> result =
          sums_of_cubes.insert(make_pair(s, 1));
        if (!result.second)
          result.first->second++;
      }
    }
  vector<int> taxicab_numbers;
  for (map<int, int>::const_iterator si = sums_of_cubes.begin(),
    se = sums_of_cubes.end(); si != se; ++si)
    if (si->second >= 2)
      taxicab_numbers.push_back(si->first);
#ifdef DEBUG
  printf("%d %d\n",
    taxicab_numbers.size(), taxicab_numbers[taxicab_numbers.size() - 1]);
#endif
  int n1, rg;
  while (scanf("%d %d", &n1, &rg) != EOF) {
    vector<int>::iterator li =
      lower_bound(taxicab_numbers.begin(), taxicab_numbers.end(), n1),
      ui = upper_bound(taxicab_numbers.begin(), taxicab_numbers.end(), n1 + rg);
    if (li == ui)
      puts("None");
    else {
      for (; ui != li; ++li)
        printf("%d\n", *li);
    }
  }
  return 0;
}

UVa 10389 - Subway

Accepted date: 2014-10-19
Ranking (as of 2014-10-20): 67 out of 381
Language: C++

/*
  UVa 10389 - Subway

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

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <limits>
#include <cmath>
#include <cstdlib>
using namespace std;

struct point {
  int x_, y_;
  int sl_; // subway line number
  int ss_; // subway station number
};

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x_ - b.x_, dy = a.y_ - b.y_;
  return sqrt(dx * dx + dy * dy);
}

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

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

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int nr_cases;
  iss >> nr_cases;
  iss.clear();
  getline(cin, line); // skip a blank line
  while (nr_cases--) {
    getline(cin, line);
    iss.str(line);
    vector<point> points;
    point s, e;
    s.sl_ = 0; e.sl_ = 1; s.ss_ = e.ss_ = -1;
    iss >> s.x_ >> s.y_ >> e.x_ >> e.y_;
    points.push_back(s);
    points.push_back(e);
    iss.clear();
    for (int sl = 2; getline(cin, line) && !line.empty(); sl++) {
      iss.str(line);
      point p;
      p.sl_ = sl;
      for (int ss = 0; ; ss++) {
        iss >> p.x_ >> p.y_;
        if (p.x_ == -1)
          break;
        p.ss_ = ss;
        points.push_back(p);
      }
      iss.clear();
    }
    const double walk = 10000.0 / 60.0, subway = 40000.0 / 60.0;
    int n = static_cast<int>(points.size());
    vector< vector<edge> > edges(n);
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++) {
        double d;
        if (points[i].sl_ == points[j].sl_)  {
          // two points are on the same subway line
          if (abs(points[i].ss_ - points[j].ss_) == 1) {
            // station i and station j are adjacent
            d = euclidean_distance(points[i], points[j]) / subway;
            edges[i].push_back(edge(j, d));
            edges[j].push_back(edge(i, d));
          }
        }
//        else {
          d = euclidean_distance(points[i], points[j]) / walk;
          edges[i].push_back(edge(j, d));
          edges[j].push_back(edge(i, d));
//        }
      }

    // apply Dijkstra's shortest path
    vector<double> distances(n, numeric_limits<double>::max());
    vector<bool> visited(n, false);
    set<int, distance_comparator> pq(distances); // priority queue
    distances[0] = 0.0;
    pq.insert(0);
    while (!pq.empty()) {
      int u = *pq.begin();
      pq.erase(pq.begin());
      visited[u] = true;
      if (u == 1)
        break;
      const vector<edge>& es = edges[u];
      for (size_t i = 0, j = es.size(); i < j; i++) {
        const edge& e = es[i];
        if (!visited[e.v_] && distances[e.v_] > distances[u] + e.w_) {
          pq.erase(e.v_); // remove vt if it has already been in the queue
            // this must be done before updating distances[]
          distances[e.v_] = distances[u] + e.w_;
          pq.insert(e.v_);
        }
      }
    }
    cout << fixed << setprecision(0) << distances[1] << endl;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 10724 - Road Construction

Accepted date: 2014-10-17
Ranking (as of 2014-10-17): 80 out of 310
Language: C++

/*
  UVa 10724 - Road Construction

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

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

const double infinite = numeric_limits<int>::max(),
  epsilon = numeric_limits<double>::epsilon();

struct point {
  double x_, y_;
};

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x_ - b.x_, dy = a.y_ - b.y_;
  return sqrt(dx * dx + dy * dy);
}

int main()
{
  while (true) {
    int N, M;
    cin >> N >> M;
    if (!N && !M)
      break;
    vector<point> points(N + 1);
    for (int i = 1; i <= N; i++)
      cin >> points[i].x_ >> points[i].y_;
    vector< vector<bool> > roads(N + 1, vector<bool>(N + 1, false));
    vector< vector<double> > matrix(N + 1, vector<double>(N + 1, infinite));
    for (int i = 1; i <= N; i++)
      matrix[i][i] = 0.0;
    while (M--) {
      int i, j;
      cin >> i >> j;
      roads[i][j] = roads[j][i] = true;
      matrix[i][j] = matrix[j][i] = euclidean_distance(points[i], points[j]);
    }

    // apply Floyd-Warshall all-pairs shortest path algorithm
    for (int k = 1; k <= N; k++)
      for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
          if (matrix[i][k] + matrix[k][j] < matrix[i][j])
            matrix[i][j] = matrix[i][k] + matrix[k][j];

    double max_cuv = 1.0;
    int max_u, max_v;
    for (int u = 1; u < N; u++)
      for (int v = u + 1; v <= N; v++) {
        if (roads[u][v])
          continue;
        double cuv = 0.0, duv = euclidean_distance(points[u], points[v]);
        for (int i = 1; i <= N; i++)
          for (int j = 1; j <= N; j++) {
            double d = matrix[i][j] - min(matrix[i][u] + matrix[v][j] + duv,
              matrix[i][v] + matrix[u][j] + duv);
            if (d > epsilon)
              cuv += d;
          }
        if (cuv - 1.0 > epsilon && cuv - max_cuv > epsilon) {
          max_cuv = cuv; max_u = u; max_v = v;
        }
      }
    if (max_cuv - 1.0 > epsilon)
      cout << max_u << ' ' << max_v << endl;
    else
      cout << "No road required\n";
  }
  return 0;
}

UVa 11049 - Basic wall maze

Accepted date: 2014-10-13
Ranking (as of 2014-10-13): 483 out of 575
Language: C++

/*
  UVa 11049 - Basic wall maze

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

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

const int nr_rows = 6, nr_columns = 6;
/*
enum {dir_s, dir_n, dir_e, dir_w};
const int nr_dirs = 4;
const char cdirs[nr_dirs] = {'S', 'N', 'E', 'W'};
const int dirs[nr_dirs][2] = {{1, 0}, {-1, 0}, {0, 1}, { 0, -1}};
*/
enum {dir_e, dir_w, dir_n, dir_s};
const int nr_dirs = 4;
const char cdirs[nr_dirs] = {'E', 'W', 'N', 'S'};
const int dirs[nr_dirs][2] = {{0, 1}, { 0, -1}, {-1, 0}, {1, 0}};

bool walls[nr_rows][nr_columns][nr_dirs];
bool visited[nr_rows][nr_columns];
pair<int, int> parents[nr_rows][nr_columns];

void print_path(const pair<int, int>& s)
{
  const pair<int, int>& ps = parents[s.first][s.second];
  if (ps.first != -1) {
    print_path(ps);
    int dir;
    if (ps.first < s.first)
      dir = dir_s;
    else if (ps.first > s.first)
      dir = dir_n;
    else if (ps.second < s.second)
      dir = dir_e;
    else
      dir = dir_w;
    putchar(cdirs[dir]);
  }
}

int main()
{
  while (true) {
    pair<int, int> ss, se;
    scanf("%d %d", &ss.second, &ss.first);
    if (!ss.first && !ss.second)
      break;
    ss.first--; ss.second--;
    scanf("%d %d", &se.second, &se.first);
    se.first--; se.second--;
    memset(walls, 0, sizeof(walls));
    for (int i = 0; i < 3; i++) {
      pair<int, int> ws, we;
      scanf("%d %d %d %d", &ws.second, &ws.first, &we.second, &we.first);
      if (ws.first == we.first) { // horizontal wall
        if (ws.first)
          for (int c = ws.second; c < we.second; c++)
            walls[ws.first - 1][c][dir_n] = true;
        if (ws.first < nr_rows)
          for (int c = ws.second; c < we.second; c++)
            walls[ws.first][c][dir_s] = true;
      }
      else { // vertical wall
        if (ws.second)
          for (int r = ws.first; r < we.first; r++)
            walls[r][ws.second - 1][dir_w] = true;
        if (ws.second < nr_columns)
          for (int r = ws.first; r < we.first; r++)
            walls[r][ws.second][dir_e] = true;
      }
    }

    // breadth first search
    memset(visited, 0, sizeof(visited));
    queue< pair<int, int> > sq;
    visited[ss.first][ss.second] = true;
    parents[ss.first][ss.second] = make_pair(-1, -1);
    sq.push(ss);
    while (!sq.empty()) {
      pair<int, int> s = sq.front(); sq.pop();
      if (s == se)
        break;
      for (int i = 0; i < nr_dirs; i++) {
        int r = s.first + dirs[i][0], c = s.second + dirs[i][1];
        if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns &&
          !walls[r][c][i] && !visited[r][c]) {
          visited[r][c] = true;
          parents[r][c] = s;
          sq.push(make_pair(r, c));
        }
      }
    }
    print_path(se);
    putchar('\n');
  }
  return 0;
}

UVa 10686 - SQF Problems

Accepted date: 2014-10-08
Ranking (as of 2014-10-08): 108 out of 222
Language: C++

/*
  UVa 10686 - SQF Problems

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10686_SQF_Problems.cpp

  Ugly.
*/

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

const int C_max = 20, W_max = 10;

struct category {
  string name_;
  int nr_keywords_, nr_appear_;
  bool keywords_[W_max];

  category() {}
} categories[C_max];

bool is_duplicated_keyword(int ci, const string& w,
  multimap< string, pair<int, int> >& keywords)
{
  pair < multimap<string, pair<int, int> >::iterator, 
    multimap<string, pair<int, int> >::iterator > result = keywords.equal_range(w);
  for (multimap<string, pair<int, int> >::iterator i = result.first;
    i != result.second; ++i)
    if (i->second.first == ci)
      return true;
  return false;
}

char remove_nonalpha(char c)
{
  return (isalpha(c)) ? c : ' ';
}

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int N;
  iss >> N;
  iss.clear();
  while (N--) {
    getline(cin, line);
    iss.str(line);
    int C;
    iss >> C;
    iss.clear();
    multimap< string, pair<int, int> > keywords;
      // key is a keyword, value is the index pair to categories[i].keywords_[j]
    for (int i = 0; i < C; i++) {
      category& c = categories[i];
      getline(cin, line);
      iss.str(line);
      iss >> c.name_ >> c.nr_keywords_ >> c.nr_appear_;
      iss.clear();
      for (int j = 0; j < c.nr_keywords_; ) {
        getline(cin, line);
        iss.str(line); // to remove blanks
        string w;
        iss >> w;
        iss.clear();
        if (is_duplicated_keyword(i, w, keywords))
          c.nr_keywords_--;
        else {
          keywords.insert(make_pair(w, make_pair(i, j)));
          c.keywords_[j] = false;
          j++;
        }
      }
    }
#ifdef DEBUG
    for (multimap<string, pair<int, int> >::const_iterator 
      ki = keywords.begin(), ke = keywords.end(); ki != ke; ++ki)
      cout << ki->first << " (" << ki->second.first <<
        ", " << ki->second.second << ")\n";
#endif
    while (getline(cin, line) && !line.empty()) {
      transform(line.begin(), line.end(), line.begin(), remove_nonalpha);
        // replace non-alpha chars with spaces
      iss.str(line);
      string w;
      while (iss >> w) {
        pair < multimap<string, pair<int, int> >::iterator, 
          multimap<string, pair<int, int> >::iterator > result =
            keywords.equal_range(w);
        for (multimap<string, pair<int, int> >::iterator i = result.first;
          i != result.second; ++i)
          categories[i->second.first].keywords_[i->second.second] = true;
      }
      iss.clear();
    }
    bool sqf = true;
    for (int i = 0; i < C; i++) {
      const category& c = categories[i];
      int nr_appear = 0;
      for (int j = 0; j < c.nr_keywords_; j++)
        if (c.keywords_[j])
          nr_appear++;
      if (nr_appear >= c.nr_appear_) {
        if (!sqf)
          cout << ',';
        else
          sqf = false;
        cout << c.name_;
#ifdef DEBUG
        cout << " (" << nr_appear << ")";
#endif
      }
    }
    if (sqf)
      cout << "SQF Problem.\n";
    else
      cout << endl;
  }
  return 0;
}

UVa 11507 - Bender B. Rodríguez Problem

Accepted date: 2014-10-06
Ranking (as of 2014-10-06): 160 out of 693
Language: C++

/*
  UVa 11507 - Bender B. Rodriguez Problem

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

#include <cstdio>

struct point {
  int x_, y_, z_;
  point() {}
  point(int x, int y, int z) : x_(x), y_(y), z_(z) {}
  point(const point& p) : x_(p.x_), y_(p.y_), z_(p.z_) {}
};

struct rotation {
  const char* s_;
  int matrix_[3][3];
} rotations[] = {
  {"+y", {{0, -1, 0}, {1, 0, 0}, {0, 0, 1}}}, // Rz(90 degree)
  {"-y", {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}}}, // Rz(-90 degree)
  {"+z", {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}}}, // Ry(-90 degree)
  {"-z", {{0, 0, 1}, {0, 1, 0}, {-1, 0, 0}}}  // Ry(90 degree)
};

point rotate_point(const point& o, const point& p, const char* s)
{
  int ri = (s[1] - 'y') * 2;
  if (s[0] == '-')
    ri++;
  const rotation& r = rotations[ri];
  point q(p.x_ - o.x_, p.y_ - o.y_, p.z_ - o.z_);
  point result;
  result.x_ =
    o.x_ + r.matrix_[0][0] * q.x_ + r.matrix_[0][1] * q.y_ + r.matrix_[0][2] * q.z_;
  result.y_ =
    o.y_ + r.matrix_[1][0] * q.x_ + r.matrix_[1][1] * q.y_ + r.matrix_[1][2] * q.z_;
  result.z_ =
    o.z_ + r.matrix_[2][0] * q.x_ + r.matrix_[2][1] * q.y_ + r.matrix_[2][2] * q.z_;
  return result;
}

int main()
{
  while (true) {
    int L;
    scanf("%d", &L);
    if (!L)
      break;
    // remember the last (left-most) point and the next to last point
    // rotate both points around j-th point
    char s[2];
    point p(L - 1, 0, 0), q(L, 0, 0);
    L--;
    while (true) {
      scanf("%s", s);
      if (s[0] != 'N') { // "No"
        q = rotate_point(p, q, s);
        break;
      }
      if (L == 1)
        break;
      L--; p.x_--;
    }
#ifdef DEBUG
    printf("(%d, %d, %d) (%d, %d, %d)\n", p.x_, p.y_, p.z_, q.x_, q.y_, q.z_);
#endif
    while (L-- > 1) {
      point o(L, 0, 0);
      scanf("%s", s);
      if (s[0] != 'N') {
        p = rotate_point(o, p, s);
        q = rotate_point(o, q, s);
#ifdef DEBUG
        printf("(%d, %d, %d) (%d, %d, %d)\n", p.x_, p.y_, p.z_, q.x_, q.y_, q.z_);
#endif
      }
    }
    if (p.x_ != q.x_)
      printf((p.x_ < q.x_) ? "+x\n": "-x\n");
    else if (p.y_ != q.y_)
      printf((p.y_ < q.y_) ? "+y\n": "-y\n");
    else
      printf((p.z_ < q.z_) ? "+z\n": "-z\n");
  }
  return 0;
}

UVa 10564 - Paths through the Hourglass

Accepted date: 2014-09-30
Ranking (as of 2014-09-30): 30 out of 599
Language: C++

/*
  UVa 10564 - Paths through the Hourglass

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

#include <cstdio>
#include <cstring>

/*
Let cells[r][c] is the value of cell at r-th row, c-th column, and, 
nr_paths[r][c][s] is the number of paths that leads to cells[r][c] with 
  the path value of s, then:
  nr_paths[r][c][s] = nr_paths[r - 1][left to c][s - cells[r][c]] +
    nr_paths[r - 1][right to c][s - cells[r][c]
*/

const int N_max = 20, S_max = 500;

int cells[N_max * 2 - 1][N_max];
long long nr_paths[N_max * 2 - 1][N_max][S_max];

#ifdef DEBUG
void print_s(int N, int S, int r)
{
  printf("%d\n", r);
  for (int c = 0; c < N; c++)
    for (int s = 0; s <= S; s++)
      printf("%3lld%c", nr_paths[r][c][s], ((s < S) ? ' ' : '\n'));
  putchar('\n');
}
#endif

/*
6 41      r   cs
6 7 2 3 6 8   0   0
  1 8 0 7 1   1   1
    2 6 5 7   2   2
      3 1 0   3   3
        7 6   4   4
          8   5   5
        8 8   6   4
      6 5 3   7   3
    9 5 9 5   8   2
  6 4 4 1 3   9   1
2 6 9 4 3 8   10  0
*/

void follow_paths(int N, int S)
{
  for (int c = 0; c < N; c++)
    for (int s = 0; s <= S; s++)
      nr_paths[2 * (N - 1)][c][s] = (s == cells[2 * (N - 1)][c]) ? 1 : 0;
#ifdef DEBUG
  print_s(N, S, 2 * (N - 1));
#endif
  for (int r = 2 * (N - 1) - 1, ci = 1; r >= 0; r--, ((r >= N - 1) ? ci++ : ci--)) {
    for (int c = ci; c < N; c++) {
      int cs = cells[r][c];
      for (int s = 0; s <= S; s++) {
        if (s < cs)
          nr_paths[r][c][s] = 0;
        else {
          long long np_left, np_right;
          if (r >= N - 1) {
            np_left = nr_paths[r + 1][c - 1][s - cs]; // from lower left
            np_right = nr_paths[r + 1][c][s - cs]; // from lower right
          }
          else {
            np_left = (c > ci) ? nr_paths[r + 1][c][s - cs] : 0;
              // from lower left
            np_right = (c < N - 1) ? nr_paths[r + 1][c + 1][s - cs] : 0;
              // from lower right
          }
          nr_paths[r][c][s] = np_left + np_right;
        }
      }
    }
#ifdef DEBUG
    print_s(N, S, r);
#endif
  }
}

void trace_path(int N, int r, int c, int s, char* path)
{
  int cs;
  if (r < N - 1) {
    cs = cells[r][c];
    if (c > r && nr_paths[r + 1][c][s - cs]) { // to lower left
      path[r] = 'L';
      trace_path(N, r + 1, c, s - cs, path);
    }
    else { // to lower right
      path[r] = 'R';
      trace_path(N, r + 1, c + 1, s - cs, path);
    }
  }
  else if (r < 2 * (N - 1)) {
    cs = cells[r][c];
    if (nr_paths[r + 1][c - 1][s - cs]) { // to lower left
      path[r] = 'L';
      trace_path(N, r + 1, c - 1, s - cs, path);
    }
    else { // to lower right
      path[r] = 'R';
      trace_path(N, r + 1, c, s - cs, path);
    }
  }
}

int main()
{
  while (true) {
    int N, S;
    scanf("%d %d", &N, &S);
    if (!N && !S)
      break;
    for (int r = 0, ci = 0; r < 2 * N - 1; r++, ((r < N) ? ci++ : ci--))
      for (int c = ci; c < N; c++)
        scanf("%d", &cells[r][c]);
    follow_paths(N, S);
    int first_c = -1;
    long long nr = 0;
    for (int c = 0; c < N; c++)
      if (nr_paths[0][c][S]) {
        if (first_c == -1)
          first_c = c;
        nr += nr_paths[0][c][S];
      }
    printf("%lld\n", nr);
    if (first_c != -1) {
      char path[N_max * 2 - 1];
      trace_path(N, 0, first_c, S, path);
      path[2 * (N - 1)] = '\0';
      printf("%d %s\n", first_c, path);
    }
    else
      putchar('\n');
  }
  return 0;
}

UVa 11227 - The silver bullet.

Accepted date: 2014-09-21
Ranking (as of 2014-09-21): 379 out of 594
Language: C++

/*
  UVa 11227 - The silver bullet.

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

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

const double epsilon = numeric_limits<double>::epsilon();

struct point {
  double x_, y_;

  bool operator==(const point& p) const {
    return fabs(x_ - p.x_) <= epsilon && fabs(y_ - p.y_) <= epsilon;
  }
  bool operator<(const point& p) const {
    return (x_ != p.x_) ? x_ < p.x_ : y_ < p.y_;
  }
};

struct line {
  double a_; // x-coefficient
  double b_; // y-coefficient
  double c_; // constant term

  bool operator<(const line& l) const {
    if (a_ != l.a_)
      return a_ < l.a_;
    else if (b_ != l.b_)
      return b_ < l.b_;
    else
      return c_ < l.c_;
  }
};

void points_to_line(const point& p1, const point& p2, line& l)
{
  if (fabs(p1.x_ - p2.x_) <= epsilon) {
    l.a_ = 1.0; l.b_ = 0; l.c_ = -p1.x_;
  }
  else {
    l.b_ = 1.0;
    l.a_ = -(p1.y_ - p2.y_) / (p1.x_ - p2.x_);
    l.c_ = -(l.a_ * p1.x_) - l.b_ * p1.y_;
  }
}

int main()
{
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    int N;
    cin >> N;
    vector<point> points(N);
    for (int i = 0; i < N; i++)
      cin >> points[i].x_ >> points[i].y_;
    sort(points.begin(), points.end());
    // remove the duplicate points
    for (vector<point>::iterator pi = points.begin(); pi != points.end(); ) {
      vector<point>::iterator pj = pi;
      ++pj;
      if (pj != points.end() && *pi == *pj)
        pi = points.erase(pi);
      else
        ++pi;
    }
    size_t n = points.size();
    map< line, set<point> > lines;
    for (size_t i = 0; i < n - 1; i++)
      for (size_t j = i + 1; j < n; j++) {
        line l;
        points_to_line(points[i], points[j], l);
        pair< map< line, set<point> >::iterator, bool > result =
          lines.insert(make_pair(l, set<point>()));
        result.first->second.insert(points[i]);
        result.first->second.insert(points[j]);
      }
    cout << "Data set #" << t;
    if (n > 1) {
      size_t aligned_max = 0;
      for (map< line, set<point> >::const_iterator li = lines.begin(),
        le = lines.end(); li != le; ++li)
        aligned_max = max(aligned_max, li->second.size());
      cout << " contains " << n << " gnus, out of which a maximum of " <<
        aligned_max << " are aligned.\n";
    }
    else
      cout << " contains a single gnu.\n";
  }
}

UVa 11947 - Cancer or Scorpio

Accepted date: 2014-09-15
Ranking (as of 2014-09-15): 477 out of 562
Language: JAVA

// UVa 11947 - Cancer or Scorpio

import java.util.Scanner;
import java.text.SimpleDateFormat;
import java.text.ParseException;
import java.util.Date;
import java.util.Calendar;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.ListIterator;

class Main {
  public static void main(String[] args) {
    SimpleDateFormat parseFormat = new SimpleDateFormat("MMddyyyy"),
      printFormat = new SimpleDateFormat("MM/dd/yyyy");
    Calendar cal = Calendar.getInstance();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int i = 1; i <= N; i++) {
      try {
        Date date = parseFormat.parse(sc.next());
        cal.setTime(date);
        cal.add(Calendar.WEEK_OF_YEAR, 40);
        String name = ZodiacSign.getZodiacSign(isLeapYear(cal.get(Calendar.YEAR)),
          cal.get(Calendar.DAY_OF_YEAR));
        System.out.println(i + " " + printFormat.format(cal.getTime()) + " " + name);
      }
      catch (ParseException e) {
      }
    }
  }

  static boolean isLeapYear(int year) {
      return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
  }
}

class ZodiacSign {
  final String name;
  final int begin, end;

  ZodiacSign(String name, int begin, int end) {
    this.name = name; this.begin = begin; this.end = end;
  }

  static final ArrayList<ZodiacSign> zodiacSigns =
    new ArrayList<ZodiacSign>(Arrays.asList(
      new ZodiacSign("capricorn",          1,        20),
      new ZodiacSign("aquarius",          21,   31 + 19),
      new ZodiacSign("pisces",       31 + 20,   59 + 20),
      new ZodiacSign("aries",        59 + 21,   90 + 20),
      new ZodiacSign("taurus",       90 + 21,  120 + 21),
      new ZodiacSign("gemini",      120 + 22,  151 + 21),
      new ZodiacSign("cancer",      151 + 22,  181 + 22),
      new ZodiacSign("leo",         181 + 23,  212 + 21),
      new ZodiacSign("virgo",       212 + 22,  243 + 23),
      new ZodiacSign("libra",       243 + 24,  273 + 23),
      new ZodiacSign("scorpio",     273 + 24,  304 + 22),
      new ZodiacSign("sagittarius", 304 + 23,  334 + 22),
      new ZodiacSign("capricorn",   334 + 23,  334 + 31)
  ));

  static final ArrayList<ZodiacSign> leapYearZodiacSigns =
    new ArrayList<ZodiacSign>(Arrays.asList(
      new ZodiacSign("capricorn",          1,        20),
      new ZodiacSign("aquarius",          21,   31 + 19),
      new ZodiacSign("pisces",       31 + 20,   60 + 20),
      new ZodiacSign("aries",        60 + 21,   91 + 20),
      new ZodiacSign("taurus",       91 + 21,  121 + 21),
      new ZodiacSign("gemini",      121 + 22,  152 + 21),
      new ZodiacSign("cancer",      152 + 22,  182 + 22),
      new ZodiacSign("leo",         182 + 23,  213 + 21),
      new ZodiacSign("virgo",       213 + 22,  244 + 23),
      new ZodiacSign("libra",       244 + 24,  274 + 23),
      new ZodiacSign("scorpio",     274 + 24,  305 + 22),
      new ZodiacSign("sagittarius", 305 + 23,  335 + 22),
      new ZodiacSign("capricorn",   335 + 23,  335 + 31)
  ));

  static String getZodiacSign(boolean leapYear, int dayOfYear) {
    final ArrayList<ZodiacSign> list = (leapYear) ? leapYearZodiacSigns : zodiacSigns;
    String name = "";
    for (ListIterator<ZodiacSign> i = list.listIterator(); i.hasNext(); ) {
      ZodiacSign zs = i.next();
      if (dayOfYear >= zs.begin && dayOfYear <= zs.end) {
        name = zs.name; break;
      }
    }
    return name;
  }
}

UVa 10246 - Asterix and Obelix

Accepted date: 2014-09-14
Ranking (as of 2014-09-14): 76 out of 613
Language: C++

/*
  UVa 10246 - Asterix and Obelix

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

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

const int C_max = 80;
int feasts[C_max + 1];
int fcosts[C_max + 1][C_max + 1], pcosts[C_max + 1][C_max + 1];

void floyd_warshall(int n)
{
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++) 
      if (pcosts[i][k] != numeric_limits<int>::max())
        for (int j = 1; j <= n; j++)
          if (pcosts[k][j] != numeric_limits<int>::max()) {
            if (pcosts[i][k] + pcosts[k][j] + max(fcosts[i][k], fcosts[k][j]) <
              pcosts[i][j] + fcosts[i][j]) {
              pcosts[i][j] = pcosts[i][k] + pcosts[k][j];
              fcosts[i][j] = max(fcosts[i][k], fcosts[k][j]);
            }
          }
}

int main()
{
  bool printed = false;
  for (int cn = 1; ; cn++) {
    int C, R, Q;
    scanf("%d %d %d", &C, &R, &Q);
    if (!C && !R && !Q)
      break;
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (int i = 1; i <= C; i++)
      scanf("%d", &feasts[i]);
    for (int i = 1; i <= C; i++)
      for (int j = 1; j <= C; j++)
        if (i != j) {
          pcosts[i][j] = numeric_limits<int>::max();
          fcosts[i][j] = 0;
        }
        else {
          pcosts[i][i] = 0;
          fcosts[i][i] = feasts[i];
        }

    while (R--) {
      int c1, c2, d;
      scanf("%d %d %d", &c1, &c2, &d);
      pcosts[c1][c2] = pcosts[c2][c1] = d;
      fcosts[c1][c2] = fcosts[c2][c1] = max(feasts[c1], feasts[c2]);
    }
    floyd_warshall(C);
    floyd_warshall(C);
    printf("Case #%d\n", cn);
    while (Q--) {
      int c1, c2;
      scanf("%d %d", &c1, &c2);
      int min_d = numeric_limits<int>::max();
      printf("%d\n", ((pcosts[c1][c2] != numeric_limits<int>::max()) ?
        pcosts[c1][c2] + fcosts[c1][c2] : -1));
    }
  }
  return 0;
}

UVa 545 - Heads

Accepted date: 2014-09-10
Ranking (as of 2014-09-10): 137 out of 609
Language: C++

/*
  UVa 545 - Heads

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

#include <cstdio>
#include <cmath>

const int n_max = 9000;

struct probability {
  double x_;
  int y_;
} probabilities[n_max + 1];

int main()
{
  const double eps = 1.0e-9; // without this value, the verdict was WA.
  int n, y = 0;
  double x = 1.0;
  probabilities[0].x_ = x; probabilities[0].y_ = y;
  for (n = 1; n <= n_max; n++) {
    x /= 2.0;
    if (x < 1.0) {
      x *= 10.0;
      y++;
    }
    probabilities[n].x_ = x; probabilities[n].y_ = y;
  }
  int r;
  scanf("%d", &r);
  while (r--) {
    int n;
    scanf("%d", &n);
    printf("2^-%d = %.3lfE-%d\n", n, probabilities[n].x_ + eps, probabilities[n].y_);
  }
  return 0;
}

UVa 743 - The MTM Machine

Accepted date: 2014-09-06
Language: C++

/*
  UVa 743 - The MTM Machine

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

#include <cstdio>
#include <cstring>

const int nr_digits_max = 1000;
char s[nr_digits_max + 1], t[nr_digits_max + 1];

void associate(int si, int length, char* s, char* t)
{
  if (--si >= 0 && s[si] == '3') {
    memcpy(t, s, si);
    memcpy(t + si, s + si + 1, length - si - 1);
    t[length - 1] = '2';
    memcpy(t + length, s + si + 1, length - si); // including '\0'
    associate(si, length * 2 - si - 1, t, s);
  }
  else
    puts(s);
}

bool MTM()
{
  if (strchr(s, '0'))
    return false;
  else {
    int length = strlen(s);
    for (int i = 0; i < length; i++) {
      if (s[i] == '2') {
        if (i < length - 1) {
          // remove '2'
          memcpy(t, s, i);
          memcpy(t + i, s + i + 1, length - i + 1); // including '\0'
          associate(i, length - 1, t, s); 
          return true;
        }
        else
          break;
      }
      else if (s[i] != '3')
        break;
    }
    return false;
  }
}

int main()
{
  while (true) {
    scanf("%s", s);
    if (!strcmp(s, "0"))
      break;
    if (!MTM())
      puts("NOT ACCEPTABLE");
  }
  return 0;
}

UVa 11086 - Composite Prime

Accepted date: 2014-08-31
Ranking (as of 2014-08-31): 144 out of 569
Language: C++

/*
  UVa 11086 - Composite Prime

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

/*
4
3 4 6 8

3           3 is a prime number
4 = 2 * 2
6 = 2 * 3
8 = 2 * 4   4 is an element in M

5
12 13 21 22 23

12 = 3 * 4  4 is an element in M
13          13 is a prime number
21 = 3 * 7
22 = 3 * 11
23          23 is a prime number
*/

#include <iostream>
#include <cmath>
using namespace std;

const int n_max = 1048576;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
bool not_composite_primes[n_max + 1];
  // composite_primes[i] is true if i is not a composite prime

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

void composite_primes()
{
  not_composite_primes[0] = not_composite_primes[1] =
    not_composite_primes[2] = not_composite_primes[3] = true;
  for (int i = 4; i <= n_max; i++)
    if (not_primes[i] && !not_composite_primes[i]) {
      for (int j = i * 2; j <= n_max; j += i)
        not_composite_primes[j] = true;
    }
}

int main()
{
  sieve_of_eratosthenes();
  composite_primes();
#ifdef DEBUG
  int nr_composite_primes = 0;
  for (int i = 4; i <= n_max; i++)
    if (not_primes[i] && !not_composite_primes[i])
      nr_composite_primes++;
  cout << nr_composite_primes << endl; // 219759
#endif
  int K;
  while (cin >> K) {
    int nr = 0;
    while (K--) {
      int n;
      cin >> n;
      if (not_primes[n] && !not_composite_primes[n])
        nr++;
    }
    cout << nr << endl;
  }
  return 0;
}

UVa 10520 - Determine it

Accepted date: 2014-08-29
Ranking (as of 2014-08-29): 178 out of 591
Language: C++

/*
  UVa 10520 - Determine it

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

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

const int n_max = 20;

long long a[n_max + 1][n_max + 1];

long long aij(int n, int i, int j)
{
  long long result = a[i][j];
  if (result != -1)
    return result;
  if (i < j) {
    for (int k = i; k < j; k++)
      result = max(result, aij(n, i, k) + aij(n, k + 1, j));
  }
  else {
    long long r0 = 0, r1 = 0;
    if (i < n)
      for (int k = i + 1; k <= n; k++) 
        r0 = max(r0, aij(n, k, 1) + aij(n, k, j));
    if (j > 0)
      for (int k = 1; k < j; k++)
        r1 = max(r1, aij(n, i, k) + aij(n, n, k));
    result = r0 + r1;
  }
  return a[i][j] = result;
}

int main()
{
  int n, an1;
  while (cin >> n >> an1) {
    memset(a, -1, sizeof(a));
    a[n][1] = an1;
    cout << aij(n, 1, n) << endl;
  }
  return 0;
}

UVa 941 - Permutations

Accepted date: 2014-08-26
Ranking (as of 2014-08-26): 119 out of 847
Language: C++

/*
  UVa 941 - Permutations

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

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

int main()
{
  const int nr_chars_max = 20;
  long long factorials[nr_chars_max];
    // factorials[i] is i!
  factorials[0] = factorials[1] = 1;
  for (int i = 2; i < nr_chars_max; i++)
    factorials[i] = factorials[i - 1] * i;

  int nr_samples;
  scanf("%d", &nr_samples);
  while (nr_samples--) {
    char S[nr_chars_max + 1];
    long long N;
    scanf("%s", S);
    scanf("%lld", &N);
    int length = strlen(S);
    sort(S, S + length);
    vector<char> s(S, S + length), t;
    for (int i = length - 1; i; i--) {
      int j = N / factorials[i];
      t.push_back(s[j]);
      s.erase(s.begin() + j);
      N %= factorials[i];
    }
    t.push_back(s[0]);
    t.push_back('\0');
    printf("%s\n", &t[0]);
  }
  return 0;
}

UVa 11857 - Driving Range

Accepted date: 2014-08-24
Ranking (as of 2014-08-24): 150 out of 596
Language: C++

/*
  UVa 11857 - Driving Range

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

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

const int n_max = 1000000, m_max = 1000000;
class union_find {
public:
  void init(int n);
  int find(int i) const;
  int do_union(int i, int j);
    // generate the union of the two sets to which i and j belong and 
    // return the representative of the result set
  int nr_sets() const {return s_;}

private:
  int n_; // number of elements
  int s_; // number of sets
  int representatives_[n_max]; // representatives[i] is the representative of 
    // a set to which i belongs
  int ranks_[n_max]; // ranks_[i] is the number of elements in the set 
    // to which i belongs
} vertices;

void union_find::init(int n)
{
  n_ = s_ = n;
  for (int i = 0; i < n_; i++) {
    representatives_[i] = i;
    ranks_[i] = 1;
  }
}

int union_find::find(int i) const
// return the representative of a set to which i belongs
{
  return (representatives_[i] == i) ? i : find(representatives_[i]);
}

int union_find::do_union(int i, int j)
// generate the union of the two sets to which i and j belong and 
// return the representative of the result set
{
  int ri = find(i), rj = find(j);
  if (ri == rj) // already in the same set
    return -1;
  s_--;
  if (ranks_[ri] >= ranks_[rj]) {
    ranks_[ri] += ranks_[rj];
    representatives_[rj] = ri;
    return ri;
  }
  else {
    ranks_[rj] += ranks_[ri];
    representatives_[ri] = rj;
    return rj;
  }
}

struct edge {
  int u_, v_, weight_;
  bool operator<(const edge& e) const {return weight_ < e.weight_;}
} edges[m_max];

int main()
{
  while (true) {
    int n, m;
    scanf("%d %d", &n, &m);
    if (!n && !m)
      break;
    for (int i = 0; i < m; i++)
      scanf("%d %d %d", &edges[i].u_, &edges[i].v_, &edges[i].weight_);
    // apply Kruskal's minimum spanning tree algorithm
    vertices.init(n);
    sort(edges, edges + m); // sort the edges in ascending order of their weights
    int max_cost = -1;
    for (int i = 0; i < m; i++)
      if (vertices.find(edges[i].u_) != vertices.find(edges[i].v_)) {
        vertices.do_union(edges[i].u_, edges[i].v_);
        if (vertices.nr_sets() == 1) {
          max_cost = edges[i].weight_;
          break;
        }
      }
    if (max_cost != -1)
      printf("%d\n", max_cost);
    else
      puts("IMPOSSIBLE");
  }
  return 0;
}

UVa 452 - Project Scheduling

Accepted date: 2014-08-22
Ranking (as of 2014-08-22): 224 out of 681
Language: C++

/*
  UVa 452 - Project Scheduling

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

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

const int nr_vertices = 26;
int nr_days[nr_vertices], nr_accumulated_days[nr_vertices],
  in_degrees[nr_vertices];
bool adjacency_matrix[nr_vertices][nr_vertices];

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int nr_cases;
  iss >> nr_cases;
  iss.clear();
  getline(cin, line); // skip a blank line
  while (nr_cases--) {
    memset(adjacency_matrix, 0, sizeof(adjacency_matrix));
    memset(nr_days, 0, sizeof(nr_days));
    while (getline(cin, line) && !line.empty()) {
      iss.str(line);
      char c;
      int d;
      iss >> c >> d;
      int u = c - 'A';
      nr_days[u] = d;
      while (iss >> c)
        adjacency_matrix[c - 'A'][u] = true;
      iss.clear();
    }
    memset(in_degrees, 0, sizeof(in_degrees));
    for (int u = 0; u < nr_vertices; u++)
      for (int v = 0; v < nr_vertices; v++)
        if (adjacency_matrix[u][v])
          in_degrees[v]++;
    memset(nr_accumulated_days, 0, sizeof(nr_accumulated_days));
    queue<int> q;
    for (int u = 0; u < nr_vertices; u++)
      if (nr_days[u] && !in_degrees[u]) {
        nr_accumulated_days[u] = nr_days[u];
        q.push(u);
      }
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v = 0; v < nr_vertices; v++)
        if (adjacency_matrix[u][v]) {
          nr_accumulated_days[v] = max(nr_accumulated_days[v],
            nr_accumulated_days[u] + nr_days[v]);
#ifdef DEBUG
          cout << static_cast<char>(v + 'A') << ": " <<
            nr_accumulated_days[v] << endl;
#endif
          if (!--in_degrees[v])
            q.push(v);
        }
    }
    int max_nr_accumulated_days = 0;
    for (int u = 0; u < nr_vertices; u++)
      max_nr_accumulated_days = max(max_nr_accumulated_days,
        nr_accumulated_days[u]);
    cout << max_nr_accumulated_days  << endl;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 10894 - Save Hridoy

Accepted date: 2014-08-12
Ranking (as of 2014-08-15): 12 out of 570
Language: C++

/*
  UVa 10894 - Save Hridoy

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

#include <cstdio>

const int hbanner_rows = 5, hbanner_columns = 61,
  vbanner_rows = 61, vbanner_columns = 5, N_max = 50;

char hbanner[hbanner_rows][hbanner_columns + 1] = {
  "*****..***..*...*.*****...*...*.*****.*****.***...*****.*...*",
  "*.....*...*.*...*.*.......*...*.*...*...*...*..*..*...*..*.*.",
  "*****.*****.*...*.***.....*****.*****...*...*...*.*...*...*..",
  "....*.*...*..*.*..*.......*...*.*.*.....*...*..*..*...*...*..",
  "*****.*...*...*...*****...*...*.*..**.*****.***...*****...*.."
};

char vbanner[vbanner_rows][vbanner_columns + 1] = {
  "*****",
  "*....",
  "*****",
  "....*",
  "*****",
  ".....",
  ".***.",
  "*...*",
  "*****",
  "*...*",
  "*...*",
  ".....",
  "*...*",
  "*...*",
  "*...*",
  ".*.*.",
  "..*..",
  ".....",
  "*****",
  "*....",
  "***..",
  "*....",
  "*****",
  ".....",
  ".....",
  ".....",
  "*...*",
  "*...*",
  "*****",
  "*...*",
  "*...*",
  ".....",
  "*****",
  "*...*",
  "*****",
  "*.*..",
  "*..**",
  ".....",
  "*****",
  "..*..",
  "..*..",
  "..*..",
  "*****",
  ".....",
  "***..",
  "*..*.",
  "*...*",
  "*..*.",
  "***..",
  ".....",
  "*****",
  "*...*",
  "*...*",
  "*...*",
  "*****",
  ".....",
  "*...*",
  ".*.*.",
  "..*..",
  "..*..",
  "..*.."
};

int main()
{
  char buff[hbanner_columns * N_max + 1];
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    if (N > 0) {
      for (int si = 0; si < hbanner_rows; si++) {
        int dj = 0;
        for (int sj = 0; sj < hbanner_columns; sj++)
          for (int n = 0; n < N; n++, dj++)
            buff[dj] = hbanner[si][sj];
        buff[dj] = '\0';
        for (int n = 0; n < N; n++)
          printf("%s\n", buff);
      }
    }
    else {
      int L = -N;
      for (int si = 0; si < vbanner_rows; si++) {
        int dj = 0;
        for (int sj = 0; sj < vbanner_columns; sj++)
          for (int n = 0; n < L; n++, dj++)
            buff[dj] = vbanner[si][sj];
        buff[dj] = '\0';
        for (int n = 0; n < L; n++)
          printf("%s\n", buff);
      }
    }
    printf("\n\n");
  }
  return 0;
}