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