UVa 1064 - Network

Accepted date: 2015-05-29
Ranking (as of 2015-05-29): 54 out of 87
Language: C++

/*
  UVa 1064 - Network

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

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

const int nr_messages_max = 5, nr_packets_max = 1000;

struct packet {
  int mn_, sn_, en_;
} packets[nr_packets_max];

struct packet_comparator {
  bool operator()(int i, int j) {
    return packets[i].sn_ < packets[j].sn_;
  }
};

struct message {
  int nr_data_, out_n_; // next byte numbet to be output
  set<int, packet_comparator> packets_;
} messages[nr_messages_max];

int remove_packet_buffers(message& m, int& out_n)
{
  int nr_data = 0;
  set<int, packet_comparator>::iterator pi = m.packets_.begin(),
    pe = m.packets_.end();
  for ( ; pi != pe; ++pi) {
    if (out_n < packets[*pi].sn_)
      break;
    nr_data += packets[*pi].en_ - packets[*pi].sn_ + 1;
    out_n = packets[*pi].en_ + 1;
  }
  if (nr_data)
    m.packets_.erase(m.packets_.begin(), pi);
  return nr_data;
}

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int N, M;
    scanf("%d %d", &N, &M);
    if (!N)
      break;
    for (int i = 0; i < N; i++)
      scanf("%d", &messages[i].nr_data_);
    for (int i = 0; i < M; i++) {
      scanf("%d %d %d", &packets[i].mn_, &packets[i].sn_, &packets[i].en_);
      packets[i].mn_--;
    }
    int order[nr_messages_max]; // order in which messages will be out
    for (int i = 0; i < N; i++)
      order[i] = i;
    int buff_max = numeric_limits<int>::max();
    do {
#ifdef DEBUG
    for (int i = 0; i < N; i++)
      printf("%d%c", order[i], ((i < N - 1) ? ' ' : '\n'));
#endif
      int b = 0, b_max = 0, nr_out = 0;
      for (int i = 0; i < N; i++) {
        messages[i].out_n_ = 1;
        messages[i].packets_.clear();
      }
      for (int i = 0; i < M; i++) {
        const packet& p = packets[i];
        message& m = messages[p.mn_];
        if (p.mn_ == order[nr_out] && m.out_n_ == p.sn_) {
          m.out_n_ = p.en_ + 1;
          int nr_data = remove_packet_buffers(m, m.out_n_);
          if (nr_data)
            b -= nr_data;
          if (m.out_n_ == m.nr_data_ + 1) { // a message is complete
            for (nr_out++; nr_out < N; nr_out++) {
              message& mm = messages[order[nr_out]];
              if (nr_data = remove_packet_buffers(mm, mm.out_n_))
                b -= nr_data;
              if (mm.out_n_ < mm.nr_data_ + 1)
                break;
            }
          }
        }
        else {
          m.packets_.insert(i);
          b += p.en_ - p.sn_ + 1;
        }
        b_max = max(b_max, b);
#ifdef DEBUG
        printf("%d %d %d,  b: %d, b_max: %d\n", p.mn_, p.sn_, p.en_, b, b_max);
#endif
#ifndef DEBUG
        if (buff_max != numeric_limits<int>::max() && b_max >= buff_max)
          break;
#endif
      }
      buff_max = min(buff_max, b_max);
#ifdef DEBUG
      printf("buff_max: %d, buff_max_min: %d\n", b_max, buff_max);
#endif
    } while (next_permutation(order, order + N));
    printf("Case %d: %d\n\n", case_nr, buff_max);
  }
  return 0;
}

UVa 11548 - Blackboard Bonanza

Accepted date: 2015-05-24
Ranking (as of 2015-05-24): 5 out of 250
Language: C++

/*
  UVa 11548 - Blackboard Bonanza

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

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

const int n_max = 70;
int word_lengths[n_max];
char words[n_max][n_max + 1];

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%s", words[i]);
      word_lengths[i] = strlen(words[i]);
    }
    int max_ctr = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (i != j)
          for (int k = 0; k < word_lengths[j]; k++) {
            int m = min(word_lengths[i], word_lengths[j] - k);
            if (m <= max_ctr)
              break;
            int ctr = 0;
            for (int l = 0; l < m; l++)
              if (words[i][l] == words[j][k + l])
                ctr++;
            max_ctr = max(max_ctr, ctr);
          }
    printf("%d\n", max_ctr);
  }
  return 0;
}

UVa 10973 - Triangle Counting

Accepted date: 2015-05-22
Ranking (as of 2015-05-22): 131 out of 308
Language: C++

/*
  UVa 10973 - Triangle Counting

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

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

const int n_max = 3000;
vector<int> edges[n_max + 1];
bool matrix[n_max + 1][n_max + 1];

void triangle_counting(int n, int ci, int ei, int t[], int& ctr)
{
  if (ci == 2) {
#ifdef DEBUG
    printf("%d %d %d\n", t[0], t[1], ei);
#endif
    if (matrix[t[0]][ei])
      ctr++;
  }
  else {
    t[ci] = ei;
    const vector<int>& es = edges[ei];
    for (size_t i = 0, j = es.size(); i < j; i++)
      triangle_counting(n, ci + 1, es[i], t, ctr);
  }
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
      edges[i].clear();
      for (int j = i + 1; j <= n; j++)
        matrix[i][j] = matrix[j][i] = false;
    }
    while (m--) {
      int i, j;
      scanf("%d %d", &i, &j);
      if (i > j)
        swap(i, j);
      edges[i].push_back(j);
      matrix[i][j] = matrix[j][i] = true;
    }
    for (int i = 1; i <= n; i++)
      sort(edges[i].begin(), edges[i].end());
    int t[2], ctr = 0;
    for (int i = 1; i <= n; i++) {
      t[0] = i;
      const vector<int>& es = edges[i];
      for (size_t j = 0, k = es.size(); j < k; j++)
        triangle_counting(n, 1, es[j], t, ctr);
    }
    printf("%d\n", ctr);
  }
  return 0;
}

UVa 947 - Master Mind Helper

Accepted date: 2015-05-21
Ranking (as of 2015-05-21): 19 out of 102
Language: C++

/*
  UVa 947 - Master Mind Helper

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

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

const int nr_digits_max = 5;
char guess[nr_digits_max + 1], code[nr_digits_max + 1];
int fn, sn;

void generate_code(int n, int ci, int& ctr)
{
  if (ci == n) {
    char s[nr_digits_max + 1], t[nr_digits_max + 1];
    memcpy(s, guess, n);
    memcpy(t, code, n);
    int fm = 0, sm = 0;
    for (int i = 0; i < n; i++)
      if (s[i] == t[i]) {
        s[i] = t[i] = '0';
        fm++;
      }
    for (int i = 0; i < n; i++)
      if (s[i] != '0')
        for (int j = 0; j < n; j++)
          if (s[i] == t[j]) {
            s[i] = t[j] = '0';
            sm++;
            break;
          }
    if (fn == fm && sn == sm)
      ctr++;
  }
  else {
    for (int i = 1; i <= 9; i++) {
      code[ci] = '0' + i;
      generate_code(n, ci + 1, ctr);
    }
  }
}

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    scanf("%s %d %d", guess, &fn, &sn);
    int ctr = 0;
    generate_code(strlen(guess), 0, ctr);
    printf("%d\n", ctr);
  }
  return 0;
}

UVa 11412 - Dig the Holes

Accepted date: 2015-05-20
Ranking (as of 2015-05-20): 82 out of 210
Language: C++

/*
  UVa 11412 - Dig the Holes

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

#include <cstdio>

enum {red, green, blue, yellow, orange, violet};
const int color_numbers[] = {-1, blue, -1, -1, -1, -1, green, -1, -1, -1, -1, -1, -1, -1, orange, -1, -1, red, -1, -1, -1, violet, -1, -1, yellow, -1};

const int nr_seqs = 6 * 5 * 4 * 3, nr_colors = violet - red + 1, nr_holes = 4;
int seqs[nr_seqs][nr_holes];

void generate_sequences(int holes, int colors, int seq[], int& si)
{
  if (holes == nr_holes) {
    for (int i = 0; i < nr_holes; i++)
      seqs[si][i] = seq[i];
#ifdef DEBUG
    printf("%d %d %d %d\n", seqs[si][0], seqs[si][1], seqs[si][2], seqs[si][3]);
#endif
    si++;
  }
  else {
    for (int i = 0, b = 1; i < nr_colors; i++, b <<= 1)
      if (!(colors & b)) {
        colors |= b;
        seq[holes] = i;
        generate_sequences(holes + 1, colors, seq, si);
        colors &= ~b;
      }
  }
}

void get_seq(const char* s, int seq[])
{
  for (int i = 0; i < nr_holes; i++)
    seq[i] = color_numbers[s[i] - 'A'];
}

bool possible_sequence(int si, int seq[], int n1, int n2)
{
  int m1 = 0, m2 = 0;
  for (int j = 0; j < nr_holes; j++) {
    int c = seqs[si][j];
    for (int k = 0; k < nr_holes; k++)
      if (seq[k] == c) {
        if (j == k)
          m1++;
        else
          m2++;
        break;
      }
  }
  return n1 == m1 && n2 == m2;
}

int main()
{
  int seq[nr_holes], si = 0;
  generate_sequences(0, 0, seq, si);
#ifdef DEBUG
  printf("%d\n", si);
#endif
  int t;
  scanf("%d", &t);
  while (t--) {
    char s[nr_holes + 1];
    int n11, n12, n21, n22, seq1[nr_holes], seq2[nr_holes];
    scanf("%s %d %d", s, &n11, &n12);
    get_seq(s, seq1);
    scanf("%s %d %d", s, &n21, &n22);
    get_seq(s, seq2);
    bool possible = false;
    for (int si = 0; si < nr_seqs; si++)
      if (possible_sequence(si, seq1, n11, n12) &&
        possible_sequence(si, seq2, n21, n22)) {
        possible = true; break;
      }
    puts((possible) ? "Possible" : "Cheat");
  }
  return 0;
}

UVa 12346 - Water Gate Management

Accepted date: 2015-05-19
Ranking (as of 2015-05-19): 132 out of 176
Language: C++

/*
  UVa 12346 - Water Gate Management

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

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

const int n_max = 20;

struct gate {
  int flow_rate_, cost_;
  long long volume_;

  bool operator<(const gate& g) const {
    return (flow_rate_ != g.flow_rate_) ? flow_rate_ > g.flow_rate_ : cost_ < g.cost_;
  }
} gates[n_max];

long long sums[n_max];
  // sums[i] is the sum of volumes between i-th gate and (n - 1)-th gate

void gate_management(int n, int ni, long long V, long long s, int cost, int& min_cost)
{
  if (s >= V) {
    if (min_cost == -1 || cost < min_cost)
      min_cost = cost;
  }
  else if (ni < n && s + sums[ni] >= V) {
    gate_management(n, ni + 1, V, s + gates[ni].volume_,
      cost + gates[ni].cost_, min_cost);
    gate_management(n, ni + 1, V, s, cost, min_cost);
  }
}

int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d %d", &gates[i].flow_rate_, &gates[i].cost_);
  sort(gates, gates + n);
  int m;
  scanf("%d", &m);
  for (int case_nr = 1; case_nr <= m; case_nr++) {
    long long V, T;
    scanf("%lld %lld", &V, &T);
    long long s = 0;
    for (int i = n - 1; i >= 0; i--) {
      gates[i].volume_ = gates[i].flow_rate_ * T;
      s += gates[i].volume_;
      sums[i] = s;
    }
    int min_cost = -1;
    gate_management(n, 0, V, 0, 0, min_cost);
    printf("Case %d: ", case_nr);
    if (min_cost != -1)
      printf("%d\n", min_cost);
    else
      puts("IMPOSSIBLE");
  }
  return 0;
}

UVa 1047 - Zones

Accepted date: 2015-05-18
Ranking (as of 2015-05-18): 110 out of 215
Language: C++

/*
  UVa 1047 - Zones

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

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

const int nr_towers_max = 20, nr_csas_max = 10;

int nr_customers[nr_towers_max];

struct csa { // common service area
  int nr_towers_;
  unsigned int towers_;
  int nr_customers_;
} csas[nr_csas_max];

int nr_planned, nr_built, nr_csas, max_nr_customers;
unsigned int max_towers;

void build_towers(int n, int ti, unsigned int towers)
{
  unsigned int t;
  if (n == nr_built) {
    int nc = 0;
    t = towers;
    for (int i = 0; t; i++, t >>= 1)
      if (t & 1)
        nc += nr_customers[i];
    for (int i = 0; i < nr_csas; i++) {
      const csa& c = csas[i];
      t = towers & c.towers_;
      if (t) {
        int nt = 0;
        for (unsigned int tt = t; tt; tt >>= 1)
          if (tt & 1)
            nt++;
        nc -= (min(nt, c.nr_towers_) - 1) * c.nr_customers_;
      }
    }
#ifdef DEBUG
    printf("%d %#x\n", nc, towers);
#endif
    if (nc > max_nr_customers) {
      max_nr_customers = nc;
      max_towers = towers;
    }
  }
  else if (ti < nr_planned) {
    t = 1 << ti;
    towers |= t;
    build_towers(n + 1, ti + 1, towers);
    towers &= ~t;
    build_towers(n, ti + 1, towers);
  }
}

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    scanf("%d %d", &nr_planned, &nr_built);
    if (!nr_planned && !nr_built)
      break;
    for (int i = 0; i < nr_planned; i++)
      scanf("%d", &nr_customers[i]);
    scanf("%d", &nr_csas);
    for (int i = 0; i < nr_csas; i++) {
      csa& c = csas[i];
      scanf("%d", &c.nr_towers_);
      c.towers_ = 0;
      for (int j = 0; j < c.nr_towers_; j++) {
        int k;
        scanf("%d", &k);
        c.towers_ |= 1 << (k - 1);
      }
      scanf("%d", &c.nr_customers_);
    }
    max_nr_customers = 0;
    build_towers(0, 0, 0);
    printf("Case Number  %d\nNumber of Customers: %d\n", case_nr, max_nr_customers);
    printf("Locations recommended:");
    for (int i = 1; max_towers; i++, max_towers >>= 1)
      if (max_towers & 1)
        printf(" %d", i);
    printf("\n\n");
  }
  return 0;
}

UVa 11975 - Tele-loto

Accepted date: 2015-05-15
Ranking (as of 2015-05-15): 27 out of 61
Language: C++

/*
  UVa 11975 - Tele-loto

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

#include <cstdio>

const int nr_balls_max = 75, nr_values = 4, nr_rows = 5, nr_columns = 5;
int balls[nr_balls_max], values[nr_values], ticket[nr_rows][nr_columns],
  findings[nr_rows][nr_columns];

bool corners(int n)
{
  return n >= 4 && findings[0][0] < 35 && findings[0][nr_columns - 1] < 35 &&
    findings[nr_rows - 1][0] < 35 && findings[nr_rows - 1][nr_columns - 1] < 35;
}

bool mid_line(int n)
{
  if (n < nr_columns)
    return false;
  for (int i = 0; i < nr_columns; i++)
    if (findings[2][i] >= 40)
      return false;
  return true;
}

bool diagonals(int n)
{
  return n >= 9 && findings[0][0] < 45 && findings[0][nr_columns - 1] < 45 &&
    findings[1][1] < 45 && findings[1][3] < 45 && findings[2][2] < 45 &&
    findings[3][1] < 45 && findings[3][3] < 45 &&
    findings[nr_rows - 1][0] < 45 && findings[nr_rows - 1][nr_columns - 1] < 45;
}

bool table(int n)
{
  if (n < nr_rows * nr_columns)
    return false;
  for (int i = 0; i < nr_rows; i++)
    for (int j = 0; j < nr_columns; j++)
      if (findings[i][j] == nr_balls_max)
        return false;
  return true;
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, L;
    scanf("%d %d", &N, &L);
    for (int i = 0; i < N; i++)
      scanf("%d", &balls[i]);
    for (int i = 0; i < nr_values; i++)
      scanf("%d", &values[i]);
    printf("Case %d:\n", t);
    while (L--) {
      for (int i = 0; i < nr_rows; i++)
        for (int j = 0; j < nr_columns; j++) {
          scanf("%d", &ticket[i][j]);
          findings[i][j] = nr_balls_max;
        }
      for (int i = 0; i < N; i++) {
        int c = (balls[i] - 1) / 15;
        for (int r = 0; r < nr_rows; r++)
          if (ticket[r][c] == balls[i]) {
            findings[r][c] = i; break;
          }
      }
      int value = 0;
      if (corners(N))
        value += values[0];
      if (mid_line(N))
        value += values[1];
      if (diagonals(N))
        value += values[2];
      if (table(N))
        value += values[3];
      printf("%d\n", value);
    }
    if (t < T)
      putchar('\n');
  }
  return 0;
}

UVa 334 - Identifying Concurrent Events

Accepted date: 2015-05-11
Ranking (as of 2015-05-11): 190 out of 386
Language: C++

/*
  UVa 334 - Identifying Concurrent Events

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

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

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int n = 0, N, NC, NM;
    cin >> NC;
    if (!NC)
      break;
    vector<string> names;
    map<string, int> name_indices;
    set< pair<int, int> > edges;
    while (NC--) {
      cin >> N;
      for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        names.push_back(s);
        name_indices.insert(make_pair(s, n));
        if (i)
          edges.insert(make_pair(n - 1, n));
        n++;
      }
    }
    cin >> NM;
    while (NM--) {
      string s, r;
      cin >> s >> r;
      edges.insert(make_pair(name_indices[s], name_indices[r]));
    }
    vector< vector<bool> > matrix(n, vector<bool>(n, false));
    for (set< pair<int, int> >::const_iterator ei = edges.begin(), ee = edges.end();
      ei != ee; ++ei)
      matrix[ei->first][ei->second] = true;
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        cout << matrix[i][j] << ((j < n - 1) ? ' ' : '\n');
#endif
    // apply Warshall's Transitive Closure algorithm
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          matrix[i][j] = matrix[i][j] || matrix[i][k] && matrix[k][j];
    int nr_events = n * (n - 1) / 2;
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
        if (matrix[i][j] || matrix[j][i])
          nr_events--;

    cout << "Case " << case_nr << ", ";
    if (nr_events) {
      cout << nr_events << " concurrent events:\n";
      if (nr_events > 2)
        nr_events = 2;
      for (int i = 0; i < n - 1 && nr_events; i++)
        for (int j = i + 1; j < n && nr_events; j++)
          if (!matrix[i][j] && !matrix[j][i]) {
            nr_events--;
            cout << '(' << names[i] << ',' << names[j] << ") ";
          }
      cout << endl;
    }
    else
      cout << "no concurrent events.\n";

  }
  return 0;
}

UVa 11047 - The Scrooge Co Problem

Accepted date: 2015-05-09
Ranking (as of 2015-05-09): 56 out of 285
Language: C++

/*
  UVa 11047 - The Scrooge Co Problem

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

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

const int n_max = 99, nr_chars_max = 31;

char names[n_max][nr_chars_max + 1];
int dists[n_max][n_max], nexts[n_max][n_max];

int get_index(int n, const char* name)
{
  for (int i = 0; i < n; i++)
    if (!strcmp(name, names[i]))
      return i;
  return -1;
}

void floyd_warshall_with_path_reconstruction(int n)
{
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      if (dists[i][k] != numeric_limits<int>::max())
        for (int j = 0; j < n; j++)
          if (dists[k][j] != numeric_limits<int>::max() &&
            dists[i][k] + dists[k][j] < dists[i][j]) {
            dists[i][j] = dists[i][k] + dists[k][j];
            nexts[i][j] = nexts[i][k];
          }
}

void print_path(int u, int v)
{
  printf("Path:%s", names[u]);
  do {
    u = nexts[u][v];
    printf(" %s", names[u]);
  } while (u != v);
  putchar('\n');
}

int main()
{
  int C;
  scanf("%d", &C);
  while (C--) {
    int P;
    scanf("%d", &P);
    for (int i = 0; i < P; i++)
      scanf("%s", names[i]);
    for (int i = 0; i < P; i++)
      for (int j = 0; j < P; j++) {
        int C;
        scanf("%d", &C);
        dists[i][j] = (C >= 0) ? C : numeric_limits<int>::max();
        nexts[i][j] = j;
      }
    floyd_warshall_with_path_reconstruction(P);
    int R;
    scanf("%d", &R);
    while (R--) {
      char employee[nr_chars_max + 1], start[nr_chars_max + 1], end[nr_chars_max + 1];
      scanf("%s %s %s", employee, start, end);
      int s = get_index(P, start), e = get_index(P, end);
      if (dists[s][e] != numeric_limits<int>::max()) {
        printf("Mr %s to go from %s to %s, you will receive %d euros\n",
          employee, start, end, dists[s][e]);
        print_path(s, e);
      }
      else
        printf("Sorry Mr %s you can not go from %s to %s\n", employee, start, end);
    }
  }
  return 0;
}

UVa 12319 - Edgetown's Traffic Jams

Accepted date: 2015-05-08
Ranking (as of 2015-05-08): 23 out of 175
Language: C++

/*
  UVa 12319 - Edgetown's Traffic Jams

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

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

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

int main()
{
  while (true) {
    string s;
    getline(cin, s);
    istringstream iss(s);
    int n;
    iss >> n;
    iss.clear();
    if (!n)
      break;
    vector< vector<int> >
      matrix(n + 1, vector<int>(n + 1, numeric_limits<int>::max())),
      pmatrix(n + 1, vector<int>(n + 1, numeric_limits<int>::max()));
    for (int i = 0; i < n; i++) {
      getline(cin, s);
      iss.str(s);
      int j, k;
      iss >> j;
      while (iss >> k)
        matrix[j][k] = 1;
      iss.clear();
    }
    for (int i = 0; i < n; i++) {
      getline(cin, s);
      iss.str(s);
      int j, k;
      iss >> j;
      while (iss >> k)
        pmatrix[j][k] = 1;
      iss.clear();
    }
    int A, B;
    getline(cin, s);
    iss.str(s);
    iss >> A >> B;
    iss.clear();
    floyd_warshall(n, matrix);
    floyd_warshall(n, pmatrix);
    bool yes = true;
    for (int i = 1; i <= n && yes; i++)
      for (int j = 1; j <= n && yes; j++)
        if (i != j)
          if (matrix[i][j] < numeric_limits<int>::max()) {
            if (pmatrix[i][j] == numeric_limits<int>::max() ||
              pmatrix[i][j] > matrix[i][j] * A + B)
              yes = false;
          }
    cout << ((yes) ? "Yes\n" : "No\n");
  }
  return 0;
}

UVa 12498 - Ant's Shopping Mall

Accepted date: 2015-05-06
Ranking (as of 2015-05-06): 67 out of 175
Language: C++

/*
  UVa 12498 - Ant's Shopping Mall

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

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

const int R_max = 50, C_max = 50;

char mall[R_max][C_max + 1];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int R, C;
    scanf("%d %d", &R, &C);
    for (int r = 0; r < R; r++)
      scanf("%s", mall[r]);
    int min_nr_moves = -1;
    for (int c = 0; c < C; c++) {
      int nr_moves = 0;
      for (int r = 0; r < R; r++) {
        int min_nr_column_moves = 0;
        if (mall[r][c] == '1') {
          min_nr_column_moves = C;
          for (int i = c - 1; i >= 0; i--)
            if (mall[r][i] == '0') {
              min_nr_column_moves = c - i;
              break;
            }
          for (int i = c + 1; i < C; i++)
            if (mall[r][i] == '0') {
              min_nr_column_moves = min(min_nr_column_moves, i - c);
              break;
            }
        }
        if (min_nr_column_moves == C) {
          nr_moves = -1;
          break;
        }
        else
          nr_moves += min_nr_column_moves;
      }
      if (nr_moves != -1) {
        if (min_nr_moves == -1)
          min_nr_moves = nr_moves;
        else
          min_nr_moves = min(min_nr_moves, nr_moves);
      }
    }
    printf("Case %d: %d\n", t, min_nr_moves);
  }
  return 0;
}

UVa 945 - Loading a Cargo Ship

Accepted date: 2015-05-04
Ranking (as of 2015-05-04): 3 out of 35
Language: C++

/*
  UVa 945 - Loading a Cargo Ship

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

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

const int c_max = 9, p_max = 999;

struct container {
  int weight_;
  int nr_packages_;
  int packages_[p_max];
} containers[c_max];

int main()
{
  bool printed = false;
  int c;
  while (scanf("%d", &c) != EOF) {
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (int i = 0; i < c; i++) {
      scanf("%d", &containers[i].weight_);
      containers[i].nr_packages_ = 0;
    }
    int p;
    scanf("%d", &p);
    int min_nr_packages = 0, unloaded = 0;
    for (int i = 0; i < p; i++) {
      int weight;
      scanf("%d", &weight);
      if (unloaded) {
        unloaded += weight;
        continue;
      }
      int ci = -1;
      for (int j = 0; j < c; j++)
        if (containers[j].nr_packages_ == min_nr_packages) {
          if (ci == -1 || containers[j].weight_ > containers[ci].weight_)
            ci = j;
        }
      if (ci == -1 || containers[ci].weight_ < weight)
        unloaded += weight;
      else {
        containers[ci].weight_ -= weight;
        containers[ci].packages_[containers[ci].nr_packages_++] = weight;
        min_nr_packages = i + 1;
        for (int j = 0; j < c; j++)
          min_nr_packages = min(min_nr_packages, containers[j].nr_packages_);
      }
    }
    int cargo = 0, unused = 0, max_nr_packages = 0;
    for (int i = 0; i < c; i++) {
      max_nr_packages = max(max_nr_packages, containers[i].nr_packages_);
      unused += containers[i].weight_;
      for (int j = 0; j < containers[i].nr_packages_; j++)
        cargo += containers[i].packages_[j];
    }
    for (int i = max_nr_packages; i > 0; i--)
      for (int j = 0; j < c; j++) {
        if (containers[j].nr_packages_ >= i)
          printf("%d", containers[j].packages_[i - 1]);
        else
          putchar(':');
        printf("%c", (j < c - 1) ? ' ' : '\n');
      }
    for (int i = 0; i < c * 2 - 1; i++)
      putchar('=');
    putchar('\n');
    for (int i = 1; i <= c; i++)
      printf("%d%c", i, ((i < c) ? ' ' : '\n'));
    printf("\ncargo weight: %d\n", cargo);
    printf("unused weight: %d\n", unused);
    printf("unloaded weight: %d\n", unloaded);
  }
  return 0;
}

UVa 949 - Getaway

Accepted date: 2015-05-02
Ranking (as of 2015-05-02): 27 out of 73
Language: C++

/*
  UVa 949 - Getaway

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

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

int main()
{
  const int nr_dirs = 4;
  pair<int, int> dirs[nr_dirs] =
    {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
  int nr, nc;
  while (cin >> nr >> nc) {
    int r;
    cin >> r;
    set< pair< pair<int, int>, pair<int, int> > > restrictions;
    while (r--) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      restrictions.insert(make_pair(make_pair(x1, y1), make_pair(x2, y2)));
    }
    int m;
    cin >> m;
    set< pair<pair<int, int>, int> > monitorizations;
    while (m--) {
      int t, x, y;
      cin >> t >> x >> y;
      monitorizations.insert(make_pair(make_pair(x, y), t));
    }
    queue< pair<pair<int, int>, int> > q;
    vector< vector<int> > arrived(nr, vector<int>(nc, numeric_limits<int>::max()));
    int t = 0;
    while (monitorizations.find(make_pair(make_pair(0, 0), t)) !=
      monitorizations.end())
      t++;
    arrived[0][0] = t;
    q.push(make_pair(make_pair(0, 0), t));
    while (!q.empty()) {
      pair<pair<int, int>, int> u = q.front(); q.pop();
      int ux = u.first.first, uy = u.first.second, ut = u.second;
      for (int i = 0; i < nr_dirs; i++) {
        int x = ux + dirs[i].first, y = uy + dirs[i].second;
        if (x >= 0 && x < nr && y >= 0 && y < nc &&
          restrictions.find(make_pair(make_pair(ux, uy), make_pair(x, y))) ==
            restrictions.end()) {
          int t = ut + 1;
          while (monitorizations.find(make_pair(make_pair(x, y), t)) !=
            monitorizations.end())
            t++;
          if (t < arrived[x][y]) {
            arrived[x][y] = t;
            q.push(make_pair(make_pair(x, y), t));
          }
        }
      }
    }
    cout << arrived[nr - 1][nc - 1] << endl;
  }
  return 0;
}