UVa 158 - Calendar

Accepted date: 2016-11-27
Run Time: 0.000
Ranking (as of 2016-11-27): 122 out of 365
Language: C++

For clarifying the problem description, see 158 - Calendar - UVa OJ Board - UVa Online Judge.
For a specified date, calculated the number of days from the date and the number of stars ('*') that should be printed of each anniversary, and then printed the anniversaries that should be printed (i.e., that have at least one stars).

/*
  UVa 158 - Calendar

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

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

const int nr_chars_max = 255;

struct anniversary {
  int i_;
  int d_, m_, p_;
  int nr_days_; // number of days from the specified date
  int nr_stars_; // number of stars that should be printed
  anniversary(int i) : i_(i) {}

  bool operator<(const anniversary& a) const
  {
    if (nr_days_ != a.nr_days_)
      return nr_days_ < a.nr_days_;
    else if (!nr_days_)
      return i_ < a.i_;
    else if (nr_stars_ != a.nr_stars_)
      return nr_stars_ > a.nr_stars_;
    else
      return i_ < a.i_;
  }
};

struct description {
  char s_[nr_chars_max + 1];

  description() {}
};

vector<anniversary> anniversaries;
vector<description> descriptions;

inline bool is_leap_year(int year)
{
  if (!(year % 400))
    return true;
  else if (!(year % 100))
    return false;
  else if (!(year % 4))
    return true;
  else
    return false;
}

int get_number_of_days(int year) // return the number of days of given year
{
  return (is_leap_year(year)) ? 366 : 365;
}

int get_number_of_days(int year, int month, int date)
// return the number of days from the first day of given year
{
  const int nr_days[] = {0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    // nr_days[i] is the number of days before the first day of i-th month
  const int nr_days_leap_year[] = {0, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};
    // nr_days[i] is the number of days before the first day of i-th month for leap years
  int nd = date;
  nd += (is_leap_year(year)) ? nr_days_leap_year[month] : nr_days[month];
  return nd;
}

const char* stars[] = {
  " *TODAY* ", " *       ", " **      ", " ***     ",
  " ****    ", " *****   ", " ******  ", " ******* "
};

int main()
{
  int year;
  scanf("%d", &year);
  while (getchar() != '\n')
    ;
  char s[nr_chars_max + 1];
  int nr_anniversaries = 0;
  while (true) {
    gets(s);
    if (s[0] != 'A')
      break;
    anniversaries.push_back(anniversary(nr_anniversaries)),
      descriptions.push_back(description());
    char* p;
    anniversary& a = anniversaries.back();
    a.d_ = strtol(&s[1], &p, 10);
    a.m_ = strtol(p, &p, 10);
    a.p_ = strtol(p, &p, 10);
    while (isspace(*p))
      p++;
    strcpy(descriptions.back().s_, p);
    nr_anniversaries++;
  }
  bool printed = false;
  while (s[0] != '#') {
    if (printed)
      putchar('\n');
    else
      printed = true;
    char* p;
    int date = strtol(&s[1], &p, 10);
    int month = strtol(p, NULL, 10);
    int nr_days = get_number_of_days(year, month, date);
    for (int i = 0; i < nr_anniversaries; i++) {
      anniversary& a = anniversaries[i];
      int nr = (a.m_ < month || a.m_ == month && a.d_ < date) ?
        get_number_of_days(year) + get_number_of_days(year + 1, a.m_, a.d_) :
        get_number_of_days(year, a.m_, a.d_);
      a.nr_days_ = nr - nr_days;
      a.nr_stars_ = (a.nr_days_ <= 7) ? a.p_ - a.nr_days_ + 1: -1;
    }
    sort(anniversaries.begin(), anniversaries.end());
    printf("Today is:%3d%3d\n", date, month);
    for (int i = 0; i < nr_anniversaries; i++) {
      const anniversary& a = anniversaries[i];
      if (/* a.nr_days_ > 7 || */ a.nr_stars_ <= 0)
        break;
      printf("%3d%3d%s%s\n", a.d_, a.m_,
        ((a.nr_days_) ? stars[a.nr_stars_] : stars[0]), descriptions[a.i_].s_);
    }
    gets(s);
  }
  return 0;
}

UVa 12186 - Another Crisis

Accepted date: 2016-11-24
Run Time: 0.070
Ranking (as of 2016-11-24): 56 out of 403
Language: C++

Applied dynamic programming.
Caluculated the number of workers who should file a petition to a boss by choosing the necessary number of subordinates by ascending order of their workers who, in turn, should file a petition to them.
Did this calculation recursively.

/*
  UVa 12186 - Another Crisis

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

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

const int N_max = 100000;
int N;
double T;
vector<int> subordinates[N_max + 1];
int nr_workers[N_max + 1];
  // nr_workds[i] is the number of workers who should file a petition to i-th boss

int file_petitions(int bi)
{
  int& nr = nr_workers[bi];
  if (nr != -1)
    return nr;
  const vector<int>& sbs = subordinates[bi];
  if (sbs.empty())
    return nr = 1;
  vector<int> nrs;
  for (size_t i = 0; i < sbs.size(); i++)
    nrs.push_back(file_petitions(sbs[i]));
  sort(nrs.begin(), nrs.end());
  nr = 0;
  for (size_t i = 0, min_nr = static_cast<size_t>(ceil(sbs.size() * T)); i < min_nr; i++)
    nr += nrs[i];
  return nr;
}

int main()
{
  while (true) {
    scanf("%d %lf", &N, &T);
    if (!N)
      break;
    T /= 100.0;
    for (int i = 0; i <= N; i++) {
      subordinates[i].clear();
      nr_workers[i] = -1;
    }
    for (int i = 1; i <= N; i++) {
      int Bi;
      scanf("%d", &Bi);
      subordinates[Bi].push_back(i);
    }
    printf("%d\n", file_petitions(0));
#ifdef DEBUG
    for (int i = 0; i <= N; i++)
      printf("%d:%d%c", i, nr_workers[i], ((i < N) ? ' ' : '\n'));
#endif
  }
  return 0;
}

UVa 1220 - Party at Hali-Bula

Accepted date: 2016-11-23
Run Time: 0.000
Ranking (as of 2016-11-23): 106 out of 395
Language: C++

Applied dynamic programming.
The number of guests that can be invited by an employee is calculated recursively either by inviting their immediate subordinates or by inviting the subordinates of each of their immediate subordinate. For the latter case, the employee can attend the party too.

/*
  UVa 1220 - Party at Hali-Bula

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

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

const int n_max =  200;

map<string, int> employees;
vector<int> subordinates[n_max];
int nr_guests[n_max];
  // nr_guests[i] is the number of guests that can be invited by the i-th employee
bool uniques[n_max];
  // uniques[i] is whether the list of guests that can be invited by the i-th employee 
  // is unique or not

int register_employee(const string& s)
{
  pair<map<string, int>::iterator, bool> result =
    employees.insert(make_pair(s, static_cast<int>(employees.size())));
  return result.first->second;
}

pair<int, bool> invite_employees(int ei)
{
  int& nr = nr_guests[ei];
  if (nr != -1)
    return make_pair(nr, uniques[ei]);
  const vector<int>& sbs = subordinates[ei];
  if (sbs.empty())
    return make_pair(nr = 1, uniques[ei] = true);
  int nr_s = 0, nr_ss = 1;
  bool unique_s = true, unique_ss = true;
  for (size_t i = 0; i < sbs.size(); i++) {
    pair<int, bool> result = invite_employees(sbs[i]); // invite immediate subordinates
    nr_s += result.first, unique_s &= result.second;
    const vector<int>& ssbs = subordinates[sbs[i]];
    for (size_t j = 0; j < ssbs.size(); j++) {
      result = invite_employees(ssbs[j]); // invite subordinates of each immediate subordinate
      nr_ss += result.first, unique_ss &= result.second;
    }
  }
  if (nr_s > nr_ss)
    nr = nr_s, uniques[ei] = unique_s;
  else if (nr_s < nr_ss)
    nr = nr_ss, uniques[ei] = unique_ss;
  else
    nr = nr_s, uniques[ei] = false;
  return make_pair(nr, uniques[ei]);
}

int main()
{
  while (true) {
    int n;
    cin >> n;
    if (!n)
      break;
    employees.clear();
    for (int i = 0; i < n; i++) {
      nr_guests[i] = -1;
      subordinates[i].clear();
    }
    string s, b;
    cin >> b;
    register_employee(b);
    for (int i = 1; i < n; i++) {
        cin >> s >> b;
      int si = register_employee(s), bi = register_employee(b);
      subordinates[bi].push_back(si);
    }
    pair<int, bool> result = invite_employees(0);
    cout << result.first << ((result.second) ?  " Yes\n" : " No\n");
  }
  return 0;
}

UVa 11974 - Switch The Lights

Accepted date: 2016-11-22
Run Time: 0.020
Ranking (as of 2016-11-22): 21 out of 378
Language: C++

Nothing but a simple BFS problem.

/*
  UVa 11974 - Switch The Lights

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

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

const int N_max = 15, M_max = 100;
int N, M, switches[M_max];
bool visited[1 << N_max];

int bfs()
{
  int s = 1 << N;
  memset(visited, 0, s);
  queue< pair<int, int> > q;
  s--;
  visited[s] = true;
  q.push(make_pair(s, 0)); // first is the switchs (state), second is the number of steps
  while (!q.empty()) {
    pair<int, int> c = q.front();
    q.pop();
    if (!c.first)
      return c.second;
    c.second++;
    for (int i = 0; i < M; i++) {
      s = c.first ^ switches[i]; // toggle the switchs
      if (!visited[s]) {
        visited[s] = true;
        q.push(make_pair(s, c.second));
      }
    }
  }
  return -1;
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
      int s = 0;
      for (int j = 0, b = 1 << (N - 1); j < N; j++, b >>= 1) { // convert to bits
        int K;
        scanf("%d", &K);
        if (K)
          s |= b;
      }
      switches[i] = s;
    }
    int nr = bfs();
    if (nr != -1)
      printf("Case %d: %d\n", t, nr);
    else
      printf("Case %d: IMPOSSIBLE\n", t);
  }
  return 0;
}

UVa 1261 - String Popping

Accepted date: 2016-11-16
Run Time: 0.010
Ranking (as of 2016-11-16): 10 out of 371
Language: C++

/*
  UVa 1261 - String Popping

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1261_String_Popping.cpp

*/

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

const int nr_chars_max = 25;
set< pair<int, int> > visited;

bool string_popping(int n, int bs)
{
#ifdef DEBUG
  printf("%d: ", n);
  if (n) {
    for (int b = 1 << (n - 1); b; b >>=1)
      putchar((bs & b) ? 'b' : 'a');
  }
  putchar('\n');
#endif
  if (!n)
    return true;
  if (n == 1)
    return false;
  int m = n, b = 1 << (n - 1), pb = bs & b, ctr = 1;
  for (m--, b >>= 1; b; m--, b >>= 1) {
    int cb = bs & b;
    if (cb && pb || !cb && !pb) // consecutive same characters
      ctr++;
    else {
      if (ctr > 1) {
        int mask = (1 << m) - 1;
        int nbs = bs & mask | (bs >> ctr) & ~mask; // pop consecutive same characters
        pair<set< pair<int, int> >::iterator, bool> result =
          visited.insert(make_pair(n - ctr, nbs));
        if (result.second) {
          if (string_popping(n - ctr, nbs))
            return true;
        }
      }
      pb = cb, ctr = 1;
    }
  }
  if (ctr > 1) {
    int nbs = bs >> ctr;
    pair<set< pair<int, int> >::iterator, bool> result =
      visited.insert(make_pair(n - ctr, nbs));
    if (result.second) {
      if (string_popping(n - ctr, nbs))
        return true;
    }
  }
  return false;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    char s[nr_chars_max + 1];
    scanf("%s", s);
    int n = strlen(s);
    int bs = 0;
    for (int i = n - 1, b = 1; i >= 0; i--, b <<= 1)
      if (s[i] == 'b')
        bs |= b;
    visited.clear();
    visited.insert(make_pair(n, bs));
    bool result = string_popping(n, bs);
#ifdef DEBUG
    printf("visited: %u\n", visited.size());
#endif
    puts((result) ? "1" : "0");
  }
  return 0;
}

UVa 11133 - Eigensequence

Accepted date: 2016-11-15
Run Time: 0.000
Ranking (as of 2016-11-15): 26 out of 402
Language: C++

/*
  UVa 11133 - Eigensequence

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

#include <cstdio>

const int an_max = 44;
int nr_ess[an_max + 1][an_max + 1];
  // nr_ess[i][j] is the number of eigensequences that start with i and end with j

int eigensequence(int a1, int an)
{
  int& nr = nr_ess[a1][an];
  if (nr == -1) {
    nr = 0;
    for (int i = 1; i <= an - a1; i++)
      if (!(a1 % i))
        nr += eigensequence(a1 + i, an);
  }
  return nr;
}

int main()
{
  while (true) {
    int a1, an;
    scanf("%d %d", &a1, &an);
    if (a1 >= an)
      break;
    for (int i = a1; i <= an; i++)
      for (int j = a1; j <= an; j++)
        nr_ess[i][j] = (i == j) ? 1 : ((i > j) ? 0 : -1);
    printf("%d %d %d\n", a1, an, eigensequence(a1, an));
  }
  return 0;
}

UVa 632 - Compression (II)

Accepted date: 2016-11-09
Run Time: 0.020
Ranking (as of 2016-11-09): 83 out of 498
Language: C++

/*
  UVa 632 - Compression (II)

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

#include <cstdio>
#include <cstring>

const int N_max = 1997, nr_line_chars_max = 50, nr_chars = 128;
char S[N_max + 1], t[N_max + 1];
int cindices[N_max + 1], nindices[N_max + 1];

int main()
{
  int M;
  scanf("%d", &M);
  while (M--) {
    int N;
    scanf("%d", &N);
    while (getchar() != '\n')
      ;
    for (char* p = S; p - S < N; p += strlen(p))
      gets(p);
    for (int i = 0; i < N; i++)
      cindices[i] = i;
#ifdef DEBUG
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
        putchar(S[(cindices[i] + j) % N]);
      putchar('\n');
    }
#endif
    for (int i = N - 1; i >= 0; i--) { // LSD radix sort
      int counts[nr_chars] = {};
      for (int j = 0; j < N; j++)
        counts[S[(cindices[j] + i) % N] + 1]++;
      for (int j = 1; j < nr_chars; j++)
        counts[j] += counts[j - 1];
      for (int j = 0; j < N; j++)
        nindices[counts[S[(cindices[j] + i) % N]]++] = cindices[j];
      for (int j = 0; j < N; j++)
        cindices[j] = nindices[j];
    }
    int r = 0;
    for (int i = 0; i < N; i++) {
#ifdef DEBUG
      for (int j = 0; j < N; j++)
        putchar(S[(cindices[i] + j) % N]);
      putchar('\n');
#endif
      if (cindices[i] == 1)
        r = i;
      t[i] = S[(cindices[i] + N - 1) % N];
    }
    t[N] = '\0';
    printf("%d\n", r);
    for (char* p = t; ; ) {
      if (N > nr_line_chars_max) {
        char c = p[nr_line_chars_max];
        p[nr_line_chars_max] = '\0';
        puts(p);
        p[nr_line_chars_max] = c;
        p += nr_line_chars_max, N -= nr_line_chars_max;
      }
      else {
        puts(p);
        break;
      }
    }
    if (M)
      putchar('\n');
  }
  return 0;
}

UVa 10555 - Dead Fraction

Accepted date: 2016-11-06
Run Time: 0.000
Ranking (as of 2016-11-06): 58 out of 457
Language: C++

/*
  UVa 10555 - Dead Fraction

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

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

long long gcd(long long x, long long y)
{
  if (x < y)
    return gcd(y, x);
  else
      return y == 0 ? x : gcd(y, x % y);
}

int get_number(const char* s, const char* e)
{
  int n = 0;
  for ( ; s < e; s++)
    n = n * 10 + *s - '0';
  return n;
}

int main()
{
  const int nr_digits_max = 9;
  long long pow10s[nr_digits_max + 1] = {1};
  for (int i = 1; i <= nr_digits_max; i++)
    pow10s[i] = pow10s[i - 1] * 10;
  while (true) {
    char s[16];
    scanf("%s", s);
    if (!s[1])
      break;
    const char *ps = &s[2], *pe = strchr(ps, '.');
    long long min_denominator = numeric_limits<int>::max(), min_numerator;
    for (const char* p = ps; p < pe; p++) {
      int non_periodic = get_number(ps, p), periodic = get_number(p, pe);
      long long numerator = (pow10s[pe - p] - 1) * non_periodic + periodic,
        denominator = pow10s[p - ps] * (pow10s[pe - p] - 1);
      long long g = gcd(numerator, denominator);
      denominator /= g;
      if (denominator < min_denominator)
        min_denominator = denominator, min_numerator = numerator / g;
    }
    printf("%lld/%lld\n", min_numerator, min_denominator);
  }
  return 0;
}

UVa 554 - Caesar Cypher

Accepted date: 2016-11-03
Run Time: 0.000
Ranking (as of 2016-11-03): 133 out of 378
Language: C++

/*
  UVa 554 - Caesar Cypher

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

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int nr_words_max = 100, nr_word_chars_max = 20,
  nr_encrypted_chars_max = 250, nr_decrypted_chars_max = 60, K_max = 27;

char words[nr_words_max + 1][nr_word_chars_max + 1];
const char* pwords[nr_words_max + 1];

int compare_words(const void* s, const void* t)
{
  const char** p = (const char**)s;
  const char** q = (const char**)t;
  return strcmp(*p, *q);
}

int main()
{
  int nr_words = 0;
  while (true) {
    gets(words[nr_words]);
    if (words[nr_words][0] == '#')
      break;
    pwords[nr_words] = &words[nr_words][0];
    nr_words++;
  }
  qsort(pwords, nr_words, sizeof(char*), compare_words);
  char s[nr_encrypted_chars_max + 1];
  gets(s);
  char t[nr_encrypted_chars_max + 1];
  int max_nr_matches = 0, max_k;
  char *p, *q, *r;
  for (int k = 0; k < K_max; k++) {
    for (p = s, q = t; *p; p++, q++) {
      int i = (*p == ' ') ? k : (*p - 'A' + 1 + k) % K_max;
      *q = (i) ? 'A' + i - 1 : ' ';
    }
    *q = '\0';
    int nr_matches = 0;
    for (p = t, q = t; ; ) {
      while (*q && *q != ' ')
        q++;
      if (*q) {
        *q = '\0';
        if (bsearch(&p, pwords, nr_words, sizeof(char*), compare_words))
          nr_matches++;
        p = ++q;
      }
      else {
        if (bsearch(&p, pwords, nr_words, sizeof(char*), compare_words))
          nr_matches++;
        break;
      }
    }
    if (nr_matches > max_nr_matches)
      max_nr_matches = nr_matches, max_k = k;
  }
#ifdef DEBUG
  printf("%d %d\n", max_nr_matches, max_k);
#endif
  for (p = s, q = t; *p; p++, q++) {
    int i = (*p == ' ') ? max_k : (*p - 'A' + 1 + max_k) % K_max;
    *q = (i) ? 'A' + i - 1 : ' ';
  }
#ifdef DEBUG
  printf("%s\n", t);
#endif
  for (p = t, q = t, r = t; ; ) {
    while (*q && *q != ' ')
      q++;
    if (q - r > nr_decrypted_chars_max) {
      char* pp = p;
      while (pp > r && *(pp - 1) == ' ')
        pp--;
      *pp = '\0';
      puts(r);
      r = p;
    }
    if (*q)
      p = ++q;
    else {
      char* pp = p;
      while (pp > r && *(pp - 1) == ' ')
        pp--;
      *pp = '\0';
      puts(r);
      break;
    }
  }
  return 0;
}

UVa 1589 - Xiangqi

Accepted date: 2016-11-02
Run Time: 0.000
Ranking (as of 2016-11-02): 218 out of 374
Language: C++

/*
  UVa 1589 - Xiangqi

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

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

const int N_max = 7, row_min = 1, row_max = 10, column_min = 1, column_max = 9;
const int bg_row_min = 1, bg_row_max = 3, bg_column_min = 4, bg_column_max = 6;
const int nr_g_dirs = 4;
int g_dirs[nr_g_dirs][2] = {
  {0, 1}, {1, 0}, {0, -1}, {-1, 0}
};

int N;

struct piece {
  char t_; // type
  int r_, c_;
} bg, pieces[N_max];

bool captured_by_general(int pi, int r, int c)
{
  const piece& p = pieces[pi];
  if (p.c_ != c)
    return false;
  for (int i = 0; i < N; i++) {
    if (i == pi)
      continue;
    if (pieces[i].c_ == c) {
      if (pieces[i].r_ == r)
        continue;
      else if (pieces[i].r_ < p.r_)
        return false;
    }
  }
#ifdef DEBUG
    printf("captured by %d-th general: (%d, %d)\n", pi, r, c);
#endif
  return true; // flying general
}

bool captured_by_chariot(int pi, int r, int c)
{
  const piece& p = pieces[pi];
  if (p.r_ == r && p.c_ == c)
    return false; // captured by the black general
  else if (p.r_ == r) {
    for (int i = 0; i < N; i++) {
      if (i == pi)
        continue;
      if (pieces[i].r_ == r) {
        if (pieces[i].c_ == c)
          continue;
        else if (pieces[i].c_ > c && pieces[i].c_ < p.c_ || pieces[i].c_ > p.c_ && pieces[i].c_ < c)
          return false;
      }
    }
#ifdef DEBUG
    printf("captured by %d-th chariot: (%d, %d)\n", pi, r, c);
#endif
    return true;
  }
  else if (p.c_ == c) {
    for (int i = 0; i < N; i++) {
      if (i == pi)
        continue;
      if (pieces[i].c_ == c) {
        if (pieces[i].r_ == r)
          continue;
        else if (pieces[i].r_ > r && pieces[i].r_ < p.r_ || pieces[i].r_ > p.r_ && pieces[i].r_ < r)
          return false;
      }
    }
#ifdef DEBUG
    printf("captured by %d-th chariot: (%d, %d)\n", pi, r, c);
#endif
    return true;
  }
  else
    return false;
}

bool captured_by_horse(int pi, int r, int c)
{
  const int nr_h_dirs = 8;
  const int h_dirs[nr_h_dirs][2] = {
    {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}
  };

  const piece& p = pieces[pi];
  if (p.r_ == r && p.c_ == c)
    return false; // captured by the black general
  for (int i = 0; i < nr_h_dirs; i++) {
    int hr = p.r_ + h_dirs[i][0], hc = p.c_ + h_dirs[i][1];
    if (hr < row_min || hr > row_max || hc < column_min || hc > column_max)
      continue;
    if (hr == r && hc == c) {
      int hhr = p.r_ + g_dirs[i / 2][0], hhc = p.c_ + g_dirs[i / 2][1];
      for (int j = 0; j < N; j++) {
        if (j == pi)
          continue;
        if (pieces[j].r_ == hhr && pieces[j].c_ == hhc) // hobbling the horse's leg
          return false;
      }
#ifdef DEBUG
      printf("captured by %d-th horse: (%d, %d)\n", pi, r, c);
#endif
      return true;
    }
  }
  return false;
}

bool captured_by_cannon(int pi, int r, int c)
{
  const piece& p = pieces[pi];
  if (p.r_ == r && p.c_ == c)
    return false; // captured by the black general
  else if (p.r_ == r) {
    bool once = false;
    for (int i = 0; i < N; i++) {
      if (i == pi)
        continue;
      if (pieces[i].r_ == r) {
        if (pieces[i].c_ == c)
          continue;
        else if (pieces[i].c_ > c && pieces[i].c_ < p.c_ || pieces[i].c_ > p.c_ && pieces[i].c_ < c) {
          if (once)
            return false;
          else
            once = true;
        }
      }
    }
    if (once) {
#ifdef DEBUG
      printf("captured by %d-th cannon: (%d, %d)\n", pi, r, c);
#endif
      return true;
    }
    else
      return false;
  }
  else if (p.c_ == c) {
    bool once = false;
    for (int i = 0; i < N; i++) {
      if (i == pi)
        continue;
      if (pieces[i].c_ == c) {
        if (pieces[i].r_ == r)
          continue;
        else if (pieces[i].r_ > r && pieces[i].r_ < p.r_ || pieces[i].r_ > p.r_ && pieces[i].r_ < r) {
          if (once)
            return false;
          else
            once = true;
        }
      }
    }
    if (once) {
#ifdef DEBUG
      printf("captured by %d-th cannon: (%d, %d)\n", pi, r, c);
#endif
      return true;
    }
    else
      return false;
  }
  else
    return false;
}

int main()
{
  while (true) {
    scanf("%d %d %d", &N, &bg.r_, &bg.c_);
    if (!N)
      break;
    for (int i = 0; i < N; i++) {
      char t[2];
      scanf("%s %d %d", t, &pieces[i].r_, &pieces[i].c_);
      pieces[i].t_ = t[0];
    }
    int nr_moves = 0;
    for (int i = 0; i < nr_g_dirs; i++) {
      int r = bg.r_ + g_dirs[i][0], c = bg.c_ + g_dirs[i][1];
      if (r < bg_row_min || r > bg_row_max || c < bg_column_min || c > bg_column_max)
        continue;
      nr_moves++;
      bool captured = false;
#ifdef DEBUG
      for (int j = 0; j < N; j++)
        switch (pieces[j].t_) {
        case 'G':
          captured |= captured_by_general(j, r, c);
          break;
        case 'R':
          captured |= captured_by_chariot(j, r, c);
          break;
        case 'H':
          captured |= captured_by_horse(j, r, c);
          break;
        case 'C':
          captured |= captured_by_cannon(j, r, c);
          break;
        }
#else
      for (int j = 0; j < N && !captured; j++)
        switch (pieces[j].t_) {
        case 'G':
          captured = captured_by_general(j, r, c);
          break;
        case 'R':
          captured = captured_by_chariot(j, r, c);
          break;
        case 'H':
          captured = captured_by_horse(j, r, c);
          break;
        case 'C':
          captured = captured_by_cannon(j, r, c);
          break;
        }
#endif
      if (captured)
        nr_moves--;
    }
    puts((!nr_moves) ? "YES" : "NO");
  }
  return 0;
}