UVa 1593 - Alignment of Code

Accepted date: 2016-08-29
Run Time: 0.000
Ranking (as of 2016-08-29): 61 out of 396
Language: C++

/*
  UVa 1593 - Alignment of Code

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

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

const int nr_chars_max = 180, nr_lines_max = 1000;

char lines[nr_lines_max][nr_chars_max + 1], buff[nr_chars_max * nr_chars_max];

struct word {
  char* p_;
  int l_;
} words[nr_lines_max][nr_chars_max + 1];

int max_lengths[nr_chars_max + 1];

int main()
{
  int nr_lines = 0;
  while (gets(lines[nr_lines])) {
    char* p = lines[nr_lines];
    while (*p == ' ')
      p++;
    for (int i = 0; *p; i++) {
      words[nr_lines][i].p_ = p;
      while (*p && *p != ' ')
        p++;
      words[nr_lines][i].l_ = p - words[nr_lines][i].p_;
      max_lengths[i] = max(max_lengths[i], words[nr_lines][i].l_ + 1);
      while (*p == ' ')
        p++;
    }
    nr_lines++;
  }
  for (int i = 0; i < nr_lines; i++) {
    char* p = buff;
    for (int j = 0; words[i][j].p_; j++) {
      memcpy(p, words[i][j].p_, words[i][j].l_);
      p += words[i][j].l_;
      if (words[i][j + 1].p_) {
        int k = max_lengths[j] - words[i][j].l_;
        memset(p, ' ', k);
        p += k;
      }
    }
    *p = '\0';
    puts(buff);
  }
  return 0;
}

UVa 10148 - Advertisement

Accepted date: 2016-08-26
Run Time: 0.010
Ranking (as of 2016-08-26): 2 out of 397
Language: C++

/*
  UVa 10148 - Advertisement

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

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

const int N_max = 1000, number_min = -10000, number_max = 10000;
bool numbers[number_max - number_min + 1];

struct path {
  int l_, h_;

  bool operator<(const path& p) const {return h_ < p.h_;}
} paths[N_max];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int K, N;
    scanf("%d %d", &K, &N);
    int l_min = number_max - number_min + 1;
    for (int i = 0; i < N; i++) {
      scanf("%d %d", &paths[i].l_, &paths[i].h_);
      paths[i].l_ -= number_min, paths[i].h_ -= number_min;
      if (paths[i].l_ > paths[i].h_)
        swap(paths[i].l_, paths[i].h_);
      l_min = min(l_min, paths[i].l_);
    }
    sort(paths, paths + N);
    int nr_numbers = 0;
    memset(numbers, 0, sizeof(numbers));
    for (int i = 0; i < N; i++) {
      const path& p = paths[i];
      if (p.h_ - p.l_ < K) {
        for (int j = p.l_; j <= p.h_; j++) {
          if (!numbers[j])
            nr_numbers++;
          numbers[j] = true;
        }
      }
      else {
        int k = K;
        for (int j = p.l_; j <= p.h_ && k; j++)
          if (numbers[j])
            k--;
        if (k) {
          for (int j = p.h_; j >= p.l_ && k; j--)
            if (!numbers[j])
              nr_numbers++, numbers[j] = true, k--;
        }
      }
    }
    printf("%d\n", nr_numbers);
    for (int i = l_min; i <= paths[N - 1].h_ && nr_numbers; i++)
      if (numbers[i]) {
        printf("%d\n", i + number_min);
        nr_numbers--;
      }
    if (nr_cases)
      putchar('\n');
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 12897 - Decoding Baby Boos

Accepted date: 2016-08-22
Run Time: 0.010
Ranking (as of 2016-08-22): 6 out of 397
Language: C++

/*
  UVa 12897 - Decoding Baby Boos

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

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

const int nr_chars_max = 1000000;
char S[nr_chars_max + 1];

const int nr_letters = 'Z' - 'A' + 1;

struct rule {
  int i_; // ordinal # at which this rule is defined
  int r_; // this rule reverse replaces a charecter with ('A' + r_)

  rule() {}
  rule(int i, int r) : i_(i), r_(r) {}

  bool operator<(const rule& r) const {return i_ < r.i_;}
};

vector<rule> rules[nr_letters];
char replaces[nr_letters]; // replaces[i] is the reverse replacement of ('A' + i)

char replace(int s)
{
  if (rules[s].empty())
    return 'A' + s;
  rule r = rules[s].front();
  while (true) {
    const vector<rule>& rs = rules[r.r_];
    vector<rule>::const_iterator i = upper_bound(rs.begin(), rs.end(), r);
    if (i == rs.end())
      break;
    r = *i;
/*
    size_t i;
    for (i = 0; i < rs.size(); i++)
      if (rs[i].i_ > r.i_)
        break;
    if (i == rs.size())
      break;
    r = rs[i];
*/
  }
  return 'A' + r.r_;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", S);
    int R;
    scanf("%d", &R);
    for (int i = 0; i < R; i++) {
      char ai[2], bi[2];
      scanf("%s %s", ai, bi);
      rules[bi[0] - 'A'].push_back(rule(i, ai[0] - 'A'));
    }
    for (int i = 0; i < nr_letters; i++)
      sort(rules[i].begin(), rules[i].end());
    for (int i = 0; i < nr_letters; i++)
      replaces[i] = replace(i);
    for (char* p = S; *p; p++)
      if (*p != '_')
        *p = replaces[*p - 'A'];
    puts(S);
    if (T)
      for (int i = 0; i < nr_letters; i++)
        rules[i].clear();
  }
  return 0;
}

UVa 1595 - Symmetry

Accepted date: 2016-08-20
Run Time: 0.010
Ranking (as of 2016-08-20): 76 out of 396
Language: C++

/*
  UVa 1595 - Symmetry

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

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

const int N_max = 1000;

struct dot {
  int x_, y_;

  dot() {}
  dot(int x, int y) : x_(x), y_(y) {}
  bool operator<(const dot &d) const {return (x_ != d.x_) ? x_ < d.x_ : y_ < d.y_;}
} dots[N_max];

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
      scanf("%d %d", &dots[i].x_, &dots[i].y_);
    bool yes = true;
    if (N > 1) {
      sort(dots, dots + N);
      int s = dots[0].x_ + dots[N - 1].x_;
      for (int i = 0; i < N; i++)
        if (!binary_search(dots, dots + N, dot(s - dots[i].x_, dots[i].y_))) {
          yes = false; break;
        }
    }
    puts((yes) ? "YES" : "NO");
  }
  return 0;
}

UVa 12269 - Lawn mower

Accepted date: 2016-08-19
Run Time: 0.000
Ranking (as of 2016-08-19): 13 out of 397
Language: C++

/*
  UVa 12269 - Lawn mower

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

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

const double length = 100.0, width = 75.0;
const int nx_max = 1000, ny_max = 1000;

struct pass {
  double l_, h_;

  bool operator<(const pass& p) const {return l_ < p.l_;}
};

pass end_to_ends[nx_max], side_to_sides[ny_max];

bool mow(double h_max, int n, const pass* passes)
{
  const pass& p = passes[0];
  if (passes[0].l_ > 0.0)
    return false;
  double h = passes[0].h_;
  for (int i = 1; i < n; i++) {
    if (h < passes[i].l_)
      return false;
    h = max(h, passes[i].h_);
  }
  return h == h_max;
}

int main()
{
  while (true) {
    int nx, ny;
    double w;
    scanf("%d %d %lf", &nx, &ny, &w);
    if (!nx)
      break;
    for (int i = 0; i < nx; i++) {
      double xi;
      scanf("%lf", &xi);
      end_to_ends[i].l_ = max(0.0, xi - w / 2.0);
      end_to_ends[i].h_ = min(width, xi + w / 2.0);
    }
    for (int i = 0; i < ny; i++) {
      double yi;
      scanf("%lf", &yi);
      side_to_sides[i].l_ = max(0.0, yi - w / 2.0);
      side_to_sides[i].h_ = min(length, yi + w / 2.0);
    }
    sort(end_to_ends, end_to_ends + nx);
    bool yes = mow(width, nx, end_to_ends);
    if (yes) {
      sort(side_to_sides, side_to_sides + ny);
      yes = mow(length, ny, side_to_sides);
    }
    puts((yes) ? "YES" : "NO");
  }
  return 0;
}

UVa 11284 - Shopping Trip

Accepted date: 2016-08-18
Run Time: 0.020
Ranking (as of 2016-08-18): 39 out of 421
Language: C++

/*
  UVa 11284 - Shopping Trip

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

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

const int infinite = numeric_limits<short>::max();
const int N_max = 50, P_max = 12;

int matrix[N_max + 1][N_max + 1];
  // matrix[i][j] is the min. distances between the store i and j
struct store {
  int i_;
  int cost_;
} stores[P_max + 1];

int costs[P_max + 1][P_max + 1];
  // costs[i][j] is the cost between the stores of i and j where DVD may be bought
int bitmasks[1 << (P_max + 1)][P_max + 1];

int tsp(int nr_places, int places, int p) // travelling salesman problem
{
  int& b = bitmasks[places][p];
  if (places == (1 << p))
    return b = costs[p][0] - stores[p].cost_;
  if (b < infinite)
    return b;
  for (int i = 0; i < nr_places; i++)
    if (i != p && (places & (1 << i)))
      b = min(b, tsp(nr_places, places & ~(1 << p), i) + costs[i][p] - stores[p].cost_);
  return b;
}

int main()
{
  int s;
  scanf("%d", &s);
  while (s--) {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i <= N; i++)
      for (int j = 0; j <= N; j++)
        matrix[i][j] = (i != j) ? infinite : 0;
    while (M--) {
      int i, j, dollars, cents, cost;
      scanf("%d %d %d.%d", &i, &j, &dollars, ¢s);
      cost = dollars * 100 + cents;
      if (cost < matrix[i][j])
        matrix[i][j] = matrix[j][i] = cost;
    }
    int P;
    scanf("%d", &P);
    for (int i = 1; i <= P; i++) {
      int dollars, cents;
      scanf("%d %d.%d", &stores[i].i_, &dollars, ¢s);
      stores[i].cost_ = dollars * 100 + cents;
    }
    for (int k = 0; k <= N; k++)
      for (int i = 0; i <= N; i++)
        if (matrix[i][k] < infinite)
          for (int j = 1; j <= N; j++)
            if (matrix[k][j] < infinite)
              matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
    for (int i = 1; i <= P; i++)
      costs[0][i] = costs[i][0] = matrix[0][stores[i].i_];
    for (int i = 1; i <= P; i++)
      for (int j = 1; j <= P; j++)
        costs[i][j] = matrix[stores[i].i_][stores[j].i_];
    int places = 1 << (P + 1);
    for (int i = 0; i < places; i++)
      for (int j = 0; j <= P; j++)
        bitmasks[i][j] = infinite;
    tsp(P + 1, places - 1, 0);
    int min_cost = infinite;
    for (int i = 0; i < places; i++)
      for (int j = 0; j <= P; j++)
        if (min_cost > bitmasks[i][j] + costs[j][0])
          min_cost = bitmasks[i][j] + costs[j][0];
    if (min_cost < 0) {
      min_cost = -min_cost;
      printf("Daniel can save $%d.%02d\n", min_cost / 100, min_cost % 100);
    }
    else
      puts("Don't leave the house");
  }
  return 0;
}

UVa 10937 - Blackbeard the Pirate

Accepted date: 2016-08-12
Run Time: 0.000
Ranking (as of 2016-08-12): 19 out of 385
Language: C++

/*
  UVa 10937 - Blackbeard the Pirate

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

  This problem is similar to 10944 - Nuts for nuts..
*/

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

const int infinite = numeric_limits<int>::max();
const int h_max = 50, w_max = 50, nr_treasures_max = 10;
char map[h_max][w_max + 1];
struct place {
  int r_, c_;
  place() {}
  place(int r, int c) : r_(r), c_(c) {}
  place(const place& p) : r_(p.r_), c_(p.c_) {}
} places[nr_treasures_max + 1];

bool visited[h_max][w_max];
int distances[nr_treasures_max + 1][nr_treasures_max + 1];
  // distances[i][j] is the distance between the treasures of i and j
int bitmasks[1 << (nr_treasures_max + 1)][nr_treasures_max + 1];

const int nr_cardinal_dirs = 4;
const pair<int, int> cardinal_dirs[nr_cardinal_dirs] =
  {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
const int nr_diagonal_dirs = 4;
const pair<int, int> diagonal_dirs[nr_diagonal_dirs] =
  {make_pair(1, 1), make_pair(-1, 1), make_pair(-1, -1), make_pair(1, -1)};

int tsp(int nr_treasures, int places, int p) // travelling salesman problem
{
  if (places == (1 << p))
    return distances[p][0]; // distance from the landing point to the treasure of p
  int& d = bitmasks[places][p];
  if (d >= 0)
    return d;
  d = infinite;
  for (int i = 0; i < nr_treasures; i++)
    if (i != p && (places & (1 << i)))
      d = min(d, distances[p][i] + tsp(nr_treasures, places & ~(1 << p), i));
  return d;
}

int bfs(int h, int w, int s, int nr_treasures)
{
  memset(visited, 0, sizeof(visited));
  for (int i = 0; i < nr_treasures; i++)
    distances[s][i] = infinite;
  queue< pair<place, int> > q;
  visited[places[s].r_][places[s].c_] = true;
  distances[s][s] = 0;
  q.push(make_pair(places[s], 0));
  while (!q.empty()) {
    place p = q.front().first;
    int d = q.front().second;
    q.pop();
    for (int i = 0; i < nr_cardinal_dirs; i++) {
      int nr = p.r_ + cardinal_dirs[i].first, nc = p.c_ + cardinal_dirs[i].second;
      if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != -1 && !visited[nr][nc]) {
        visited[nr][nc] = true;
        if (map[nr][nc] < nr_treasures)
          distances[s][map[nr][nc]] = distances[map[nr][nc]][s] = d + 1;
        q.push(make_pair(place(nr, nc), d + 1));
      }
    }
  }
  for (int i = 0; i < nr_treasures; i++)
    if (distances[s][i] == infinite)
      return -1;
  return 0;
}

int main()
{
  while (true) {
    int h, w;
    scanf("%d %d", &h, &w);
    if (!h)
      break;
    int nr_treasures = 1;
    for (int r = 0; r < h; r++) {
      scanf("%s", map[r]);
      for(int c = 0; c < w; c++)
        switch (map[r][c]) {
        case '@':
          places[0].r_ = r, places[0].c_ = c;
          map[r][c] = 0;
          break;
        case '!':
          places[nr_treasures].r_ = r, places[nr_treasures].c_ = c;
          map[r][c] = nr_treasures++;
          break;
        case '~': case '#':
          map[r][c] = -1;
            break;
        }
    }
    int result = 0;
    for (int r = 0; r < h; r++)
      for(int c = 0; c < w; c++)
        if (map[r][c] == '*') {
          for (int i = 0; i < nr_cardinal_dirs; i++) {
            int nr = r + cardinal_dirs[i].first, nc = c + cardinal_dirs[i].second;
            if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != '*') {
              if (map[nr][nc] >= 0 && map[nr][nc] < nr_treasures)
                result = -1; // a treasure is not reachable
              map[nr][nc] = -1;
            }
            if (result == -1)
              break;
          }
          for (int i = 0; i < nr_diagonal_dirs; i++) {
            int nr = r + diagonal_dirs[i].first, nc = c + diagonal_dirs[i].second;
            if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != '*') {
              if (map[nr][nc] >= 0 && map[nr][nc] < nr_treasures)
                result = -1;
              map[nr][nc] = -1;
            }
            if (result == -1)
              break;
          }
          if (result == -1)
            break;
        }
    if (result != -1) {
      // calculate the distances between the treasures/landing point
      for (int i = 0; i < nr_treasures; i++)
        if ((result = bfs(h, w, i, nr_treasures)) == -1)
          break;
      if (result != -1) {
        memset(bitmasks, -1, sizeof(bitmasks));
        result = tsp(nr_treasures, (1 << nr_treasures) - 1, 0);
      }
    }
    printf("%d\n", result);
  }
  return 0;
}

UVa 757 - Gone Fishing

Accepted date: 2016-08-11
Run Time: 0.050
Ranking (as of 2016-08-11): 187 out of 508
Language: C++

/*
  UVa 757 - Gone Fishing

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

#include <cstdio>

const int n_max = 25, h_max = 16, interval = 5, nr_intervals_max = h_max * 60 / interval;

int fi[n_max], di[n_max], ti[n_max];
int caught[n_max][nr_intervals_max + 1];
  // caught[i][j] is the number of fishes caught at the i-th lake with j intervals spent
int from[n_max][nr_intervals_max + 1];

void print_intervals(int i, int j)
{
  if (!i)
    printf("%d", j * interval);
  else {
    print_intervals(i - 1, from[i][j]);
    printf(", %d", (j - from[i][j]) * interval);
  }
}

int main()
{
  bool printed = false;
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    if (printed)
      putchar('\n');
    else
      printed = true;
    int h;
    scanf("%d", &h);
    int nr_intervals = h * 60 / interval;
    for (int i = 0; i < n; i++)
      scanf("%d", &fi[i]);
    for (int i = 0; i < n; i++)
      scanf("%d", &di[i]);
    for (int i = 0; i < n - 1; i++)
      scanf("%d", &ti[i]);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < nr_intervals; j++)
        caught[i][j] = from[i][j] = 0;
    for (int j = 1, f = fi[0], c = f; j <= nr_intervals; j++) {
      caught[0][j] = c;
      if ((f -= di[0]) > 0)
        c += f;
    }
    int max_i = 0, max_j = nr_intervals;
    nr_intervals -= ti[0];
    for (int i = 1; i < n && nr_intervals > 0; i++) {
      for (int j = 1; j <= nr_intervals; j++) {
        caught[i][j] = caught[i - 1][j], from[i][j] = j;
        for (int k = j - 1, f = fi[i], c = f; k >= 0; k--) {
          if (caught[i][j] < caught[i - 1][k] + c)
            caught[i][j] = caught[i - 1][k] + c, from[i][j] = k;
          if ((f -= di[i]) > 0)
            c += f;
        }
      }
      if (caught[max_i][max_j] < caught[i][nr_intervals])
        max_i = i, max_j = nr_intervals;
      nr_intervals -= ti[i];
    }
#ifdef DEBUG
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= h * 60 / interval; j++)
        if (caught[i][j])
          printf("[%d][%d]: (%d %d) ", i, j, caught[i][j], from[i][j]);
      putchar('\n');
    }
    printf("%d %d\n", max_i, max_j);
#endif
    print_intervals(max_i, max_j);
    for (int i = max_i; i < n - 1; i++)
      printf(", 0");
    printf("\nNumber of fish expected: %d\n", caught[max_i][max_j]);
  }
  return 0;
}

UVa 11658 - Best Coalitions

Accepted date: 2016-08-09
Run Time: 0.000
Ranking (as of 2016-08-09): 25 out of 396
Language: C++

/*
  UVa 11658 - Best Coalitions

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

#include <cstdio>
#include <cstring>

const int n_max = 100, p_max = 10000;
int percentages[n_max + 1];
bool coalitions[p_max + 1];

int main()
{
  while (true) {
    int n, x;
    scanf("%d %d", &n, &x);
    if (!n)
      break;
    x--;
    int px;
    for (int i = 0, j = 0; i < n; i++) {
      int integral, decimal;
      scanf("%d.%d", &integral, &decimal);
      percentages[j] = integral * 100 + decimal;
      if (i == x)
        px = percentages[j];
      else
        j++;
    }
    if (px > 5000) {
      printf("%.2lf\n", 100.0);
      continue;
    }
    memset(coalitions, 0, sizeof(coalitions));
    int ci = 0;
    for (int i = 0; i < n - 1; i++) {
      int p = percentages[i];
      for (int j = ci; j; j--)
        if (coalitions[j])
          coalitions[j + p] = true;
      coalitions[p] = true;
      ci += p;
#ifdef DEBUG
      for (int j = 1; j <= ci; j++)
        if (coalitions[j])
          printf("%d%c", j, ((j < ci) ? ' ' : '\n'));
#endif
    }
    double sp = 0.0;
    for (int i = 5001 - px; i <= ci; i++)
      if (coalitions[i]) {
        sp = static_cast<double>(px) * 100.0 / static_cast<double>(px + i);
        break;
      }
    printf("%.2lf\n", sp);
  }
  return 0;
}

UVa 11149 - Power of Matrix

Accepted date: 2016-08-08
Run Time: 0.220
Ranking (as of 2016-08-08): 151 out of 404
Language: C++

/*
  UVa 11149 - Power of Matrix

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

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

const int n_max = 40, k_max = 1000000;

struct matrix {
  vector< vector<int> > entries_;
  matrix(int n) : entries_(n, vector<int>(n)) {}
};

int n;
matrix I(n_max); // identity matrix

void add_matrix(matrix& a, matrix& b, matrix& result)
{
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      result.entries_[i][j] = (a.entries_[i][j] + b.entries_[i][j]) % 10;
}

void multiply_matrix(matrix& a, matrix& b, matrix& result)
{
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      int r = 0;
      for (int k = 0; k < n; k++) {
        r += a.entries_[i][k] * b.entries_[k][j] % 10;
        r %= 10;
      }
      result.entries_[i][j] = r;
    }
}

void power_of_matrix(int k, matrix& a, matrix& result)
{
  if (k == 1) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        result.entries_[i][j] = a.entries_[i][j];
  }
  else {
    matrix p(n);
    power_of_matrix(k / 2, a, p);
    if (k & 1) {
      matrix r(n);
      multiply_matrix(p, p, r);
      multiply_matrix(r, a, result);
    }
    else
      multiply_matrix(p, p, result);
  }
}

/*
S(k) = A + A^2 + A^3 + ... + A^k, then
  S(1) = A
  S(k) = S(k / 2) * (I + A^(k / 2)) if n is even
  S(k) = S(k / 2) * (I + A^(k / 2)) + A^k if n is odd
*/

void sum_of_powers(int k, matrix& a, matrix& result)
{
  if (k == 1) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        result.entries_[i][j] = a.entries_[i][j];
  }
  else {
    matrix s(n), p(n), r(n);
    sum_of_powers(k / 2, a, s);
    power_of_matrix(k / 2, a, p);
    add_matrix(I, p, r);
    if (k & 1) { // k is odd
      matrix rr(n);
      multiply_matrix(s, r, rr);
      power_of_matrix(k, a, p);
      add_matrix(rr, p, result);
    }
    else
      multiply_matrix(s, r, result);
  }
}

int main()
{
  for (int i = 0; i < n_max; i++)
    for (int j = 0; j < n_max; j++)
      I.entries_[i][j] = (i == j) ? 1 : 0;
  while (true) {
    int k;
    scanf("%d %d", &n, &k);
    if (!n)
      break;
    matrix a(n);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        scanf("%d", &a.entries_[i][j]);
        a.entries_[i][j] %= 10;
      }
    matrix result(n);
    sum_of_powers(k, a, result);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        printf("%d%c", result.entries_[i][j], ((j < n - 1) ? ' ' : '\n'));
    putchar('\n');
  }
  return 0;
}

UVa 242 - Stamps and Envelope Size

Accepted date: 2016-08-06
Run Time: 0.030
Ranking (as of 2016-08-06): 107 out of 500
Language: C++

/*
  UVa 242 - Stamps and Envelope Size

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

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

const int S_max = 10, max_denomination = 100, N_max = 10;

int nr_denominations[N_max + 1], denominations[N_max + 1][S_max + 1],
  max_coverages[N_max + 1];
bool values[S_max + 1][S_max + 1][max_denomination * S_max + 1];
  // values[i][j][k] is true if value of k can be represented using j stamps out of i stamps

int get_max_coverage(int nr_stamps, int nr_denoms, const int* denoms)
{
  memset(values, 0, sizeof(values));
  int max_v = 0;
  for (int j = 1, k = denoms[1]; j <= nr_stamps; j++, k += denoms[1])
    values[1][j][k] = true, max_v = k;
#ifdef DEBUG
  for (int j = 1; j <= nr_stamps; j++)
    for (int k = 1; k <= max_v; k++)
    if (values[1][j][k])
      printf("[%d][%d][%d] ", 1, j, k);
  putchar('\n');
#endif
  for (int i = 2; i <= nr_denoms; i++) {
    int max_k = max_v;
    max_v = 0;
    for (int j = 1; j <= nr_stamps; j++)
      for (int k = 1; k <= max_k; k++)
        if (values[i - 1][j][k]) {
          values[i][j][k] = true;
          for (int l = 1, s = denoms[i]; l <= nr_stamps - j; l++, s += denoms[i])
            values[i][j + l][k + s] = true, max_v = max(max_v, k + s);
        }
    for (int j = 1, k = denoms[i]; j <= nr_stamps; j++, k += denoms[i])
      values[i][j][k] = true, max_v = max(max_v, k);
#ifdef DEBUG
    for (int j = 1; j <= nr_stamps; j++)
      for (int k = 1; k <= max_v; k++)
      if (values[i][j][k])
        printf("[%d][%d][%d] ", i, j, k);
    putchar('\n');
#endif
  }
  int k;
  for (k = 0; k < max_v; k++) {
    int j;
    for (j = 1; j <= nr_stamps; j++)
      if (values[nr_denoms][j][k + 1])
        break;
    if (j > nr_stamps)
      break;
  }
  return k;
}

int compare_denomination(int di, int dj)
{
  if (nr_denominations[di] != nr_denominations[dj])
    return (nr_denominations[di] < nr_denominations[dj]) ? di : dj;
  for (int i = nr_denominations[di]; i; i--)
    if (denominations[di][i] != denominations[dj][i])
      return (denominations[di][i] < denominations[dj][i]) ? di : dj;
  return di;
}

int main()
{
  while (true) {
    int S;
    scanf("%d", &S);
    if (!S)
      break;
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
      scanf("%d", &nr_denominations[i]);
      for (int j = 1; j <= nr_denominations[i]; j++)
        scanf("%d", &denominations[i][j]);
      max_coverages[i] = get_max_coverage(S, nr_denominations[i], &denominations[i][0]);
#ifdef DEBUG
      printf("max coverage: %d\n", max_coverages[i]);
#endif
    }
    int max_coverage = max_coverages[1], max_coverage_denomination = 1;
    for (int i = 2; i <= N; i++) {
      if (max_coverage < max_coverages[i])
        max_coverage = max_coverages[i], max_coverage_denomination = i;
      else if (max_coverage == max_coverages[i])
        max_coverage_denomination = compare_denomination(max_coverage_denomination, i);
    }
    printf("max coverage = %3d :", max_coverage);
    for (int i = 1; i <= nr_denominations[max_coverage_denomination]; i++)
      printf("%3d", denominations[max_coverage_denomination][i]);
    putchar('\n');
  }
  return 0;
}

UVa 10804 - Gopher Strategy

Accepted date: 2016-08-04
Run Time: 0.390
Ranking (as of 2016-08-04): 100 out of 406
Language: C++

/*
  UVa 10804 - Gopher Strategy

  To build using Visual Studio 2008:
    cl -EHsc -O2 UVa_10804_Gopher_Strategy.cpp
*/

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

const int m_max = 50, n_max = 50;

pair<double, double> gophers[m_max], holes[n_max];
double distances[m_max][n_max], unique_distances[m_max * n_max];

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

struct edge {
  int v_; // neighboring vertex
  int capacity_; // capacity of edge
  int flow_; // flow through edge
  int residual_; // residual capacity of edge

  edge(int v, int capacity, int residual)
    : v_(v), capacity_(capacity), flow_(0), residual_(residual) {}
};

struct vertex_state {
  bool discovered_;
  int parent_;

  vertex_state() : discovered_(false), parent_(-1) {}
};

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

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

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

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

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

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

int get_gophers(vector< vector<edge> >& graph, int nr_gophers, int nr_holes,
  int source, int sink, double d)
{
  vector<edge>& gs =graph[source];
  for (int i = 0; i < nr_gophers; i++) {
    gs[i].capacity_ = gs[i].residual_ = 1, gs[i].flow_ = 0;
    vector<edge>& gg = graph[i];
    for (size_t j = 0; j < gg.size(); j++) {
      if (gg[j].v_ == source)
        gg[j].capacity_ = 1, gg[j].residual_ = gg[j].flow_ = 0;
      else {
        if (distances[i][gg[j].v_ - nr_gophers] <= d)
          gg[j].capacity_ = gg[j].residual_ = 1, gg[j].flow_ = 0;
        else
          gg[j].capacity_ = gg[j].residual_ = gg[j].flow_ = 0;
      }
    }
  }
  for (int i = nr_gophers; i < nr_gophers + nr_holes; i++) {
    vector<edge>& gh = graph[i];
    for (size_t j = 0; j < gh.size(); j++) {
      if (gh[j].v_ == sink)
        gh[j].capacity_ = gh[j].residual_ = 1, gh[j].flow_ = 0;
      else {
        if (distances[gh[j].v_][i - nr_gophers] <= d)
          gh[j].capacity_ = 1, gh[j].residual_ = gh[j].flow_ = 0;
        else
          gh[j].capacity_ = gh[j].residual_ = gh[j].flow_ = 0;
      }
    }
  }
  vector<edge>& gt = graph[sink];
  for (int i = 0; i < nr_holes; i++)
    gt[i].capacity_ = 1, gt[i].residual_ = gt[i].flow_ = 0;
  netflow(graph, source, sink); // apply Ford-Fulkerson's augmenting path algorithm
  int flow = total_flow(graph, source);
#ifdef DEBUG
  printf("%lf %d\n", d, flow);
#endif
  return flow;
}

int main()
{
  int N;
  scanf("%d", &N);
  for (int cn = 1; cn <= N; cn++) {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    for (int i = 0; i < m; i++)
      scanf("%lf %lf", &gophers[i].first, &gophers[i].second);
    for (int i = 0; i < n; i++)
      scanf("%lf %lf", &holes[i].first, &holes[i].second);
    if (!m || m == k) {
      printf("Case #%d:\n%.3lf\n\n", cn, 0.0);
      continue;
    }
    if (n < m - k) {
      printf("Case #%d:\nToo bad.\n\n", cn);
      continue;
    }
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        distances[i][j] = unique_distances[i * m + j] = euclidean_distance(gophers[i], holes[j]);
    int nr_unique_distances = m * n;
    sort(unique_distances, unique_distances + nr_unique_distances);
    nr_unique_distances =
      unique(unique_distances, unique_distances + nr_unique_distances) - unique_distances;
    int nr_vertices = m + n + 2, source = m + n, sink = m + n + 1;
    // indices are:
    //  0 - (m - 1): gopher vertices, m - (m + n - 1): hole vertices,
    //  (m + n): source vertex, (m + n + 1): sink vertex
    vector< vector<edge> > graph(nr_vertices);
    for (int i = 0; i < m; i++) {
      // append the edges between the source and gopher vertices
      graph[source].push_back(edge(i, 0, 0));
      graph[i].push_back(edge(source, 0, 0));
      for (int j = 0; j < n; j++) {
        // append the edges between gopher vertices and hole vertices
        graph[i].push_back(edge(m + j, 0, 0));
        graph[m + j].push_back(edge(i, 0, 0));
      }
    }
    for (int i = m; i < m + n; i++) {
      // append the edges between hole vertices and the sink
      graph[i].push_back(edge(sink, 1, 1));
      graph[sink].push_back(edge(i, 1, 0));
    }
    int min_di = 0;
    for (int low = 0, high = nr_unique_distances; low < high; ) {
      int mid = (low + high) / 2;
      int result = get_gophers(graph, m, n, source, sink, unique_distances[mid]) - (m - k);
      if (result < 0)
        low = mid + 1;
      else
        min_di = high = mid;
    }
    printf("Case #%d:\n%.3lf\n\n", cn, unique_distances[min_di]);
  }
  return 0;
}

UVa 10537 - The Toll! Revisited

Accepted date: 2016-08-02
Run Time: 0.000
Ranking (as of 2016-08-02): 103 out of 596
Language: C++

/*
  UVa 10537 - The Toll! Revisited

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

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

const long long infinite = numeric_limits<long long>::max();

const int nr_letters = 'Z' - 'A' + 1, nr_vertices = nr_letters * 2;

vector<int> edges[nr_vertices];

bool visited[nr_vertices];
long long distances[nr_vertices];
int parents[nr_vertices];

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

inline long long get_distance(int u, long long p)
{
  if (u < nr_letters) { // town
    return p + (p + 18) / 19;
/*
    long long q = p / 19, m = p % 19;
    return (m) ? 20 * q + m + 1 : 20 * q;
*/
  }
  else // village
    return p + 1;
}

long long dijkstra_shortest_path(int start, int end, long long p)
{
  for (int i = 0; i < nr_vertices; i++)
    visited[i] = false, distances[i] = infinite;
  set<int, distance_comparator> pq; // priority queue
  distances[start] = p, parents[start] = -1;
  pq.insert(start);
  while(!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    if (u == end)
      break;
    long long d = get_distance(u, distances[u]);
#ifdef DEBUG
    printf("\t%c %lld %lld\n", ((u < nr_letters) ? u + 'A' : u + 'a' - nr_letters), d, w);
#endif
    const vector<int>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i];
      if (!visited[v] && distances[v] > d) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = d, parents[v] = u;
        pq.insert(v);
      }
    }
  }
  return distances[end];
}

inline int get_vertex(char cu)
{
  return (isupper(cu)) ? cu - 'A' : cu - 'a' + nr_letters;
}

int main()
{
  for (int cn = 1; ; cn++) {
    int n;
    cin >> n;
    if (n == -1)
      break;
    for (int i = 0; i < nr_vertices; i++)
      edges[i].clear();
    while (n--) {
      char cu, cv;
      cin >> cu >> cv;
      int u = get_vertex(cu), v = get_vertex(cv);
      edges[u].push_back(v), edges[v].push_back(u);
    }
    long long p;
    char cs, ce;
    cin >> p >> cs >> ce;
    int start = get_vertex(cs), end = get_vertex(ce);
    long long d = dijkstra_shortest_path(end, start, p);
    printf("Case %d:\n%lld\n", cn, d);
    int u = start;
    while (true) {
      putchar((u < nr_letters) ? u + 'A' : u + 'a' - nr_letters);
      if ((u = parents[u]) == -1)
        break;
      putchar('-');
    }
    putchar('\n');
  }
  return 0;
}