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