UVa 10687 - Monitoring the Amazon

Accepted date: 2015-03-28
Ranking (as of 2015-03-28): 59 out of 407
Language: C++

/*
  UVa 10687 - Monitoring the Amazon

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

#include <queue>
#include <algorithm>
#include <cstdio>
#ifndef ONLINE_JUDGE
#include <cassert>
#endif
using namespace std;

const int N_max = 1000;

struct station {
  int i_;
  int x_, y_;

  station() {}
  station(const station& s) : i_(s.i_), x_(s.x_), y_(s.y_) {}
} stations[N_max];

bool visited[N_max];

struct station_comparator {
  const station& s_;

  station_comparator(const station& s) : s_(s) {}
  bool operator() (const station& si, const station& sj) const {
    if (si.i_ == s_.i_)
      return true;
    else if (sj.i_ == s_.i_)
      return false;
    else {
      int di = (si.x_ - s_.x_) * (si.x_ - s_.x_) + (si.y_ - s_.y_) * (si.y_ - s_.y_),
        dj = (sj.x_ - s_.x_) * (sj.x_ - s_.x_) + (sj.y_ - s_.y_) * (sj.y_ - s_.y_);
      if (di != dj)
        return di < dj;
      else if (si.x_ != sj.x_)
        return si.x_ < sj.x_;
      else
        return si.y_ < sj.y_;
    }
  }
};

void bsf(int N)
{
  queue<station> q;
  visited[0] = true;
  q.push(stations[0]);
  while (!q.empty()) {
    station s = q.front(); q.pop();
    sort(stations, stations + N, station_comparator(s));
#ifndef ONLINE_JUDGE
    assert(s.i_ == stations[0].i_);
#endif
    if (N > 1 && !visited[stations[1].i_]) {
      visited[stations[1].i_] = true;
      q.push(stations[1]);
    }
    if (N > 2 && !visited[stations[2].i_]) {
      visited[stations[2].i_] = true;
      q.push(stations[2]);
    }
  }
}

int main()
{
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    for (int i = 0; i < N; i++) {
      stations[i].i_ = i;
      scanf("%d %d", &stations[i].x_, &stations[i].y_);
      visited[i] = false;
    }
    bsf(N);
    bool reachable = true;
    for (int i = 0; i < N; i++)
      if (!visited[i]) {
        reachable = false;
        break;
      }
    puts((reachable) ?
      "All stations are reachable." : "There are stations that are unreachable.");
  }
  return 0;
}

UVa 12291 - Polyomino Composer

Accepted date: 2015-03-27
Ranking (as of 2015-03-27): 142 out of 176
Language: C++

/*
  UVa 12291 - Polyomino Composer

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

#include <cstdio>

const int nm_max = 10;
char small[nm_max][nm_max + 1], large[nm_max][nm_max + 1];

bool polyomino(int n, int m, int ssi, int ssj)
{
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (large[i][j] == '*') {
        for (int si = 0, li = i - ssi; si < m; si++, li++)
          for (int sj = 0, lj = j - ssj; sj < m; sj++, lj++)
            if (small[si][sj] == '*') {
              if (li < 0 || li >= n || lj < 0 || lj >= n || large[li][lj] != '*')
                return false;
              large[li][lj] = '.';
            }
        return true;
      }
  return false;
}

int main()
{
  while (true) {
    int n, m;
    scanf("%d %d", &n, &m);
    if (!n)
      break;
    for (int i = 0; i < n; i++)
      scanf("%s", large[i]);
    for (int i = 0; i < m; i++)
      scanf("%s", small[i]);
    int ssi = -1, ssj;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++)
        if (small[i][j] == '*') {
          ssi = i, ssj = j;
          break;
        }
      if (ssi != -1)
        break;
    }
    int possible = (polyomino(n, m, ssi, ssj) && polyomino(n, m, ssi, ssj)) ? 1 : 0;
    if (possible) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
          if (large[i][j] == '*') {
            possible = 0;
            break;
          }
        if (!possible)
          break;
      }
    }
    printf("%d\n", possible);
  }
  return 0;
}

UVa 12187 - Brothers

Accepted date: 2015-03-25
Ranking (as of 2015-03-25): 149 out of 234
Language: C++

/*
  UVa 12187 - Brothers

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

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

const int R_max = 100, C_max = 100;

int countries[2][R_max][C_max];

int main()
{
  const int nr_dirs = 4;
  const int dirs[nr_dirs][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  while (true) {
    int N, R, C, K;
    scanf("%d %d %d %d", &N, &R, &C, &K);
    if (!N)
      break;
    int (*pc)[R_max][C_max] = &countries[0], (*cc)[R_max][C_max] = &countries[1];
    for (int i = 0; i < R; i++)
      for (int j = 0; j < C; j++)
        scanf("%d", &(*pc)[i][j]);
    for (int k = 0; k < K; k++) {
      for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
          (*cc)[i][j] = (*pc)[i][j];
      for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
          for (int d = 0; d < nr_dirs; d++) {
            int r = i + dirs[d][0], c = j + dirs[d][1];
            if (r >= 0 && r < R && c >= 0 && c < C) {
              int h = (*pc)[r][c];
              if (!h)
                h = N;
              if ((*pc)[i][j] + 1 == h)
                (*cc)[r][c] = (*pc)[i][j];
            }
          }
      swap(pc, cc);
    }
    for (int i = 0; i < R; i++)
      for (int j = 0; j < C; j++)
        printf("%d%c", (*pc)[i][j], ((j < C - 1) ? ' ' : '\n'));
  }
  return 0;
}

UVa 1061 - Consanguine Calculations

Accepted date: 2015-03-18
Ranking (as of 2015-03-18): 145 out of 209
Language: C++

/*
  UVa 1061 - Consanguine Calculations

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

#include <cstdio>
#include <cstring>

enum {A_allele, B_allele, O_allele};
enum {A_type, AB_type, B_type, O_type};
enum {Rh_positive, Rh_negative};

const int nr_blood_types = O_type - A_type + 1;

struct blood_types {
  int ctr_;
  bool types_[nr_blood_types];
};

blood_types parent_other_parent[nr_blood_types][nr_blood_types] = {
  { // A
    {2, {true,  false,  false,  true}},   // A
    {3, {true,  true, true, false}},  // AB
    {4, {true,  true,   true, true}},   // B
    {2, {true,  false,  false,  true}}    // O
  },
  { // AB
    {3, {true,  true, true, false}},  // A
    {3, {true,  true, true, false}},  // AB
    {3, {true,  true, true, false}},  // B
    {2, {true,  false,  true, false}}   // O
  },
  { // B
    {4, {true,  true,   true, true}},   // A
    {3, {true,  true, true, false}},  // AB
    {2, {false, false,  true, true}},   // B
    {2, {false, false,  true, true}},   // O
  },
  { // O
    {2, {true,  false,  false,  true}},   // A
    {2, {true,  false,  true, false}},  // AB
    {2, {false, false,  true, true}},   // B
    {1, {false, false,  false,  true}}    // O
  }
};

blood_types parent_child[nr_blood_types][nr_blood_types] = {
  { // A
    {4, {true,  true, true, true}},   // A
    {2, {false, true, true, false}},  // AB
    {2, {false, true, true, false}},  // B
    {3, {true,  false,  true, true}},   // O
  },
  { // AB
    {4, {true,  true, true, true}},   // A
    {3, {true,  true, true, false}},  // AB
    {4, {true,  true, true, true}},   // B
    {0, {false, false,  false,  false}},  // O
  },
  { // B
    {2, {true,  true, false,  false}},  // A
    {2, {true,  true, false,  false}},  // AB
    {4, {true,  true, true, true}},   // B
    {3, {true,  false,  true, true}},   // O
  },
  { // O
    {2, {true,  true, false,  false}},  // A
    {0, {false, false,  false,  false}},  // AB
    {2, {false, true, true, false}},  // B
    {3, {true,  false,  true, true}},   // O
  }
};

const char* blood_symbols[nr_blood_types] = {"A", "AB", "B", "O"};

void get_blood_type_and_rh_factor(const char* s, int& blood_type, int& rh_factor) {
  int length = strlen(s);
  if (length < 3) {
    switch (s[0]) {
    case 'A':
      blood_type = A_type; break;
      break;
    case 'B':
      blood_type = B_type; break;
      break;
    case 'O':
      blood_type = O_type; break;
      break;
    }
  }
  else
    blood_type = AB_type;
  rh_factor = (s[length - 1] == '+') ? Rh_positive : Rh_negative;
}

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    const int nr_chars_max = 3;
    char parent[nr_chars_max + 1], other_parent[nr_chars_max + 1],
      child[nr_chars_max + 1];
    scanf("%s %s %s", parent, other_parent, child);
    if (parent[0] == 'E')
      break;
    if (parent[0] == '?') {
      int parent_type, parent_factor, child_type, child_factor;
      get_blood_type_and_rh_factor(other_parent, parent_type, parent_factor);
      get_blood_type_and_rh_factor(child, child_type, child_factor);
      blood_types& bt = parent_child[parent_type][child_type];
      if (bt.ctr_) {
        bool factor_positive_only =
          parent_factor == Rh_negative && child_factor == Rh_positive;
        printf("Case %d: ", case_nr);
        if (bt.ctr_ > 1 || !factor_positive_only)
          putchar('{');
        for (int i = 0, j = 0; i < nr_blood_types; i++)
          if (bt.types_[i]) {
            if (j++)
              printf(", ");
            if (factor_positive_only)
              printf("%s+", blood_symbols[i]);
            else
              printf("%s+, %s-", blood_symbols[i], blood_symbols[i]);
          }
        if (bt.ctr_ > 1 || !factor_positive_only)
          putchar('}');
        printf(" %s %s\n", other_parent, child);
      }
      else
        printf("Case %d: IMPOSSIBLE %s %s\n", case_nr, other_parent, child);
    }
    else if (other_parent[0] == '?') {
      int parent_type, parent_factor, child_type, child_factor;
      get_blood_type_and_rh_factor(parent, parent_type, parent_factor);
      get_blood_type_and_rh_factor(child, child_type, child_factor);
      blood_types& bt = parent_child[parent_type][child_type];
      if (bt.ctr_) {
        bool factor_positive_only =
          parent_factor == Rh_negative && child_factor == Rh_positive;
        printf("Case %d: %s ", case_nr, parent);
        if (bt.ctr_ > 1 || !factor_positive_only)
          putchar('{');
        for (int i = 0, j = 0; i < nr_blood_types; i++)
          if (bt.types_[i]) {
            if (j++)
              printf(", ");
            if (factor_positive_only)
              printf("%s+", blood_symbols[i]);
            else
              printf("%s+, %s-", blood_symbols[i], blood_symbols[i]);
          }
        if (bt.ctr_ > 1 || !factor_positive_only)
          putchar('}');
        printf(" %s\n", child);
      }
      else
        printf("Case %d: %s IMPOSSIBLE %s\n", case_nr, parent, child);
    }
    else {
      int parent_type, parent_factor, other_parent_type, other_parent_factor;
      get_blood_type_and_rh_factor(parent, parent_type, parent_factor);
      get_blood_type_and_rh_factor(other_parent,
        other_parent_type, other_parent_factor);
      blood_types& bt = parent_other_parent[parent_type][other_parent_type];
      bool factor_negative_only =
        parent_factor == Rh_negative && other_parent_factor == Rh_negative;
      printf("Case %d: %s %s ", case_nr, parent, other_parent);
      if (bt.ctr_ > 1 || !factor_negative_only)
        putchar('{');
      for (int i = 0, j = 0; i < nr_blood_types; i++)
        if (bt.types_[i]) {
          if (j++)
            printf(", ");
          if (factor_negative_only)
            printf("%s-", blood_symbols[i]);
          else
            printf("%s+, %s-", blood_symbols[i], blood_symbols[i]);
          }
      if (bt.ctr_ > 1 || !factor_negative_only)
        puts("}");
      else
        putchar('\n');
    }
  }
  return 0;
}

UVa 11717 - Energy Saving Microcontroller

Accepted date: 2015-03-15
Ranking (as of 2015-03-15): 96 out of 252
Language: C++

/*
  UVa 11717 - Energy Saving Microcontroller

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

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int n, i, k;
    scanf("%d %d %d", &n, &i, &k);
    bool active = true;
    int nr_inactive = 0, nr_ignored = 0, last_active = 0, next_active;
    while (n--) {
      int ms;
      scanf("%d", &ms);
      if (active) {
        if (ms < last_active + i)
          last_active = ms;
        else {
          active = false;
          nr_inactive++;
          next_active = ms + k;
        }
      }
      else {
        if (ms < next_active)
          nr_ignored++;
        else if (ms < next_active + i) {
          active = true;
          last_active = ms;
        }
        else {
          nr_inactive++;
          next_active = ms + k;
        }
      }
    }
    printf("Case %d: %d %d\n", t, nr_inactive, nr_ignored);
  }
  return 0;
}

UVa 12608 - Garbage Collection

Accepted date: 2015-03-15
Ranking (as of 2015-03-15): 32 out of 170
Language: C++

/*
  UVa 12608 - Garbage Collection

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

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int W, N;
    scanf("%d %d", &W, &N);
    int d = 0, w = 0, wi, pxi = 0, xi;
    while (N--) {
      scanf("%d %d", &xi, &wi);
      d += xi - pxi;
      w += wi;
      if (w > W) {
        d += xi * 2;
        if (wi == W) {
          if (N)
            d += xi * 2;
          w = 0;
        }
        else
          w = wi;
      }
      else if (w == W) {
        if (N)
          d += xi * 2;
        w = 0;
      }
      pxi = xi;
#ifdef DEBUG
      printf("   %d %d\n", d, w);
#endif
    }
    d += pxi;
    printf("%d\n", d);
  }
  return 0;
}

UVa 603 - Parking Lot

Accepted date: 2015-03-13
Ranking (as of 2015-03-13): 25 out of 375
Language: C++

/*
  UVa 603 - Parking Lot

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

#include <cstdio>

const int nr_cars_max = 20;

struct car {
  int original_, parked_, current_;
} cars[nr_cars_max + 1];

int main()
{
  int nr_sets;
  scanf("%d", &nr_sets);
  getchar();
  getchar(); // skip a blank line
  while (nr_sets--) {
    int nr_cars;
    for (nr_cars = 0; ; nr_cars++) {
      car& c = cars[nr_cars];
      scanf("%d", &c.original_);
      if (c.original_ == 99)
        break;
      c.parked_ = 0;
      c.current_ = c.original_;
    }
    getchar();
    while (true) {
      int cc;
      if ((cc = getchar()) == '\n' || cc == EOF)
        break;
      ungetc(cc, stdin);
      int p;
      scanf("%d", &p);
      getchar();
      int min_d = nr_cars_max + 1, min_i;
      for (int i = 0; i < nr_cars; i++) {
        car& c = cars[i];
        if (!c.parked_) {
          int d = p - c.current_;
          if (d < 0)
            d += nr_cars_max;
          if (d < min_d) {
            min_d = d; min_i = i;
          }
        }
      }
      for (int i = 0; i < nr_cars; i++) {
        car& c = cars[i];
        if (!c.parked_) {
          c.current_ += min_d;
          if (c.current_ > nr_cars_max)
            c.current_ -= nr_cars_max;
          if (i == min_i)
            c.parked_ = c.current_;
        }
      }
    }
    for (int i = 0; i < nr_cars; i++) {
      const car& c = cars[i];
      if (c.parked_)
        printf("Original position %d parked in %d\n", c.original_, c.parked_);
      else
        printf("Original position %d did not park\n", c.original_);
    }
    if (nr_sets)
      putchar('\n');
  }
  return 0;
}

UVa 405 - Message Routing

Accepted date: 2015-03-12
Language: C++

/*
  UVa 405 - Message Routing

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

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

const int M_max = 10, I_max = 9, nr_components = 4, nr_chars_max = 15;

struct routing_table {
  int mi_;
  char components_[nr_components][nr_chars_max + 1];
};

struct mta {
  int nr_tables_;
  routing_table routing_tables_[I_max];
} mtas[M_max];

string mta_names[M_max];
bool routed[M_max];

int main()
{
  int M;
  char s[nr_chars_max + 1];
  for (int scenario_nr = 1; scanf("%d", &M) != EOF; scenario_nr++) {
    map<string, int> mta_name_indices;
    for (int i = 0; i < M; i++) {
      int I;
      scanf("%s %d", s, &I);
      pair<map<string, int>::iterator, bool> result =
        mta_name_indices.insert(make_pair(s, static_cast<int>(mta_name_indices.size())));
      mta_names[result.first->second] = result.first->first;
      mta& m = mtas[result.first->second];
      m.nr_tables_ = I;
      for (int j = 0; j < I; j++) {
        scanf("%s", s);
        pair<map<string, int>::iterator, bool> result =
          mta_name_indices.insert(make_pair(s, static_cast<int>(mta_name_indices.size())));
        routing_table& r = m.routing_tables_[j];
        r.mi_ = result.first->second;
        for (int k = 0; k < nr_components; k++)
          scanf("%s", &r.components_[k]);
      }
    }
    printf("Scenario # %d\n", scenario_nr);
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < M; j++)
        routed[j] = false;
      routing_table r;
      scanf("%s", s);
      routed[r.mi_ = mta_name_indices[s]] = true;
      for (int j = 0; j < nr_components; j++)
        scanf("%s", &r.components_[j]);
      while (true) {
        mta& m = mtas[r.mi_];
        int j;
        for (j = 0; j < m.nr_tables_; j++) {
          routing_table& mr = m.routing_tables_[j];
          int k;
          for (k = 0; k < nr_components; k++)
            if (mr.components_[k][0] != '*' &&
              strcmp(mr.components_[k], r.components_[k]))
              break;
          if (k == nr_components) // found
            break;
        }
        if (j < m.nr_tables_) { // found
          if (r.mi_ == m.routing_tables_[j].mi_) {
            printf("%d -- delivered to %s\n", i, mta_names[r.mi_].c_str());
            break;
          }
          else if (routed[m.routing_tables_[j].mi_]) {
            printf("%d -- circular routing detected by %s\n",
              i, mta_names[m.routing_tables_[j].mi_].c_str());
            break;
          }
          else
            routed[r.mi_ = m.routing_tables_[j].mi_] = true;
        }
        else {
          printf("%d -- unable to route at %s\n", i, mta_names[r.mi_].c_str());
          break;
        }
      }
    }
    putchar('\n');
  }
  return 0;
}

UVa 449 - Majoring in Scales

Accepted date: 2015-03-11
Ranking (as of 2015-03-11): 14 out of 161
Language: C++

/*
  UVa 449 - Majoring in Scales

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

#include <cstdio>
#include <cstring>

const int nr_keys = 12, nr_notes = 7, nr_intervals = 7;

const char* major_keys[nr_keys][nr_notes] = {
  {"C", "D",  "E",  "F",  "G",  "A",  "B"},
  {"Db",  "Eb", "F",  "Gb", "Ab", "Bb", "C"},
  {"D", "E",  "F#", "G",  "A",  "B",  "C#"},
  {"Eb",  "F",  "G",  "Ab", "Bb", "C",  "D"},
  {"E", "F#", "G#", "A",  "B",  "C#", "D#"},
  {"F", "G",  "A",  "Bb", "C",  "D",  "E"},
  {"Gb",  "Ab", "Bb",   "Cb", "Db", "Eb", "F"},
  {"G", "A",  "B",  "C",  "D",  "E",  "F#"},
  {"Ab",  "Bb", "C",  "Db", "Eb", "F",  "G"},
  {"A", "B",  "C#", "D",  "E",  "F#", "G#"},
  {"Bb",  "C",  "D",  "Eb", "F",  "G",  "A"},
  {"B", "C#", "D#", "E",  "F#", "G#", "A#"}
};

const char* intervals[nr_intervals] = {
  "OCTAVE", "SECOND", "THIRD", "FOURTH", "FIFTH", "SIXTH", "SEVENTH"
};

int main()
{
  int i, n;
  char scale[4];
  while (scanf("%s", scale) != EOF) {
    const char* (*pkey)[nr_notes];
    for (i = 0; i < nr_keys; i++)
      if (!strcmp(scale, major_keys[i][0])) {
        pkey = &major_keys[i];
        break;
      }
    printf("Key of %s\n", scale);
    char note[4], dir[8], interval[16];
    scanf("%s %s %s", note, dir, interval);
    while (true) {
      char* p = strchr(interval, ';');
      bool next = false;
      if (p) {
        *p = '\0';
        next = true;
      }
      for (n = 0; n < nr_notes; n++)
        if (!strcmp(note, (*pkey)[n]))
          break;
      if (n == nr_notes)
        printf("%s: invalid note for this key\n", note);
      else {
        for (i = 0; i < nr_intervals; i++)
          if (!strcmp(interval, intervals[i]))
            break;
        if (dir[0] == 'U') {
          n += i;
          if (n >= nr_notes)
            n -= nr_notes;
        }
        else {
          n -= i;
          if (n < 0)
            n += nr_notes;
        }
        printf("%s: %s %s > %s\n", note, dir, interval, (*pkey)[n]);
      }
      if (next) {
        strcpy(note, p + 1);
        scanf("%s %s", dir, interval);
      }
      else
        break;
    }
    putchar('\n');
  }
  return 0;
}

UVa 349 - Transferable Voting (II)

Accepted date: 2015-03-10
Language: C++

/*
  UVa 349 - Transferable Voting (II)

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

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

const int nr_votes_max = 100, nr_candidates_max = 5;

struct ballot {
  int ci_;
    // index to the next choices_[], or -1, if no more choices_[] will be examined
  bool votes_[nr_candidates_max + 1];
  int choices_[nr_candidates_max];
} ballots[nr_votes_max];

int votes[nr_candidates_max + 1];
  // votes[i] is the number of votes for the candidate of i, 
  // or -1 for eliminated candidates

int main()
{
  for (int e = 1; ; e++) {
    int c, n;
    scanf("%d %d", &c, &n);
    if (!c && !n)
      break;
    int nr_ballots = 0, nr_bad_ballots = 0;
    memset(votes, 0, sizeof(votes));
    for (int i = 0; i < n; i++) {
      ballot& b = ballots[nr_ballots];
      memset(b.votes_, 0, sizeof(b.votes_));
      bool bad = false;
      for (int j = 0; j < c; j++) {
        scanf("%d", &b.choices_[j]);
        if (b.choices_[j] < 1 || b.choices_[j] > c || b.votes_[b.choices_[j]])
          bad = true;
        else
          b.votes_[b.choices_[j]] = true;
      }
      if (bad)
        nr_bad_ballots++;
      else {
        b.ci_ = 0;
        nr_ballots++;
      }
    }
    int nr_majority = nr_ballots / 2 + 1;
    int max_votes, min_votes, max_c, min_c;
    for (int cc = c; cc > 1; cc--) {
      for (int i = 0; i < nr_ballots; i++) {
        ballot& b = ballots[i];
        if (b.ci_ != -1)
          votes[b.choices_[b.ci_]]++;
      }
      max_votes = 0, min_votes = nr_ballots + 1;
      for (int i = 1; i <= c; i++)
        if (votes[i] != -1) {
          max_votes = max(max_votes, votes[i]);
          min_votes = min(min_votes, votes[i]);
        }
      max_c = -1, min_c = -1;
      for (int i = 1; i <= c; i++) {
        if (votes[i] == max_votes) {
          if (max_c == -1)
            max_c = i;
          else
            max_c = -1;
        }
        if (votes[i] == min_votes) {
          if (min_c == -1)
            min_c = i;
        }
      }
      if (max_votes >= nr_majority && max_c != -1)
        break; // one candidate is elected
      else {
        for (int i = 0; i < n; i++) {
          ballot& b = ballots[i];
          if (b.choices_[b.ci_] == min_c)
            b.ci_++;
          else
            b.ci_ = -1;
        }
      }
    }
    printf("Election #%d\n", e);
    if (nr_bad_ballots)
      printf("   %d bad ballot(s)\n", nr_bad_ballots);
    if (max_c != -1)
      printf("   Candidate %d is elected.\n", max_c);
    else {
      printf("   The following candidates are tied:");
      for (int i = 1; i <= c; i++)
        if (votes[i] == max_votes)
          printf(" %d", i);
      putchar('\n');
    }
  }
  return 0;
}

UVa 335 - Processing MX Record

Accepted date: 2015-03-08
Ranking (as of 2015-03-08): 34 out of 225
Language: C++

/*
  UVa 335 - Processing MX Records

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

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

struct MX_record {
  vector<string> pieces_;
  bool operational_;
  int preference_;
  string redirected_name_;
};

void get_pieces(const string& s, vector<string>& pieces)
{
  for (const char *p = s.c_str(), *q = p; *p; ) {
    while (*p && *p != '.')
      p++;
    pieces.push_back(string(q, p - q));
    if (*p)
      q = ++p;
  }
}

bool compare_pieces(const vector<string>& vs, const vector<string>& vt)
{
  int i = vs.size() - 1, j = vt.size() - 1;
  for( ; i >= 0 && j >= 0; i--, j--) {
    if (vs[i] == "*" || vt[j] == "*")
      return true;
    else if (vs[i] != vt[j])
      return false;
  }
  return (i == -1 && j == -1) ? true : false;
}

int main()
{
  string s, line;
  getline(cin, line);
  istringstream iss(line);
  int N;
  iss >> N;
  iss.clear();
  vector<MX_record> MX_records(N);
  for (int i = 0; i < N; i++) {
    MX_records[i].operational_ = true;
    getline(cin, line);
    iss.str(line);
    if (line[0] != ' ') {
      iss >> s;
      get_pieces(s, MX_records[i].pieces_);
    }
    else
      MX_records[i].pieces_ = MX_records[i - 1].pieces_;
    iss >> MX_records[i].preference_ >> MX_records[i].redirected_name_;
    iss.clear();
  }
  while (true) {
    getline(cin, line);
    if (line[0] == 'X')
      break;
    else {
      iss.str(line);
      char c;
      iss >> c >> s;
      iss.clear();
      switch (c) {
      case 'A':
      {
        vector<string> pieces;
        get_pieces(s, pieces);
        int ri = -1;
        for (int i = 0; i < N; i++)
          if (compare_pieces(pieces, MX_records[i].pieces_)) {
            if (MX_records[i].operational_ &&
              (ri == -1 || MX_records[ri].preference_ > MX_records[i].preference_))
              ri = i;
          }
        cout << s << " =>";
        if (ri != -1)
          cout << ' ' << MX_records[ri].redirected_name_;
        cout << endl;
      }
        break;
      case 'U':
        for (int i = 0; i < N; i++)
          if (MX_records[i].redirected_name_ == s)
            MX_records[i].operational_ = true;
        break;
      case 'D':
        for (int i = 0; i < N; i++)
          if (MX_records[i].redirected_name_ == s)
            MX_records[i].operational_ = false;
        break;
      }
    }
  }
  return 0;
}

UVa 11860 - Document Analyzer

Accepted date: 2015-03-07
Ranking (as of 2015-03-07): 12 out of 179
Language: C++

/*
  UVa 11860 - Document Analyzer

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

#include <string>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
using namespace std;

const int nr_words_max = 100000;
int positions[nr_words_max]; // positions[i] is the word number of i-th word
int word_ctrs[nr_words_max]; // word_ctrs[i] is the number of word whose number is i

int main()
{
  int T;
  scanf("%d", &T);
  while (getchar() != '\n')
    ;
  for (int t = 1; t <= T; t++) {
    int nr_words = 0, nr_positions = 0;
    map<string, int> words;
    while (true) {
      const int nr_chars_max = 150;
      char s[nr_chars_max + 1];
      gets(s);
      if (strstr(s, "END"))
        break;
      for (const char *ps = s, *qs = s; *ps; ) {
        while (*ps && !islower(*ps))
          ps++;
        if (*ps) {
          qs = ps++;
          while (*ps && islower(*ps))
            ps++;
          pair<map<string, int>::iterator, bool> result =
            words.insert(make_pair(string(qs, ps - qs), nr_words));
          positions[nr_positions++] = result.first->second;
          if (result.second)
            word_ctrs[nr_words++] = 0;
        }
      }
    }
    int min_p = 0, min_q = nr_positions, nr = 0;
    for (int p = 0, q = 0; p < nr_positions && q <= nr_positions; ) {
      if (nr == nr_words) {
        if (q - p < min_q - min_p)
          min_p = p, min_q = q;
        if (!--word_ctrs[positions[p]])
          nr--;
        p++;
      }
      else {
        if (q < nr_positions && !word_ctrs[positions[q]]++)
          nr++;
        q++;
      }
    }
    printf("Document %d: %d %d\n", t, min_p + 1, min_q);
  }
  return 0;
}

UVa 11348 - Exhibition

Accepted date: 2015-03-03
Ranking (as of 2015-03-03): 157 out of 326
Language: C++

/*
  UVa 11348 - Exhibition

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

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

int main()
{
  int K;
  scanf("%d", &K);
  for (int k = 1; k <= K; k++) {
    int N;
    scanf("%d", &N);
    map< int, set<int> > stamps;
      // key is  the type of stamp, value is the indices of friends who own the stamp
    for (int i = 0; i < N; i++) {
      int M;
      scanf("%d", &M);
      while (M--) {
        int A;
        scanf("%d", &A);
        pair<map< int, set<int> >::iterator, bool>
          result = stamps.insert(make_pair(A, set<int>()));
        result.first->second.insert(i);
      }
    }
    int ctr = 0;
    vector<int> unique_stamp_ctrs(N, 0);
    for (map< int, set<int> >::const_iterator i = stamps.begin(), e = stamps.end();
      i != e; ++i)
      if (i->second.size() == 1) {
        ctr++;
        unique_stamp_ctrs[*i->second.begin()]++;
      }
    printf("Case %d:", k);
    if (ctr)
      for (size_t i = 0; i < N; i++)
        printf(" %.6lf%%", (static_cast<double>(unique_stamp_ctrs[i]) * 100.0) /
          static_cast<double>(ctr));
    putchar('\n');
  }
  return 0;
}

UVa 11906 - Knight in a War Grid

Accepted date: 2015-03-02
Ranking (as of 2015-03-02): 152 out of 418
Language: C++

/*
  UVa 11906 - Knight in a War Grid

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

#include <cstdio>

const int R_max = 100, C_max = 100;

int R, C, M, N;
bool visited[R_max][C_max];
int grid[R_max][C_max];
  // grid[r][c] is the number of squares from which the knight can reach grid[r][c]
  // -1 for the ones that the knight cannot reach, -2 for the ones containing water

void dfs(int r, int c)
{
  visited[r][c] = true;
  const int nr_dirs = 4;
  const int dirs[nr_dirs][2] = {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
  int ctr = 0;
  if (!M) {
    for (int i = 0; i < nr_dirs / 2; i++) {
      int nr = r + N * dirs[i][0];
      if (nr >= 0 && nr < R && grid[nr][c] != -2) {
        ctr++;
        if (!visited[nr][c])
          dfs(nr, c);
      }
    }
    for (int i = 0; i < nr_dirs / 2; i++) {
      int nc = c + N * dirs[i][0];
      if (nc >= 0 && nc < C && grid[r][nc] != -2) {
        ctr++;
        if (!visited[r][nc])
          dfs(r, nc);
      }
    }
  }
  else if (!N) {
    for (int i = 0; i < nr_dirs / 2; i++) {
      int nr = r + M * dirs[i][0];
      if (nr >= 0 && nr < R && grid[nr][c] != -2) {
        ctr++;
        if (!visited[nr][c])
          dfs(nr, c);
      }
    }
    for (int i = 0; i < nr_dirs / 2; i++) {
      int nc = c + M * dirs[i][0];
      if (nc >= 0 && nc < C && grid[r][nc] != -2) {
        ctr++;
        if (!visited[r][nc])
          dfs(r, nc);
      }
    }
  }
  else {
    for (int i = 0; i < nr_dirs; i++) {
      int nr = r + M * dirs[i][0], nc = c + N * dirs[i][1];
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != -2) {
        ctr++;
        if (!visited[nr][nc])
          dfs(nr, nc);
      }
    }
    if (M != N)
      for (int i = 0; i < nr_dirs; i++) {
        int nr = r + N * dirs[i][0], nc = c + M * dirs[i][1];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != -2) {
          ctr++;
          if (!visited[nr][nc])
            dfs(nr, nc);
        }
      }
  }
  grid[r][c] = ctr;
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int W;
    scanf("%d %d %d %d %d", &R, &C, &M, &N, &W);
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++) {
        visited[r][c] = false;
        grid[r][c] = -1;
      }
    while (W--) {
      int r, c;
      scanf("%d %d", &r, &c);
      grid[r][c] = -2;
    }
    dfs(0, 0);
    int even = 0, odd = 0;
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++)
        if (grid[r][c] >= 0) {
          if (grid[r][c] & 1)
            odd++;
          else
            even++;
        }
    printf("Case %d: %d %d\n", t, even, odd);
  }
  return 0;
}

UVa 790 - Head Judge Headache

Accepted date: 2015-03-01
Ranking (as of 2015-03-01): 41 out of 157
Language: C++

/*
  UVa 790 - Head Judge Headache

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

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

const int nr_teams_max = 25, nr_problems = 'G' - 'A' + 1;

struct submission {
  int time_;
  char status_; // 'Y' or 'N'

  submission() {}
  submission(int time, char status) : time_(time), status_(status) {}

  bool operator<(const submission& s) const
  {
    if (time_ != s.time_)
      return time_ < s.time_;
    else
      return status_ < s.status_;
  }
};

struct team {
  int nr_;
  int nr_solved_;
  int time_consumed_;
  vector< vector<submission> > submissions_;

  team() : nr_(nr_teams_max + 1), nr_solved_(0), time_consumed_(0),
    submissions_(nr_problems, vector<submission>()) {}

  bool operator<(const team& t) const
  {
    if (nr_solved_ != t.nr_solved_)
      return nr_solved_ > t.nr_solved_;
    else if (time_consumed_ != t.time_consumed_)
      return time_consumed_ < t.time_consumed_;
    else
      return nr_ < t.nr_;
  }
};

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  int nr_cases;
  iss.str(line);
  iss >> nr_cases;
  iss.clear();
  getline(cin, line);
  while (nr_cases--) {
    vector<team> teams(nr_teams_max);
    int nr_max = 0;
    while (getline(cin, line) && !line.empty()) {
      iss.str(line);
      int nr, h, m;
      char pl, sr, c;
      iss >> nr >> pl >> h >> c >> m >> sr;
      iss.clear();
      if (nr > nr_max)
        nr_max = nr;
      teams[nr - 1].submissions_[pl - 'A'].push_back(submission(h * 60 + m, sr));
    }
    for (int i = 0; i < nr_teams_max; i++)
      if (i < nr_max) {
        team& t = teams[i];
        t.nr_ = i + 1;
        for (int j = 0; j < nr_problems; j++) {
          vector<submission>& submissions = t.submissions_[j];
          sort(submissions.begin(), submissions.end());
          for (int k = 0; k < submissions.size(); k++)
            if (submissions[k].status_ == 'Y') {
              t.nr_solved_++;
              t.time_consumed_ += submissions[k].time_ + k * 20;
              break;
            }
        }
      }
    sort(teams.begin(), teams.begin() + nr_teams_max);
    cout << "RANK TEAM PRO/SOLVED TIME\n";
    for (int i = 0, rank = 0; i < nr_teams_max && teams[i].nr_ <= nr_teams_max; i++) {
      if (!i || teams[i].nr_solved_ != teams[i - 1].nr_solved_ ||
        teams[i].time_consumed_ != teams[i - 1].time_consumed_)
        rank = i + 1;
      if (teams[i].nr_solved_)
        cout << setw(4) << rank << setw(5) << teams[i].nr_ << setw(5) <<
          teams[i].nr_solved_ << setw(11) << teams[i].time_consumed_ << endl;
      else
        cout << setw(4) << rank << setw(5) << teams[i].nr_ << endl;
    }
    if (nr_cases)
      cout << endl;
  }
  return 0;
}