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