UVa 10146 - Dictionary

Accepted date: 2016-12-206
Run Time: 0.030
Ranking (as of 2016-12-26): 6 out of 370
Language: C++

/*
  UVa 10146 - Dictionary

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

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

const int nr_chars_max = 10;

const char* spaces[] = {
  "", " ", "  ", "   ", "    ", "     ", "      ", "       ", "        ", 
  "         ", "          "
};

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (getchar() != '\n')
    ;
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  gets(s);
  while (nr_cases--) {
    gets(s);
    puts(s);
    char *previous = s, *current = t;
    int nr_spaces = 1;
    while (gets(current) && current[0]) {
      int i;
      for (i = 0; i < nr_spaces; i++)
        if (!previous[i] || !current[i] || previous[i] != current[i])
          break;
      printf("%s%s\n", spaces[i], current);
      nr_spaces = i + 1;
      swap(previous, current);
    }
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}

UVa 12205 - Happy Telephones

Accepted date: 2016-12-25
Run Time: 0.040
Ranking (as of 2016-12-25): 22 out of 362
Language: C++

First, applied the line sweep algorithm to calculate the number of connections at each start/stop time of the telephone calls.
For a given interval, found the number of calls at the start time of the interval and then iterated over the telephone call times till the end time of the interval and added the phone calls that started during the interval.

/*
  UVa 12205 - Happy Telephones

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

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

const int N_max = 10000, M_max = 100;

struct event {
  int s_; // 0 for start, 1 for stop
  int t_; // time

  event() {}
  event(int s, int t) : s_(s), t_(t) {}
  bool operator<(const event& e) const {
    if (t_ != e.t_)
      return t_ < e.t_;
    else
      return s_ > e.s_;
  }
} events[N_max * 2];

int main()
{
  while (true) {
    int N, M;
    scanf("%d %d", &N, &M);
    if (!N)
      break;
    int n = 0;
    while (N--) {
      int s, d;
      scanf("%*d %*d %d %d", &s, &d);
      events[n].s_ = 0, events[n].t_ = s;
      n++;
      events[n].s_ = 1, events[n].t_ = s + d;
      n++;
    }
    sort(events, events + n);
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      printf("%d:%d%c", events[i].t_, events[i].s_, ((i < n - 1) ? ' ' : '\n'));
#endif
    int nr = 0;
    map<int, int> nr_calls; // key is the time, value is the number of calls from the time
    for (int i = 0; i < n; i++) {
      if (!events[i].s_)
        nr++;
      else
        nr--;
      nr_calls[events[i].t_] = nr;
    }
#ifdef DEBUG
    for (map<int, int>::const_iterator i = nr_calls.begin(); i != nr_calls.end(); ++i)
      printf("%d:%d ", i->first, i->second);
    putchar('\n');
#endif
    while (M--) {
      int s, d;
      scanf("%d %d", &s, &d);
      nr = 0;
      map<int, int>::const_iterator i = nr_calls.upper_bound(s);
      if (i != nr_calls.end()) {
#ifdef DEBUG
        printf("%d:%d\n", i->first, i->second);
#endif
        if (i != nr_calls.begin())
          nr = (--i)->second;
        int j = upper_bound(events, events + n, event(0, s)) - events;
#ifdef DEBUG
        if (j < n)
          printf("%d:%d\n", events[j].t_, events[j].s_);
#endif
        for ( ; j < n && events[j].t_ < s + d; j++)
          if (!events[j].s_)
            nr++;
      }
      printf("%d\n", nr);
    }
  }
  return 0;
}

UVa 12506 - Shortest Names

Accepted date: 2016-12-23
Run Time: 0.010
Ranking (as of 2016-12-23): 31 out of 363
Language: C++

Used trie.
During the construction of trie, counted the number of occurrences of each trie node.
Then, treversed the trie and summed up the number of occurrences of letters except for the nodes whose parent node has the occurrence counter value of 1.

/*
  UVa 12506 - Shortest Names

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

#include <cstdio>
#include <cstring>

const int nr_letters = 'z' - 'a' + 1, nr_chars_max = 1000000;
char name[nr_chars_max + 1];

struct trie_node {
  static int ctrs_[nr_letters];

  int ctr_;
  trie_node* children_[nr_letters];

  trie_node() : ctr_(0) {
    memset(children_, 0, sizeof(children_));
  }
  ~trie_node() {
    for (int i = 0; i < nr_letters; i++)
      delete children_[i];
  }
  void insert(const char* s);
  void count_prefix(int ci);
};

int trie_node::ctrs_[nr_letters];

void trie_node::insert(const char* s)
{
  trie_node* p = this;
  for (int i = 0, length = strlen(s); i < length; i++) {
    int j = s[i] - 'a';
    if (!p->children_[j])
      p->children_[j] = new trie_node();
    p = p->children_[j];
    p->ctr_++;
  }
}

void trie_node::count_prefix(int ci)
{
  ctrs_[ci] += ctr_;
  if (ctr_ > 1)
    for (int i = 0; i < nr_letters; i++)
      if (children_[i])
        children_[i]->count_prefix(i);
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    memset(trie_node::ctrs_, 0, sizeof(trie_node::ctrs_));
    trie_node* root = new trie_node();
    while (n--) {
      scanf("%s", name);
      root->insert(name);
    }
    for (int i = 0; i < nr_letters; i++)
      if (root->children_[i])
        root->children_[i]->count_prefix(i);
    int ctr = 0;
    for (int i = 0; i < nr_letters; i++)
      ctr += trie_node::ctrs_[i];
    printf("%d\n", ctr);
    delete root;
  }
  return 0;
}

UVa 12467 - Secret Word

Accepted date: 2016-12-11
Run Time: 0.020
Ranking (as of 2016-12-11): 3 out of 363
Language: C++

Applied KMP (Knuth-Morris-Pratt) algorithm where patten is an input string and text is the reverse of the input string.

/*
  UVa 12467 - Secret Word

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

#include <cstdio>
#include <cstring>

const int nr_chars_max = 1000000;
char S[nr_chars_max + 1];
int lps[nr_chars_max];
  // length of the maximum matching proper prefix which is also a suffix of S[0..i]

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", S);
    int n = strlen(S);
    // apply KMP (Knuth-Morris-Pratt) algorithm 
    // where patten is an input string and text is the reverse of the input string
    // calculate lps[]
    lps[0] = 0;
    for (int i = 1, length = 0 /* length of the previous longest prefix suffix */;
      i < n; ) {
      if (S[i] == S[length])
        lps[i++] = ++length;
          else {
          if (length)
          length = lps[length - 1];
              else
                  lps[i++] = 0;
      }
    }
    int max_length = 0, max_i;
    for (int i = n - 1, j = 0; i >= 0; ) {
      if (i >= 0 && S[j] == S[i])
        j++, i--;
      if (j > max_length)
        max_length = j, max_i = i + 1;
      if (j == n)
        j = lps[j - 1];
      else if (i >= 0 && S[j] != S[i]) {
        if (j)
          j = lps[j - 1];
        else
          i--;
      }
    }
#ifdef DEBUG
    printf("%d %d\n", max_i, max_length);
#endif
    S[max_i + max_length] = '\0';
    puts(&S[max_i]);
  }
  return 0;
}

UVa 11515 - Cranes

Accepted date: 2016-12-09
Run Time: 0.000
Ranking (as of 2016-12-09): 78 out of 364
Language: C++

Applied dynamic programming.
areas[i] is the areas with the bitmap i of cranes' usage where each bit of i corresponds to the i-th crane.

/*
  UVa 11515 - Cranes

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

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

const int C_max = 15;

struct crane {
  int x_, y_, r_;
} cranes[C_max];

bool overlapped[C_max][C_max];
  // overlapped[i][j] is true 
  // if the covering areas of i-th crane and j-th crane are overlapped
int areas[1 << C_max];
  // areas[i] is the areas with the bitmap i of cranes' usage

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int C;
    scanf("%d", &C);
    for (int i = 0; i < C; i++)
      scanf("%d %d %d", &cranes[i].x_, &cranes[i].y_, &cranes[i].r_);
    memset(overlapped, 0, sizeof(overlapped));
    for (int i = 0; i < C - 1; i++)
      for (int j = i + 1; j < C; j++) {
        int dx = cranes[i].x_ - cranes[j].x_, dy = cranes[i].y_ - cranes[j].y_,
          dr = cranes[i].r_ + cranes[j].r_;
        if (dx * dx + dy * dy <= dr * dr)
          overlapped[i][j] = overlapped[j][i] = true;
      }
    memset(areas, 0, sizeof(int) * (1 << C));
    areas[1] = cranes[0].r_ * cranes[0].r_;
#ifdef DEBUG
    printf("[1]:%d\n", areas[1]);
#endif
    for (int i = 1, ib = 1 << 1; i < C; i++, ib <<= 1) {
      int a = cranes[i].r_ * cranes[i].r_;
      for (int j = 1; j < ib; j++)
        if (areas[j]) {
          int k, kb;
          for (k = 0, kb = 1; k < i; k++, kb <<= 1)
            if (j & kb && overlapped[i][k])
              break;
          if (k == i) // not overlapped
            areas[j | ib] = areas[j] + a;
        }
      areas[ib] = a;
#ifdef DEBUG
      for (int j = 1; j < 1 << ib; j++)
        if (areas[j])
          printf("[%d]:%d ", j, areas[j]);
      putchar('\n');
#endif
    }
    int max_area = 0;
    for (int j = 1; j < 1 << C; j++)
      max_area = max(max_area, areas[j]);
    printf("%d\n", max_area);
  }
  return 0;
}

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

UVa 11582 - Colossal Fibonacci Numbers!

Accepted date: 2016-10-30
Run Time: 0.010
Ranking (as of 2016-10-30): 24 out of 440
Language: C++

/*
  UVa 11582 - Colossal Fibonacci Numbers!

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

#include <cstdio>

const int pisano_periods[] = {
  0,
  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60,
  16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60,
  40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120,
  60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120,
  216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300,
  50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120,
  110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240,
  32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240,
  48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120,
  90, 336, 120, 48, 380, 120, 180, 96, 144, 180, 190, 96, 388, 588, 280, 336, 396, 120, 22, 300,
  136, 150, 112, 72, 40, 624, 48, 168, 90, 240, 42, 108, 280, 72, 440, 72, 240, 108, 296, 60,
  252, 456, 448, 48, 600, 228, 456, 72, 114, 240, 80, 84, 52, 168, 160, 174, 312, 144, 238, 120,
  240, 330, 648, 60, 560, 120, 252, 60, 168, 1500, 250, 48, 240, 768, 360, 384, 516, 264, 304, 420,
  168, 390, 176, 120, 540, 144, 88, 408, 268, 360, 270, 72, 112, 276, 100, 48, 556, 138, 120, 240,
  56, 96, 568, 210, 360, 420, 80, 48, 612, 420, 392, 444, 588, 336, 580, 228, 360, 444, 336, 600,
  176, 150, 200, 72, 60, 72, 88, 240, 208, 60, 310, 168, 628, 948, 240, 78, 636, 216, 70, 480,
  72, 48, 36, 216, 700, 984, 216, 120, 32, 120, 110, 168, 456, 336, 680, 48, 676, 1092, 152, 180,
  30, 72, 784, 264, 240, 348, 232, 168, 174, 1200, 504, 240, 236, 696, 140, 132, 144, 534, 358, 120,
  342, 90, 440, 336, 740, 120, 736, 48, 120, 1140, 432, 120, 748, 180, 1000, 96, 28, 144, 378, 180,
  256, 570, 768, 192, 80, 1164, 264, 588, 388, 840, 144, 336, 520, 396, 780, 120, 796, 66, 144, 600,
  200, 408, 420, 150, 1080, 336, 380, 72, 408, 120, 552, 624, 464, 48, 840, 336, 184, 90, 418, 240,
  84, 42, 96, 108, 900, 840, 240, 72, 280, 1320, 430, 72, 868, 240, 280, 108, 144, 888, 438, 60,
  336, 252, 888, 456, 220, 1344, 296, 96, 448, 600, 40, 228, 200, 456, 560, 72, 916, 114, 72, 240,
  46, 240, 928, 168, 120, 156, 936, 168, 272, 480, 632, 348, 440, 312, 900, 144, 216, 714, 478, 240,
  532, 240, 48, 330, 980, 648, 976, 60, 328, 1680, 490, 120, 252, 252, 120, 120, 560, 168, 498, 1500,
  336, 750, 1008, 48, 100, 240, 728, 768, 254, 360, 592, 768, 72, 516, 1040, 264, 160, 912, 696, 420,
  26, 168, 1048, 390, 400, 528, 180, 120, 1104, 540, 696, 144, 280, 264, 360, 408, 712, 804, 560, 360,
  90, 270, 360, 144, 540, 336, 1096, 276, 120, 300, 126, 48, 624, 1668, 760, 138, 124, 120, 616, 240,
  360, 168, 376, 96, 380, 1704, 432, 420, 568, 360, 570, 420, 760, 240, 1200, 96, 1156, 612, 776, 420,
  336, 1176, 540, 444, 840, 588, 1176, 336, 90, 1740, 792, 456, 1188, 360, 720, 444, 88, 336, 598, 600,
  600, 528, 408, 150, 220, 600, 1216, 144, 112, 60, 224, 72, 1228, 264, 40, 240, 1236, 624, 206, 60,
  144, 930, 176, 168, 2500, 1884, 360, 948, 684, 240, 630, 156, 168, 636, 1280, 216, 112, 210, 840, 960,
  640, 72, 1288, 48, 440, 36, 1296, 216, 290, 2100, 240, 984, 1308, 216, 260, 120, 888, 96, 658, 120,
  220, 330, 504, 168, 720, 456, 336, 336, 448, 2040, 60, 48, 1348, 2028, 1800, 1092, 452, 456, 784, 180,
  456, 30, 1368, 72, 1380, 2352, 456, 264, 756, 240, 138, 348, 240, 696, 460, 168, 360, 174, 104, 1200,
  700, 504, 684, 480, 160, 708, 400, 696, 118, 420, 312, 132, 240, 144, 140, 534, 952, 1074, 718, 120,
  208, 342, 240, 90, 700, 1320, 1456, 336, 1944, 2220, 792, 120, 1468, 2208, 560, 48, 680, 120, 738, 1140,
  504, 432, 496, 120, 740, 2244, 168, 180, 144, 3000, 750, 96, 1000, 84, 100, 144, 1516, 378, 240, 180,
  380, 768, 432, 570, 360, 768, 812, 384, 192, 240, 1032, 1164, 1548, 264, 300, 588, 304, 1164, 360, 840,
  70, 144, 504, 336, 1580, 1560, 1576, 396, 176, 780, 304, 120, 420, 2388, 1080, 66, 228, 144, 288, 1200,
  264, 600, 740, 408, 240, 420, 536, 300, 202, 1080, 270, 336, 1080, 1140, 1640, 72, 792, 408, 336, 120,
  820, 552, 1648, 624, 200, 1392, 1656, 48, 276, 840, 1112, 672, 1008, 552, 1680, 90, 360, 1254, 838, 240,
  406, 84, 56, 42, 1820, 96, 880, 216, 568, 900, 912, 840, 1708, 240, 360, 72, 1716, 840, 78, 1320,
  80, 1290, 1728, 144, 1740, 2604, 1224, 240, 390, 840, 952, 108, 1176, 144, 2000, 888, 1756, 438, 1176, 120,
  176, 336, 1768, 252, 1160, 888, 1776, 456, 256, 660, 1080, 1344, 288, 888, 1780, 192, 336, 1344, 210, 600,
  108, 120, 176, 228, 180, 600, 1816, 456, 600, 1680, 70, 72, 840, 2748, 120, 114, 1040, 72, 102, 240,
  88, 138, 140, 240, 1900, 2784, 624, 336, 928, 120, 1008, 156, 1240, 936, 180, 168, 1876, 816, 1256, 480,
  470, 1896, 240, 696, 720, 1320, 1896, 312, 1036, 900, 1272, 144, 212, 216, 380, 714, 280, 1434, 1104, 480,
  930, 1596, 72, 240, 1940, 48, 176, 660, 72, 2940, 970, 648, 368, 2928, 1400, 120, 652, 984, 220, 1680,
  216, 1470, 1968, 120, 1980, 252, 32, 252, 528, 120, 198, 240, 440, 1680, 220, 168, 1996, 498, 1368, 1500
};

int modpow(unsigned long long base, unsigned long long exp, int modulas)
{
  int b = static_cast<int>(base % modulas);
  int result = 1;
  while (exp) {
    if (exp & 1)
      result = (result * b) % modulas;
    b = (b * b) % modulas;
    exp >>= 1;
  }
  return result;
}

int fibonacci(int n, int modulo)
{
  int fib[2][2] = {{1, 1}, {1, 0}}, result[2][2]= {{1, 0}, {0, 1}};
  while (n) {
    if(n & 1) {
      int r[2][2] = {};
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          for (int k = 0; k < 2; k++)
            r[i][j] = (r[i][j] + result[i][k] * fib[k][j] % modulo) % modulo;
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          result[i][j] = r[i][j];
        }
    int r[2][2] = {};
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
          r[i][j] = (r[i][j] + fib[i][k] * fib[k][j] % modulo) % modulo;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        fib[i][j] = r[i][j];
    n /= 2;
  }
#ifdef DEBUG
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        printf("[%d][%d]:%lld%c", i, j, result[i][j], ((j < 1) ?  ' ' : '\n'));
#endif
  return result[0][1];
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    unsigned long long a, b;
    int n;
    scanf("%llu %llu %d", &a, &b, &n);
    printf("%lld\n", fibonacci(modpow(a, b, pisano_periods[n]), n));
  }
  return 0;
}

UVa 10690 - Expression Again

Accepted date: 2016-10-28
Run Time: 0.160
Ranking (as of 2016-10-28): 35 out of 395
Language: C++

/*
  UVa 10690 - Expression Again

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

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

const int N_max = 50, M_max = 50, integer_min = -50, integer_max = 50;
const int first_term_min = (N_max + M_max) * integer_min,
  first_term_max = (N_max + M_max) * integer_max;
int integers[N_max + M_max + 1];

bool expressions[2][N_max + 1][first_term_max - first_term_min + 1];
  // expressions[i][j][k] is true for the product of up to (i % 2)-th integers 
  // with j integers for the first term and sum of j integers (the first term) being k

#ifdef DEBUG
void print_expressions(int i,int j, int k_min, int k_max, const bool exps[])
{
  printf("[%d][%d]:", i, j);
  for (int k = k_min; k <= k_max; k++)
    if (exps[k])
      printf(" %d", k + first_term_min);
  putchar('\n');
}
#endif

int main()
{
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    int s = 0;
    for (int i = 1; i <= N + M; i++) {
      scanf("%d", &integers[i]);
      s += integers[i];
    }
    memset(&expressions[1], 0, sizeof(expressions[0]));
    int pj_min = 0, pj_max = 1, integer = integers[1];
    int pk_min = 0 - first_term_min, pk_max = integer - first_term_min;
    expressions[1][pj_min][pk_min] = expressions[1][pj_max][pk_max] = true;
#ifdef DEBUG
    print_expressions(1, pj_min, pk_min, pk_min, expressions[1][pj_min]);
    print_expressions(1, pj_max, pk_max, pk_max, expressions[1][pj_max]);
#endif
    if (pk_min > pk_max)
      swap(pk_min, pk_max);
    for (int i = 2; i <= N + M; i++) {
      int pi = (i - 1) %2, ci = i % 2;
      int cj_min = max(0, i - M), cj_max = min(i, N);
      int ck_min = pk_min, ck_max = pk_max;
      memset(&expressions[ci], 0, sizeof(expressions[0]));
      integer = integers[i];
      for (int j = pj_min; j <= pj_max; j++) {
        for (int k = pk_min; k <= pk_max; k++)
          if (expressions[pi][j][k]) {
            expressions[ci][j][k] = true;
            if (j < cj_max) {
              expressions[ci][j + 1][k + integer] = true;
              ck_min = min(ck_min, k + integer), ck_max = max(ck_max, k + integer);
            }
          }
      }
      pj_min = cj_min, pj_max = cj_max;
      pk_min = ck_min, pk_max = ck_max;
#ifdef DEBUG
      for (int j = pj_min; j <= pj_max; j++)
        print_expressions(i, j, pk_min, pk_max, expressions[ci][j]);
#endif
    }
    int ci = (N + M) % 2, p_min = (N_max + M_max) * integer_max + 1,
      p_max = (N_max + M_max) * integer_min - 1;
    for (int k = pk_min; k <= pk_max; k++)
      if (expressions[ci][pj_min][k]) {
        int p = k + first_term_min;
        p *= s - p;
        p_min = min(p_min, p), p_max = max(p_max, p);
      }
    printf("%d %d\n", p_max, p_min);
  }
  return 0;
}

UVa 11832 - Account Book

Accepted date: 2016-10-24
Run Time: 0.040
Ranking (as of 2016-10-24): 16 out of 384
Language: C++

/*
  UVa 11832 - Account Book

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

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

const int N_max = 40, F_min = -16000, F_max = 16000;

int Ti[N_max + 1];
bool cash_flow[N_max + 1][F_max - F_min + 1][2];
  // cash_flow[i][j][0/1] is the cash_flow of j, up to i-th transaction, 
  // with i-th transaction of income (1) or expense (0)
char transactions[N_max + 2];

void transaction(int n, int f)
{
  int t = Ti[n];
  if (cash_flow[n][f - F_min][0]) {
    cash_flow[n][f - F_min][0] = false;
    if (transactions[n] != '?')
      transactions[n] = (transactions[n] == '+') ? '?' : '-';
#ifdef DEBUG
    printf("[%d][%d][0]: %c\n", n, f, transactions[n]);
#endif
    if (n > 1)
      transaction(n - 1, f + t);
  }
  if (cash_flow[n][f - F_min][1]) {
    cash_flow[n][f - F_min][1] = false;
    if (transactions[n] != '?')
      transactions[n] = (transactions[n] == '-') ? '?' : '+';
#ifdef DEBUG
    printf("[%d][%d][1]: %c\n", n, f, transactions[n]);
#endif
    if (n > 1)
      transaction(n - 1, f - t);
  }
}

int main()
{
  while (true) {
    int N, F;
    scanf("%d %d", &N, &F);
    if (!N)
      break;
    for (int i = 1; i <= N; i++)
      scanf("%d", &Ti[i]);
    memset(cash_flow, 0, sizeof(cash_flow));
    int j_min = -Ti[1] - F_min, j_max = Ti[1] - F_min;
    cash_flow[1][j_min][0] = cash_flow[1][j_max][1] = true;
#ifdef DEBUG
    printf("[1][%d][0] [1][%d][1]\n", j_min + F_min, j_max + F_min);
#endif
    for (int i = 2; i <= N; i++) {
      int t = Ti[i];
      for (int j = j_min; j <= j_max; j++)
        if (cash_flow[i - 1][j][0] || cash_flow[i - 1][j][1]) {
          if (j - t >= 0)
            cash_flow[i][j - t][0] = true;
          if (j + t <= F_max - F_min)
          cash_flow[i][j + t][1] = true;
        }
      j_min = max(j_min - t, 0), j_max = min(j_max + t, F_max - F_min);
#ifdef DEBUG
      for (int j = j_min; j <= j_max; j++)
        for (int k = 0; k < 2; k++)
          if (cash_flow[i][j][k])
            printf("[%d][%d][%d] ", i, j + F_min, k);
      putchar('\n');
#endif
    }
    if (cash_flow[N][F - F_min][0] || cash_flow[N][F - F_min][1]) {
      memset(transactions, 0, sizeof(transactions));
      transaction(N, F);
      puts(transactions + 1);
    }
    else
      puts("*");
  }
  return 0;
}

UVa 10094 - Place the Guards

Accepted date: 2016-10-17
Run Time: 0.000
Ranking (as of 2016-10-17): 9 out of 422
Language: C++

For more information, see Wikipedia's article Eight queens puzzle.

/*
  UVa 10094 - Place the Guards

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

#include <cstdio>
#ifdef DEBUG
#include <cassert>
#include <cstdlib>
#endif

const int n_max = 1000;
int rows[n_max + 1]; // rows[i] is the row number for i-th column

#ifdef DEBUG
bool validate_rows(int n)
{
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j) {
        if (rows[i] == rows[j] || abs(i - j) == abs(rows[i] - rows[j]))
          return false;
      }
  return true;
}
#endif

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    if (n < 4)
      puts("Impossible");
    else {
      int m = n;
      if (m & 1) { // odd
        rows[m] = m;
        m--;
      }
      int i, j, k;
      if ((m - 2) % 6)
        for (i = 1, j = m / 2; i <= j; i++) {
          k = 2 * i;
          rows[i] = k, rows[j + i] = k - 1;
        }
      else
        for (i = 1, j = m / 2; i <= j; i++) {
          k = (2 * i + j - 3) % m;
          rows[i] = 1 + k, rows[m + 1 - i] = m - k;
        }
#ifdef DEBUG
      assert(validate_rows(n));
#endif
      for (int i = 1; i <= n; i++)
        printf("%d%c", rows[i], ((i < n) ? ' ' : '\n'));
    }
  }
  return 0;
}

UVa 12101 - Prime Path

Accepted date: 2016-10-14
Run Time: 0.000
Ranking (as of 2016-10-14): 28 out of 378
Language: C++

/*
  UVa 12101 - Prime Path

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

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

const int n_min = 1000, n_max = 9999, nr_digits = '9' - '0' + 1;

bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
bool visited[n_max + 1];

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

struct path {
  int p_; // prime
  int s_; // steps

  path(int p, int s) : p_(p), s_(s) {}
};

void push_prime(queue<path>& q, int s, int d0, int d1, int d2, int d3)
{
  int p = d0 * 1000 + d1 * 100 + d2 * 10 + d3;
  if (!not_primes[p] && !visited[p]) {
    visited[p] = true;
    q.push(path(p, s));
  }
}

int bfs(int start, int end)
{
  queue<path> q;
  memset(visited, 0, sizeof(visited));
  visited[start] = true;
  q.push(path(start, 0));
  while (!q.empty()) {
    path p = q.front();
    q.pop();
    if (p.p_ == end)
      return p.s_;
    int d0 = p.p_ / 1000, d1 = p.p_ % 1000 / 100,
      d2 = p.p_ % 100 / 10, d3 = p.p_ % 10, s = p.s_ + 1;
    for (int d = 1; d < nr_digits; d++)
      push_prime(q, s, d, d1, d2, d3);
    for (int d = 0; d < nr_digits; d++)
      push_prime(q, s, d0, d, d2, d3);
    for (int d = 0; d < nr_digits; d++)
      push_prime(q, s, d0, d1, d, d3);
    for (int d = 1; d < nr_digits; d += 2)
      push_prime(q, s, d0, d1, d2, d);
  }
  return -1;
}

int main()
{
  sieve_of_eratosthenes();
  int t;
  scanf("%d", &t);
  while (t--) {
    int start, end;
    scanf("%d %d", &start, &end);
    int steps = bfs(start, end);
    if (steps != -1)
      printf("%d\n", steps);
    else
      puts("Impossible");
  }
  return 0;
}

UVa 718 - Skyscraper Floors

Accepted date: 2016-10-13
Run Time: 0.010
Ranking (as of 2016-10-13): 72 out of 415
Language: C++

/*
  UVa 718 - Skyscraper Floors

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

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

// extended Euclidean Algorithm
long long gcd_ex(long long a, long long b, long long& x, long long& y)
{
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  long long x1, y1;
  long long d = gcd_ex(b, a % b, x1, y1);
  x = y1, y = x1 - (a / b) * y1;
  return d;
}

bool linear_diophantine_equation(int a, int b, int c,
  long long& d, long long& x0, long long& y0)
{
  long long u, v;
  d = gcd_ex(a, b, u, v);
  if (c % d)
    return false;
  x0 = u * (c / d), y0 = v * (c / d);
  return true;
}

bool reachable(int Xi, int Xj, int Yi, int Yj, int F)
{
  long long d, x0, y0;
  if (!linear_diophantine_equation(Xi, -Xj, Yj - Yi, d, x0, y0))
    return false;
  int xi = static_cast<int>(Xi / d), xj = static_cast<int>(-Xj / d);
  double d_min = static_cast<double>(-x0) / xj,
    d_max = (static_cast<double>(F - 1 - Yi) / Xi - x0) / xj;
  if (xj < 0)
    swap(d_min, d_max);
  int ti_min = static_cast<int>(ceil(d_min)), ti_max = static_cast<int>(floor(d_max));
  d_min = (y0 - static_cast<double>(F - 1 - Yj) / Xj) / xi,
    d_max = static_cast<double>(y0) / xi;
  if (xi < 0)
    swap(d_min, d_max);
  int tj_min = static_cast<int>(ceil(d_min)), tj_max = static_cast<int>(floor(d_max));
  return (ti_min > tj_max || ti_max < tj_min) ? false : true;
}

const int E_max = 100;

int Xs[E_max], Ys[E_max];
bool A_reachables[E_max], B_reachables[E_max], reachables[E_max][E_max];

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int F, E, A, B;
    scanf("%d %d %d %d", &F, &E, &A, &B);
    for (int i = 0; i < E; i++)
      scanf("%d %d", &Xs[i], &Ys[i]);
    for (int i = 0; i < E; i++) {
      A_reachables[i] = A >= Ys[i] && !((A - Ys[i]) % Xs[i]);
      B_reachables[i] = B >= Ys[i] && !((B - Ys[i]) % Xs[i]);
    }
    for (int i = 0; i < E - 1; i++)
      for (int j = i + 1; j < E; j++)
        reachables[i][j] = reachables[j][i] = reachable(Xs[i], Xs[j], Ys[i], Ys[j], F);
#ifdef DEBUG
    for (int i = 0; i < E - 1; i++)
      for (int j = i + 1; j < E; j++)
        if (reachables[i][j])
          printf("[%d][%d] ", i, j);
    putchar('\n');
#endif
    for (int k = 0; k < E; k++)
      for (int i = 0; i < E; i++)
        for (int j = 0; j < E; j++)
          reachables[i][j] |= reachables[i][k] && reachables[k][j];
    bool possible = false;
    for (int i = 0; i < E && !possible; i++)
      if (A_reachables[i])
        for (int j = 0; j < E && !possible; j++)
          if (B_reachables[j] && reachables[i][j])
            possible = true;
    puts((possible) ? "It is possible to move the furniture." :
      "The furniture cannot be moved.");
  }
  return 0;
}

UVa 11552 - Fewest Flops

Accepted date: 2016-10-06
Run Time: 0.000
Ranking (as of 2016-10-06): 27 out of 466
Language: C++

/*
  UVa 11552 - Fewest Flops

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

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

const int nr_letters = 26, nr_chars_max = 1000, infinite = nr_chars_max + 1;
int nr_chunks[nr_chars_max]; // number of chunks in Si
int freqs[nr_chars_max][nr_letters];
  // freqs[i][j] is the number of occurrences of ('a' + j) charactor in Si
int min_nr_chunks[nr_chars_max][nr_letters];
  // min_nr_chunks[i][j] min. number of chunks up to Si with the last character of of j

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int k;
    char S[nr_chars_max + 1];
    scanf("%d %s", &k, S);
    int length = strlen(S), n = length / k;
    for (int i = 0, si = 0; i < n; i++, si += k) {
      nr_chunks[i] = 0;
      memset(&freqs[i], 0, sizeof(freqs[0]));
      for (int j = 0; j < k; j++)
        if (!freqs[i][S[si + j] - 'a']++)
          nr_chunks[i]++;
    }
    for (int j = 0; j < nr_letters; j++)
      min_nr_chunks[0][j] = (freqs[0][j]) ? nr_chunks[0] : infinite;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < nr_letters; j++)
        min_nr_chunks[i][j] = infinite;

#ifdef DEBUG
    for (int j = 0; j < nr_letters; j++)
      if (min_nr_chunks[0][j] < infinite)
        printf("[0][%c]: %d ", 'a' + j, min_nr_chunks[0][j]);
    putchar('\n');
#endif
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < nr_letters; j++) {
        if (freqs[i][j])
          for (int k = 0; k < nr_letters; k++)
            if (freqs[i + 1][k]) {
              int nr = 0;
              if (j != k)
                nr = (freqs[i + 1][j]) ? nr_chunks[i + 1] - 1 : nr_chunks[i + 1];
              else if (nr_chunks[i + 1] != 1) // j == k
                nr = nr_chunks[i + 1];
              min_nr_chunks[i + 1][k] = min(min_nr_chunks[i + 1][k], min_nr_chunks[i][j] + nr);
            }
      }
#ifdef DEBUG
      for (int j = 0; j < nr_letters; j++)
        if (min_nr_chunks[i + 1][j] < infinite)
          printf("[%d][%c]: %d ", i + 1, 'a' + j, min_nr_chunks[i + 1][j]);
      putchar('\n');
#endif
    }
    int min_nr = infinite;
    for (int j = 0; j < nr_letters; j++)
      min_nr = min(min_nr, min_nr_chunks[n - 1][j]);
    printf("%d\n", min_nr);
  }
  return 0;
}

UVa 10964 - Strange Planet

Accepted date: 2016-10-05
Run Time: 0.000
Ranking (as of 2016-10-05): 8 out of 378
Language: C++11

/*
  UVa 10964 - Strange Planet

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

#include <cstdio>
#include <cmath>

void get_coordinate(int c, int& x, int& y)
{
  int d = static_cast<int>((1.0 + sqrt(1.0 + static_cast<double>(c) * 2.0)) / 2.0);
    // c is in the d-th diamond shape from the origin
  if (2 * d * (d - 1) == c)
    d--;
  x = 1 - d, y = 1;
  int c_min = 2 * d * (d - 1) + 1, c_max = c_min + d - 1;
  if (c <= c_max)
    x += c - c_min, y += c - c_min;
  else {
    x += c_max - c_min, y += c_max - c_min;
    c_min = c_max, c_max += d;
    if (c <= c_max)
      x += c - c_min, y -= c - c_min;
    else {
      x += c_max - c_min, y -= c_max - c_min;
      c_min = c_max, c_max += d;
      if (c <= c_max)
        x -= c - c_min, y -= c - c_min;
      else {
        x -= c_max - c_min, y -= c_max - c_min;
        c_min = c_max, c_max += d;
        x -= c - c_min, y += c - c_min;
      }
    }
  }
#ifdef DEBUG
  printf("%d: (%d, %d)\n", c, x, y);
#endif
}

int main()
{
  while (true) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a == -1)
      break;
    int ax, ay, bx, by;
    get_coordinate(a, ax, ay);
    get_coordinate(b, bx, by);
    printf("%.2lf\n", hypot(static_cast<double>(ax - bx), static_cast<double>(ay - by)));
  }
  return 0;
}

UVa 493 - Rational Spiral

Accepted date: 2016-10-04
Run Time: 0.000
Ranking (as of 2016-10-04): 12 out of 479
Language: C++

/*
  UVa 493 - Rational Spiral

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

#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 650, nr_rationals_max = 514407;
int coprimes[n_max];

struct rational {
  int numerator_, denominator_;
} rationals[nr_rationals_max] = {
  {1, 1}, {0, 1}, {-1, 1}
};
int nr_rationals = 3;

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

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 2; i <= n_max; i++) {
    int nr_coprimes = 0;
    for (int j = 1; j < i; j++)
      if (gcd(i, j) == 1)
        coprimes[nr_coprimes++] = j;
    for (int j = nr_coprimes - 1; j >= 0; j--, nr_rationals++)
      rationals[nr_rationals].numerator_ = -i,
        rationals[nr_rationals].denominator_ = coprimes[j];
    for (int j = 0; j < nr_coprimes; j++, nr_rationals++)
      rationals[nr_rationals].numerator_ = i,
        rationals[nr_rationals].denominator_ = coprimes[j];
    for (int j = nr_coprimes - 1; j >= 0; j--, nr_rationals++)
      rationals[nr_rationals].numerator_ = coprimes[j],
        rationals[nr_rationals].denominator_ = i;
    for (int j = 0; j < nr_coprimes; j++, nr_rationals++)
      rationals[nr_rationals].numerator_ = -coprimes[j],
        rationals[nr_rationals].denominator_ = i;
  }
#ifdef DEBUG
  printf("%d\n", nr_rationals);
#endif
  int i;
  while (scanf("%d", &i) != EOF)
    printf("%d / %d\n", rationals[i].numerator_, rationals[i].denominator_);
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 702 - The Vindictive Coach

Accepted date: 2016-09-30
Run Time: 0.000
Ranking (as of 2016-09-30): 129 out of 530
Language: C++

/*
  UVa 702 - The Vindictive Coach

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

#include <cstdio>

const int N_max = 22;
long long nr_alignments[N_max][N_max][N_max];
  // nr_alignments[i][j][k] is the number of alignments at the i-th player 
  // with j players less than i-th player' number and 
  // k players greater than -i-th player's number

int main()
{
  int N, m;
  while (scanf("%d %d", &N, &m) != EOF) {
    if (N == 1) {
      puts("1");
      continue;
    }
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
          nr_alignments[i][j][k] = 0;
    int n = 0, less;
    if (m == 1) {
      n++;
      if (N > 2)
        nr_alignments[n][1][N - 3] = 1;
      else
        nr_alignments[n][0][0] = 1;
    }
    else
      nr_alignments[n][m - 1][N - m] = 1;
    for (n++, less = 1; n < N; n++, less = 1 - less) {
      for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
          long long nr = nr_alignments[n - 1][i][j];
          if (nr) {
            if (less && i) {
              for (int ii = i - 1, jj = j; ii >= 0; ii--, jj++)
                nr_alignments[n][ii][jj] += nr;
            }
            else if (!less && j) {
              for (int ii = i, jj = j - 1; jj >= 0; ii++, jj--)
                nr_alignments[n][ii][jj] += nr;
            }
          }
        }
#ifdef DEBUG
      printf("%d\n  ", n);
      for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
          long long nr = nr_alignments[n][i][j];
          if (nr)
            printf("[%d][%d]:%lld ", i, j, nr);
        }
      putchar('\n');
#endif
    }
    long long nr = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        nr += nr_alignments[N - 1][i][j];
    printf("%lld\n", nr);
  }
  return 0;
}

UVa 12124 - Assemble

Accepted date: 2016-09-27
Run Time: 0.080
Ranking (as of 2016-09-27): 321 out of 391
Language: C++

Sort of dynamic programming, although very slow.

/*
  UVa 12124 - Assemble

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

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

const int n_max = 1000, nr_chars_max = 20;

#ifdef DEBUG
void print_qualities(const map<int, int>& qualities)
{
  printf("%d\n  ", qualities.size());
  for (map<int, int>::const_iterator i = qualities.begin(); i != qualities.end(); ++i)
    printf("%d:%d ", i->first, i->second);
  putchar('\n');
}
#endif

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, b;
    scanf("%d %d", &n, &b);
    int nr_types = 0;
    map<string, int> types;
    vector< map<int, int> > components;
    while (n--) {
      char type[nr_chars_max + 1];
      int price, quality;
      scanf("%s %*s %d %d", type, &price, &quality);
      pair<map<string, int>::iterator, bool> sr =
        types.insert(make_pair(string(type), nr_types));
      if (sr.second) {
        nr_types++;
        components.push_back(map<int, int>());
      }
      pair<map<int, int>::iterator, bool> cr =
        components[sr.first->second].insert(make_pair(quality, price));
      if (!cr.second && cr.first->second > price)
        cr.first->second = price;
    };
    vector< map<int, int> > qualities(nr_types);
    for (map<int, int>::const_iterator k = components[0].begin();
      k != components[0].end(); ++k) {
      int q = k->first, p = k->second;
      if (p <= b)
        qualities[0].insert(make_pair(q, p));
    }
#ifdef DEBUG
    print_qualities(qualities[0]);
#endif
    for (int i = 1; i < nr_types; i++) {
      for (map<int, int>::const_iterator j = qualities[i - 1].begin();
        j != qualities[i - 1].end(); ++j) {
        int quality = j->first, price = j->second;
        for (map<int, int>::const_iterator k = components[i].begin();
          k != components[i].end(); ++k) {
          int q = min(quality, k->first), p = price + k->second;
          if (p <= b) {
            pair<map<int, int>::iterator, bool> qr =
              qualities[i].insert(make_pair(q, p));
            if (!qr.second && qr.first->second > p)
              qr.first->second = p;
          }
        }
      }
#ifdef DEBUG
      print_qualities(qualities[i]);
#endif
    }
    printf("%d\n", qualities[nr_types - 1].rbegin()->first);
  }
  return 0;
}

UVa 12470 - Tribonacci

Accepted date: 2016-09-24
Run Time: 0.000
Ranking (as of 2016-09-24): 75 out of 400
Language: C++

/*
  UVa 12470 - Tribonacci

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

#include <cstdio>

/*
t(k + 3)    1 1 1  t(k + 2)
t(k + 2) =  1 0 0  t(k + 1)
t(k + 1)    0 1 0  t(k)
*/

long long tribonacci(long long n)
{
  const long long modulo = 1000000009;
  long long trib[3][3] = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}},
    result[3][3]= {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  while (n) {
    if(n & 1) {
      long long r[3][3] = {};
      for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
          for (int k = 0; k < 3; k++)
            r[i][j] = (r[i][j] + result[i][k] * trib[k][j] % modulo) % modulo;
      for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
          result[i][j] = r[i][j];
        }
    long long r[3][3]= {};
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < 3; j++)
        for (int k = 0; k < 3; k++)
          r[i][j] = (r[i][j] + trib[i][k] * trib[k][j] % modulo) % modulo;
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < 3; j++)
        trib[i][j] = r[i][j];
    n /= 2;
  }
  return result[0][1];
}

int main()
{
  while (true) {
    long long n;
    scanf("%lld", &n);
    if (!n)
      break;
    printf("%lld\n", tribonacci(n - 1));
  }
  return 0;
}

UVa 12894 - Perfect Flag

Accepted date: 2016-09-23
Run Time: 0.000
Ranking (as of 2016-09-23): 172 out of 382
Language: C++

/*
  UVa 12894 - Perfect Flag

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

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int x0, y0, x1, y1, cx, cy, r;
    scanf("%d %d %d %d %d %d %d", &x0, &y0, &x1, &y1, &cx, &cy, &r);
    int l = x1 - x0, w = y1 - y0;
    bool valid = l && w && l * 6 == w * 10 && l == r * 5 &&
      l * 9 == (cx - x0) * 20 && w == (cy - y0) * 2;
    puts((valid) ? "YES" : "NO");
  }
  return 0;
}

UVa 12657 - Boxes in a Line

Accepted date: 2016-09-22
Run Time: 0.090
Ranking (as of 2016-09-22): 72 out of 388
Language: C++

/*
  UVa 12657 - Boxes in a Line

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

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

const int n_max = 100000;

struct list {
  int value_;
  list *left_, *right_;
} lists[n_max + 1];

void remove(list* l)
{
  l->right_->left_ = l->left_, l->left_->right_ = l->right_;
}

void insert_left(list* ll, list* l)
{
  l->left_->right_ = ll, ll->left_ = l->left_;
  ll->right_ = l, l->left_ = ll;
}

void insert_right(list* rl, list* l)
{
  l->right_->left_ = rl, rl->right_ = l->right_;
  rl->left_ = l, l->right_ = rl;
}

void swap_(list* ll, list* rl)
{
  if (ll->left_ != rl && ll->right_ != rl) {
    ll->left_->right_ = rl, ll->right_->left_= rl;
    rl->left_->right_ = ll, rl->right_->left_ = ll;
    swap(ll->left_, rl->left_);
    swap(ll->right_, rl->right_);
  }
  else if (ll->right_ == rl) {
    ll->left_->right_ = rl, rl->right_->left_ = ll;
    ll->right_ = rl->right_, rl->left_ = ll->left_;
    ll->left_ = rl, rl->right_ = ll;
  }
  else {
    ll->right_->left_ = rl, rl->left_->right_ = ll;
    ll->left_ = rl->left_, rl->right_ = ll->right_;
    ll->right_ = rl, rl->left_ = ll;
  }
}

#ifdef DEBUG
void print_list(bool reverse)
{
  if (reverse)
    for (list* l = lists[0].left_; l != &lists[0]; l = l->left_)
      printf("%d ", l->value_);
  else
    for (list* l = lists[0].right_; l != &lists[0]; l = l->right_)
      printf("%d ", l->value_);
  putchar('\n');
}
#endif

int main()
{
  for (int cn = 1; ; cn++) {
    int n, m;
    if (scanf("%d %d", &n, &m) == EOF)
      break;
    lists[0].left_ = &lists[n], lists[0].right_ = &lists[1];
    for (int i = 1; i < n; i++)
      lists[i].value_ = i,
        lists[i].left_ = &lists[i - 1], lists[i].right_ = &lists[i + 1];
    lists[n].value_ = n,
      lists[n].left_ = &lists[n - 1], lists[n].right_ = &lists[0];
    bool reverse = false;
    while (m--) {
      int c, X, Y;
      scanf("%d", &c);
      if (c != 4)
        scanf("%d %d", &X, &Y);
      switch (c) {
      case 1:
        if (reverse) {
          if (lists[X].left_ != &lists[Y]) {
            remove(&lists[X]);
            insert_right(&lists[X], &lists[Y]);
          }
        }
        else {
          if (lists[X].right_ != &lists[Y]) {
            remove(&lists[X]);
            insert_left(&lists[X], &lists[Y]);
          }
        }
        break;
      case 2:
        if (reverse) {
          if (lists[X].right_ != &lists[Y]) {
            remove(&lists[X]);
            insert_left(&lists[X], &lists[Y]);
          }
        }
        else {
          if (lists[X].left_ != &lists[Y]) {
            remove(&lists[X]);
            insert_right(&lists[X], &lists[Y]);
          }
        }
        break;
      case 3:
        swap_(&lists[X], &lists[Y]);
        break;
      case 4:
        reverse = !reverse;
        break;
      }
#ifdef DEBUG
      print_list(reverse);
#endif
    }
    bool odd = true;
    unsigned int s = 0;
    if (reverse) {
      for (list* l = lists[0].left_; l != &lists[0]; l = l->left_) {
        if (odd)
          odd = false, s += l->value_;
        else
          odd = true;
      }
    }
    else {
      for (list* l = lists[0].right_; l != &lists[0]; l = l->right_) {
        if (odd)
          odd = false, s += l->value_;
        else
          odd = true;
      }
    }
    printf("Case %d: %u\n", cn, s);
  }
  return 0;
}

UVa 12563 - Jin Ge Jin Qu hao

Accepted date: 2016-09-21
Run Time: 0.000
Ranking (as of 2016-09-21): 64 out of 386
Language: C++

/*
  UVa 12563 - Jin Ge Jin Qu hao

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

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

const int n_max = 50, t_max = 180 * n_max, jin_ge_jin_qu = 678;
int ts[n_max + 1][t_max + 1];

int main()
{
  int T;
  scanf("%d", &T);
  for (int c = 1; c <= T; c++) {
    int n, t;
    scanf("%d %d", &n, &t);
    int s = 0;
    for (int i = 1; i <= n; i++) {
      int st;
      scanf("%d", &st);
      for (int j = 1; j <= s + st; j++)
        ts[i][j] = 0;
      ts[i][st] = 1;
      for (int j = 1; j <= s; j++) {
        if (ts[i - 1][j]) {
          ts[i][j] = max(ts[i][j], ts[i - 1][j]);
          if (j + st < t)
            ts[i][j + st] = max(ts[i][j + st], ts[i - 1][j] + 1);
        }
      }
      s += st;
    }
#ifdef DEBUG
    for (int i = 1; i <= s; i++)
      if (ts[n][i])
        printf("%d:%d ", i, ts[n][i]);
    putchar('\n');
#endif
    int max_songs = 0, max_length = 0;
    for (int i = 1; i <= min(s, t); i++)
      if (ts[n][i]) {
        if (max_songs < ts[n][i])
          max_songs = ts[n][i], max_length = i;
        else if (max_songs == ts[n][i] && max_length < i)
          max_length = i;
      }
    printf("Case %d: %d %d\n", c, max_songs + 1, max_length + jin_ge_jin_qu);
  }
  return 0;
}

UVa 533 - Equation Solver

Accepted date: 2016-09-19
Run Time: 0.000
Ranking (as of 2016-09-19): 11 out of 389
Language: C++

/*
  UVa 533 - Equation Solver

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

#include <cstdio>
#include <cctype>
#ifndef ONLINE_JUDGE
#include <cassert>
#endif

struct linear_expression {
  int v_, c_;

  linear_expression() : v_(0), c_(0) {}
};

const int nr_chars_max = 100;
const char *ps;

int get_number()
{
  if (isdigit(*ps)) {
    int n = *ps++ - '0';
    while (isdigit(*ps)) {
      n = n * 10 + *ps++ - '0';
    }
    return n;
  }
  else
    return -1;
}

void expression(linear_expression& le);
void term(linear_expression& le);
void factor(linear_expression& le);

void expression(linear_expression& le)
{
  term(le);
  while (*ps == '+' || *ps == '-') {
    char c = *ps++;
    linear_expression le_;
    term(le_);
    if (c == '+')
      le.v_ += le_.v_, le.c_ += le_.c_;
    else
      le.v_ -= le_.v_, le.c_ -= le_.c_;
  }
}

void term(linear_expression& le)
{
  factor(le);
  while (*ps == '*') {
    ps++;
    linear_expression le_;
    factor(le_);
    le.v_ = le.c_ * le_.v_ + le.v_ * le_.c_;
    le.c_ *= le_.c_;
  }
}

void factor(linear_expression& le)
{
  int n = get_number();
  if (n != -1)
    le.c_ = n;
  else if (*ps == 'x')
    ps++, le.v_ = 1;
  else {
#ifndef ONLINE_JUDGE
    assert(*ps == '(');
#endif
    ps++;
    expression(le);
#ifndef ONLINE_JUDGE
    assert(*ps == ')');
#endif
    ps++;
  }
}

int main()
{
  char s[nr_chars_max + 1];
  for (int eq = 1; gets(s); eq++) {
    if (eq > 1)
      putchar('\n');
    ps = s;
    linear_expression lle, rle;
    expression(lle);
#ifdef DEBUG
    printf("%d*x + %d\n",  lle.v_, lle.c_);
#endif
#ifndef ONLINE_JUDGE
    assert(*ps == '=');
#endif
    ps++;
    expression(rle);
#ifdef DEBUG
    printf("%d*x + %d\n",  rle.v_, rle.c_);
#endif
    printf("Equation #%d\n", eq);
    int v = lle.v_, c = lle.c_;
    v -= rle.v_, c -= rle.c_;
    if (v)
      printf("x = %.6lf\n", static_cast<double>(-c) / v);
    else if (c)
      puts("No solution.");
    else
      puts("Infinitely many solutions.");
  
  }
  return 0;
}

UVa 10058 - Jimmi's Riddles

Accepted date: 2016-09-17
Run Time: 0.000
Ranking (as of 2016-09-17): 154 out of 541
Language: C++

Yet another simple implementation of recursive descent parser.

/*
  UVa 10058 - Jimmi's Riddles

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

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cctype>
using namespace std;

const char *ps, *pws, *pwe;

bool get_word(const char** s, const char** e)
{
  while (isspace(*ps))
    ps++;
  *s = ps;
  while (*ps && !isspace(*ps))
    ps++;
  *e = ps;
  return *s < *e;
}

enum {COMMA, AND, ARTICLE, NOUN, VERB};

struct word {
  int length_;
  const char* s_;
};

word articles[] = {
  {1, "a"}, {3, "the"}
};
const size_t nr_articles = sizeof(articles) / sizeof(word);

word nouns[] = {
  {3, "tom"}, {5, "jerry"}, {5, "goofy"}, {6, "mickey"},
  {5, "jimmy"}, {3, "dog"}, {3, "cat"}, {5, "mouse"}
};
const size_t nr_nouns = sizeof(nouns) / sizeof(word);

word verbs[] = {
  {4, "hate"}, {4, "love"}, {4, "know"}, {4, "like"}
};
const size_t nr_verbs = sizeof(verbs) / sizeof(word);

bool accept(int wn)
{
  if (pws == pwe) {
    if (!get_word(&pws, &pwe))
      return false;
  }
  size_t nr_chars = pwe - pws, i;
  bool result = false;
  switch (wn) {
  case COMMA:
    result = nr_chars == 1 && *pws == ',';
    break;
  case AND:
    result = nr_chars == 3 && !strncmp(pws, "and", 3);
    break;
  case ARTICLE:
    for (i = 0; i < nr_articles; i++)
      if (nr_chars == articles[i].length_ &&
        !strncmp(pws, articles[i].s_, articles[i].length_))
        break;
    result = i < nr_articles;
    break;
  case NOUN:
    for (i = 0; i < nr_nouns; i++)
      if (nr_chars == nouns[i].length_ && !strncmp(pws, nouns[i].s_, nouns[i].length_))
        break;
    result = i < nr_nouns;
    break;
  case VERB:
    for (i = 0; i < nr_verbs; i++)
      if (!strncmp(pws, verbs[i].s_, verbs[i].length_)) {
        if (nr_chars == verbs[i].length_)
          break;
        const char* p = pws + verbs[i].length_;
        for ( ; p < pwe; p++)
          if (*p != 's')
            break;
        if (p == pwe)
          break;
      }
    result = i < nr_verbs;
    break;
  }
  if (result)
    pws = pwe;
  return result;
}

void statement(), action(), active_list(), actor();

void statement()
{
  action();
  while (accept(COMMA))
    action();
}

void action()
{
  active_list();
  if (accept(VERB))
    active_list();
  else
    throw -1;
}

void active_list()
{
  actor();
  while (accept(AND))
    actor();
}

void actor()
{
  if (accept(ARTICLE))
    ;
  if (accept(NOUN))
    ;
  else
    throw -1;
}

int main()
{
  string riddle;
  while (getline(cin, riddle)) {
    ps = pws = pwe = riddle.c_str();
    bool yes = false;
    try {
      statement();
      while (isspace(*pws))
        pws++;
      if (!*pws)
        yes = true;
      else
        throw -1;
    }
    catch (int) {
    }
    cout << ((yes) ? "YES I WILL\n" : "NO I WON'T\n");
  }
  return 0;
}

UVa 134 - Loglan-A Logical Language

Accepted date: 2016-09-16
Run Time: 0.000
Ranking (as of 2016-09-16): 290 out of 808
Language: C++

Another simple implementation of recursive descent parser.

/*
  UVa 134 - Loglan-A Logical Language

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

#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

string sentence;
const char *ps, *pws, *pwe;

bool get_word_or_name(const char** s, const char** e)
{
  while (isspace(*ps))
    ps++;
  *s = ps;
  while (*ps && !isspace(*ps) && *ps != '.')
    ps++;
  *e = ps;
  return *s < *e;
}

bool is_vowel(char c)
{
  return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

enum {A, MOD, BA, DA, LA, NAM, PREDA};

bool accept(int wn)
{
  if (pws == pwe) {
    if (!get_word_or_name(&pws, &pwe))
      return false;
  }
  bool result = false;
  switch (wn) {
  case A:
    result = pwe - pws == 1 && is_vowel(*pws);
    break;
  case MOD:
    result = pwe - pws == 2 && *pws == 'g' && is_vowel(*(pws + 1));
    break;
  case BA:
    result = pwe - pws == 2 && *pws == 'b' && is_vowel(*(pws + 1));
    break;
  case DA:
    result = pwe - pws == 2 && *pws == 'd' && is_vowel(*(pws + 1));
    break;
  case LA:
    result = pwe - pws == 2 && *pws == 'l' && is_vowel(*(pws + 1));
    break;
  case NAM:
    result = pwe > pws && !is_vowel(*(pwe - 1));
    break;
  case PREDA:
    result = pwe - pws == 5 && !is_vowel(*pws) && 
      (!is_vowel(*(pws + 1)) && is_vowel(*(pws + 2)) ||
        is_vowel(*(pws + 1)) && !is_vowel(*(pws + 2))) &&
      !is_vowel(*(pws + 3)) && is_vowel(*(pws + 4));
    break;
  }
  if (result)
    pws = pwe;
  return result;
}

void predclaim(), preds(), predname(), predstring(), statement(), verbpred();

void predclaim()
{
  if (accept(DA))
    preds();
  else {
    predname();
    if (accept(BA))
      preds();
    else
      throw -1;
  }
}

void preds()
{
  predstring();
  while (accept(A))
    predstring();
}

void predname()
{
  if (accept(LA))
    predstring();
  else if (accept(NAM))
    ;
  else
    throw -1;
}

void predstring()
{
  if (accept(PREDA)) {
    while (accept(PREDA))
    ;
  }
  else
    throw -1;
}

void statement()
{
  predname();
  verbpred();
  if (*ps && *ps != '.')
    predname();
}

void verbpred()
{
  if (accept(MOD))
    predstring();
  else
    throw -1;
}

int main()
{
  while (true) {
    string line;
    getline(cin, line);
    if (line[0] == '#')
      break;
    sentence.clear();
    while (true) {
      sentence += line;
      if (sentence.find_first_of('.') != string::npos)
        break;
      sentence += ' ';
      getline(cin, line);
    }
#ifdef DEBUG
    cout << sentence << endl;
#endif
//    transform(sentence.begin(), sentence.end(), sentence.begin(), (int(*)(int))tolower);
    bool good = false;
    try {
      ps = pws = pwe = sentence.c_str();
      statement();
      if (*ps == '.')
        good = true;
      else
        throw -1;
    }
    catch (int) {
      try {
        ps = pws = pwe = sentence.c_str();
        predclaim();
        if (*ps == '.')
          good = true;
      }
      catch (int) {
      }
    }
    cout << ((good) ? "Good\n" : "Bad!\n");
  }
  return 0;
}

UVa 622 - Grammar Evaluation

Accepted date: 2016-09-15
Run Time: 0.000
Ranking (as of 2016-09-15): 304 out of 680
Language: C++

A simple implementation of recursive descent parser.

/*
  UVa 622 - Grammar Evaluation

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

/*
< expression > := < component > | < component > + < expression >
< component > := < factor > | < factor > * < component >
< factor > := < positiveinteger > | (< expression >)
*/

#include <cstdio>
#include <cstring>
#include <cctype>

const int nr_chars_max = 255;

char s[nr_chars_max + 1], *ps;

int positive_integer()
{
  if (isdigit(*ps)) {
    int n = 0;
    do
      n = n * 10 + *ps++ - '0';
    while (isdigit(*ps));
    return n;
  }
  else
    return -1;
}

int expression();
int component();
int factor();

int factor()
{
  int n = positive_integer();
  if (n != -1)
    return n;
  else if (*ps == '(') {
    ps++;
    n = expression();
    if (*ps == ')')
      ps++;
    else
      throw -1;
    return n;
  }
  else {
    throw -1;
    return -1;
  }
}

int component()
{
  int n = factor();
  if (*ps == '*') {
    ps++;
    n *= component();
  }
  return n;
}

int expression()
{
  int n = component();
  if (*ps == '+') {
    ps++;
    n += expression();
  }
  return n;
}

int main()
{
  int n;
  scanf("%d", &n);
  while (n--) {
    scanf("%s", ps = s);
    try {
      int n = expression();
      if (*ps)
        throw -1;
      printf("%d\n", n);
    }
    catch (int e) {
      puts("ERROR");
    }
  }
  return 0;
}

UVa 707 - Robbery

Accepted date: 2016-09-13
Run Time: 0.010
Ranking (as of 2016-09-13): 12 out of 392
Language: C++

/*
  UVa 707 - Robbery

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

#include <cstdio>

const int W_max = 100, H_max = 100, t_max = 100;
int W, H, t, city[t_max + 1][H_max + 1][W_max + 1];

struct deduction {
  int r_, c_;
} deductions[t_max + 1];

const int nr_moves = 5;
const int moves[nr_moves][2] = {{0, 0}, {0, -1}, {0, 1}, {-1, 0}, {1, 0}};

void deduce(int ti, int r, int c)
{
#ifdef DEBUG
  printf("%d %d %d\n", ti, r, c);
#endif
  if (deductions[ti].r_ == -1)
    deductions[ti].r_ = r, deductions[ti].c_ = c;
  else if (r != deductions[ti].r_ || c != deductions[ti].c_)
    deductions[ti].c_ = -1;
}

int move(int ti, int r, int c)
{
  int& result = city[ti][r][c];
  if (result != -1)
    return result;
  if (ti == t) {
    result = 1;
    deduce(ti, r, c);
  }
  else {
    result = 0;
    for (int i = 0; i < nr_moves; i++) {
      int nr = r + moves[i][0], nc = c + moves[i][1];
      if (nr > 0 && nr <= H && nc > 0 && nc <= W && move(ti + 1, nr, nc)) {
        result = 1;
        deduce(ti, r, c);
      }
    }
  }
  return result;
}

int main()
{
  for (int nr = 1; ; nr++) {
    scanf("%d %d %d", &W, &H, &t);
    if (!W)
      break;
    for (int i = 1; i <= t; i++) {
      for (int j = 1; j <= H; j++)
        for (int k = 1; k <= W; k++)
          city[i][j][k] = -1;
      deductions[i].r_ = deductions[i].c_ = -1;
    }
    int n;
    scanf("%d", &n);
    while (n--) {
      int ti, Li, Ti, Ri, Bi;
      scanf("%d %d %d %d %d", &ti, &Li, &Ti, &Ri, &Bi);
      for (int i = Ti; i <= Bi; i++)
        for (int j = Li; j <= Ri; j++)
          city[ti][i][j] = 0;
    }
    for (int i = 1; i <= H; i++)
      for (int j = 1; j <= W; j++)
        move(1, i, j);
    printf("Robbery #%d:\n", nr);
    if (deductions[t].r_ == -1)
      puts("The robber has escaped.\n");
    else {
      int nr_deductions = 0;
      for (int i = 1; i <= t; i++)
        if (deductions[i].c_ != -1) {
          nr_deductions++;
          printf("Time step %d: The robber has been at %d,%d.\n",
            i, deductions[i].c_, deductions[i].r_);
        }
      if (nr_deductions)
        putchar('\n');
      else
        puts("Nothing known.\n");
    }
  }
  return 0;
}

UVa 1207 - AGTC

Accepted date: 2016-09-12
Run Time: 0.000
Ranking (as of 2016-09-12): 79 out of 481
Language: C++

/*
  UVa 1207 - AGTC

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

  This problem is similar to UVa 164 - String Computer, 
    UVa 526 - String Distance and Transform Process.
*/

#include <cstdio>
#include <cstring>

const int nr_chars_max = 1000;

enum {editMatchOrReplace, editInsert, editDelete};

struct edit_state {
  int cost_; // cost of reaching this state
/*
    int parent_; // parent state
*/
} edite_states[nr_chars_max + 1][nr_chars_max + 1];

int edit_distance(const char* s, const char* t, int sl, int tl)
{
  for (int i = 0; i < nr_chars_max + 1; i++) {
    // first row
    edite_states[0][i].cost_ = i;
/*
    edite_states[0][i].parent_ =  (i) ? editInsert : -1;
*/
    // first column
        edite_states[i][0].cost_ = i;
/*
    edite_states[i][0].parent_ = (i) ? editDelete : -1;
*/
  }

  for (int i = 1; i < sl; i++)
    for (int j = 1; j < tl; j++) {
      int costs[editDelete - editMatchOrReplace + 1];
      // For inserting or deleting or replacing characters, 
      // cost is one, while for maching characters, cost is zero.
      costs[editMatchOrReplace] =
        edite_states[i - 1][j - 1].cost_ + ((s[i] == t[j]) ? 0 : 1);
      costs[editInsert] = edite_states[i][j - 1].cost_ + 1;
      costs[editDelete] = edite_states[i - 1][j].cost_ + 1;
      edite_states[i][j].cost_ = costs[editMatchOrReplace];
/*
      edite_states[i][j].parent_ = editMatchOrReplace;
*/
      for (int k = editInsert; k <= editDelete; k++)
        if (costs[k] < edite_states[i][j].cost_) {
          edite_states[i][j].cost_ = costs[k];
/*
          edite_states[i][j].parent_ = k;
*/
        }
    }
  return edite_states[sl - 1][tl - 1].cost_;
} 

/*
void reconstruct_path(char* s, char* t, int i, int j, int& p, int& n)
{
  int parent = edite_states[i][j].parent_;
  if (parent == -1)
    p = n = 1;
  else if (parent == editMatchOrReplace) {
    reconstruct_path(s, t, i - 1,j - 1, p, n);
    if (s[i] != t[j]) {
      printf("%d Replace %d,%c\n", n, p, t[j]);
      n++;
    }
    p++;
  }
  else if (parent == editInsert) {
    reconstruct_path(s, t, i, j - 1, p, n);
    printf("%d Insert %d,%c\n", n, p, t[j]);
    p++; n++;
  }
  else if (parent == editDelete) {
    reconstruct_path(s, t, i - 1, j, p, n);
    printf("%d Delete %d\n", n, p);
    n++;
  }
}
*/

char s[nr_chars_max + 2], t[nr_chars_max + 2];

int main()
{
  while (true) {
    s[0] = t[0] = ' ';
    int sl, tl;
    if (scanf("%d %s", &sl, &s[1]) == EOF)
      break;
    scanf("%d %s", &tl, &t[1]);
    int d = edit_distance(s, t, sl + 1, tl + 1);
    printf("%d\n", d);
  }
  return 0;
}

UVa 12526 - Cellphone Typing

Accepted date: 2016-09-11
Run Time: 0.460
Ranking (as of 2016-09-11): 92 out of 399
Language: C++

/*
  UVa 12526 - Cellphone Typing

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

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

const int N_max = 100000, nr_chars_max = 80;
struct word {
  char s_[nr_chars_max + 1];

  bool operator<(const word& w) const {return strcmp(s_, w.s_) < 0;}
} words[N_max];

int typing(word& w, int i, int low, int high, int nr_typing)
{
  if (low == high || !w.s_[i])
    return nr_typing;
  char c = w.s_[i + 1];
  w.s_[i + 1] = '\0';
  int l = lower_bound(words + low, words + high, w) - words;
  w.s_[i]++;
  int h = lower_bound(words + low, words + high, w) - words;
  w.s_[i]--, w.s_[i + 1] = c;
  if (i && l == low && h == high)
    ;
  else
    nr_typing++;
  return typing(w, i + 1, l, h, nr_typing);
}

int main()
{
  int N;
  while (scanf("%d", &N) != EOF) {
    for (int i = 0; i < N; i++)
      scanf("%s", words[i].s_);
    sort(words, words + N);
    int nr_typings = 0;
    for (int i = 0; i < N; i++) {
      word w;
      strcpy(w.s_, words[i].s_);
      int nr = typing(w, 0, 0, N, 0);
#ifdef DEBUG
      printf("%s: %d\n", w.s_, nr);
#endif
      nr_typings += nr;
    }
    printf("%.2lf\n", static_cast<double>(nr_typings) / N);
  }
  return 0;
}

UVa 11058 - Encoding

Accepted date: 2016-09-08
Run Time: 0.000
Ranking (as of 2016-09-08): 10 out of 394
Language: C++

/*
  UVa 11058 - Encoding

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

#include <cstdio>
#include <cstring>

int main()
{
  const int nr_chars = 128, nr_letters = 'z' - 'a' + 1, S_max = 100;
  for (int N = 1; ; N++) {
    char S[S_max + 1], s[S_max + 1];
    if (scanf("%s", S) == EOF)
      break;
    char replacements[nr_chars];
    for (int i = 0; i < nr_letters; i++) {
      char c;
      scanf("%s", &c);
      replacements['a' + i] = c;
    }
    char *p, *q;
    for (p = S, q = s; *p; p++, q++)
      *q = replacements[*p];
    *q = '\0';
#ifdef DEBUG
    printf("%s\n", s);
#endif
    int R;
    scanf("%d", &R);
    while (R--) {
      int P;
      char X, Y;
      scanf("%d %c %c", &P, &X, &Y);
      for (p = S + P, q = s + P; *p; p++, q++)
        if (*p == X)
          *q = Y;
    }
    printf("Case #%d: The encoding string is %s.\n\n", N, s);
  }
  return 0;
}

UVa 11107 - Life Forms

Accepted date: 2016-09-07
Run Time: 0.310
Ranking (as of 2016-09-08): 148 out of 486
Language: C++

Note that suffix array construction is based on a sample code that can be downloaded from Competitive Programming support materials site, with a few modifications.
The rest of the code in the main function is a variation of Longest Common Substring calculation.

/*
  UVa 11107 - Life Forms

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

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

typedef pair<int, int> ii;

#define MAX_N 101010                         // second approach: O(n log n)
char T[MAX_N];                   // the input string, up to 100K characters
int n;                                        // the length of input string
int RA[MAX_N], tempRA[MAX_N];        // rank array and temporary rank array
int SA[MAX_N], tempSA[MAX_N];    // suffix array and temporary suffix array
int c[MAX_N];                                    // for counting/radix sort

char P[MAX_N];                  // the pattern string (for string matching)
int m;                                      // the length of pattern string

int Phi[MAX_N];                      // for computing longest common prefix
int PLCP[MAX_N];
int LCP[MAX_N];  // LCP[i] stores the LCP between previous suffix T+SA[i-1]
                                              // and current suffix T+SA[i]

bool cmp(int a, int b) { return strcmp(T + a, T + b) < 0; }      // compare

void constructSA_slow() {               // cannot go beyond 1000 characters
  for (int i = 0; i < n; i++) SA[i] = i; // initial SA: {0, 1, 2, ..., n-1}
  sort(SA, SA + n, cmp); // sort: O(n log n) * compare: O(n) = O(n^2 log n)
}

void countingSort(int k) {                                          // O(n)
  int i, sum, maxi = max(300, n);   // up to 255 ASCII chars or length of n
  memset(c, 0, sizeof c);                          // clear frequency table
  for (i = 0; i < n; i++)       // count the frequency of each integer rank
    c[i + k < n ? RA[i + k] : 0]++;
  for (i = sum = 0; i < maxi; i++) {
    int t = c[i]; c[i] = sum; sum += t;
  }
  for (i = 0; i < n; i++)          // shuffle the suffix array if necessary
    tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
  for (i = 0; i < n; i++)                     // update the suffix array SA
    SA[i] = tempSA[i];
}

void constructSA() {         // this version can go up to 100000 characters
  int i, k, r;
  for (i = 0; i < n; i++) RA[i] = T[i];                 // initial rankings
  for (i = 0; i < n; i++) SA[i] = i;     // initial SA: {0, 1, 2, ..., n-1}
  for (k = 1; k < n; k <<= 1) {       // repeat sorting process log n times
    countingSort(k);  // actually radix sort: sort based on the second item
    countingSort(0);          // then (stable) sort based on the first item
    tempRA[SA[0]] = r = 0;             // re-ranking; start from rank r = 0
    for (i = 1; i < n; i++)                    // compare adjacent suffixes
      tempRA[SA[i]] = // if same pair => same rank r; otherwise, increase r
      (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
    for (i = 0; i < n; i++)                     // update the rank array RA
      RA[i] = tempRA[i];
    if (RA[SA[n-1]] == n-1) break;               // nice optimization trick
} }

void computeLCP_slow() {
  LCP[0] = 0;                                              // default value
  for (int i = 1; i < n; i++) {                // compute LCP by definition
    int L = 0;                                       // always reset L to 0
    while (T[SA[i] + L] == T[SA[i-1] + L]) L++;      // same L-th char, L++
    LCP[i] = L;
} }

void computeLCP() {
  int i, L;
  Phi[SA[0]] = -1;                                         // default value
  for (i = 1; i < n; i++)                            // compute Phi in O(n)
    Phi[SA[i]] = SA[i-1];    // remember which suffix is behind this suffix
  for (i = L = 0; i < n; i++) {             // compute Permuted LCP in O(n)
    if (Phi[i] == -1) { PLCP[i] = 0; continue; }            // special case
    while (T[i + L] != '.' && T[i + L] == T[Phi[i] + L]) L++; // L increased max n times
    PLCP[i] = L;
    L = max(L-1, 0);                             // L decreased max n times
  }
  for (i = 0; i < n; i++)                            // compute LCP in O(n)
    LCP[i] = PLCP[SA[i]];   // put the permuted LCP to the correct position
}

ii stringMatching() {                      // string matching in O(m log n)
  int lo = 0, hi = n-1, mid = lo;              // valid matching = [0..n-1]
  while (lo < hi) {                                     // find lower bound
    mid = (lo + hi) / 2;                              // this is round down
    int res = strncmp(T + SA[mid], P, m);  // try to find P in suffix 'mid'
    if (res >= 0) hi = mid;        // prune upper half (notice the >= sign)
    else          lo = mid + 1;           // prune lower half including mid
  }                                      // observe `=' in "res >= 0" above
  if (strncmp(T + SA[lo], P, m) != 0) return ii(-1, -1);    // if not found
  ii ans; ans.first = lo;
  lo = 0; hi = n - 1; mid = lo;
  while (lo < hi) {            // if lower bound is found, find upper bound
    mid = (lo + hi) / 2;
    int res = strncmp(T + SA[mid], P, m);
    if (res > 0) hi = mid;                              // prune upper half
    else         lo = mid + 1;            // prune lower half including mid
  }                           // (notice the selected branch when res == 0)
  if (strncmp(T + SA[hi], P, m) != 0) hi--;                 // special case
  ans.second = hi;
  return ans;
} // return lower/upperbound as first/second item of the pair, respectively

ii LRS() {                 // returns a pair (the LRS length and its index)
  int i, idx = 0, maxLCP = -1;
  for (i = 1; i < n; i++)                         // O(n), start from i = 1
    if (LCP[i] > maxLCP)
      maxLCP = LCP[i], idx = i;
  return ii(maxLCP, idx);
}

const int nr_life_forms_max = 100, nr_chars_max = 1000;
int nr_life_forms, lengths[nr_life_forms_max], counters[nr_life_forms_max];
int Owners[MAX_N];

int owner(int idx)
{
  for (int i = 0, length = lengths[i] + 1; ; i++, length += lengths[i] + 1) {
    if (idx < length - 1)
      return i;
    else if (idx == length - 1)
      return -1;
  }
}

/*
int owner(int idx) { return (idx < n-m-1) ? 1 : 2; }
*/

ii LCS() {                 // returns a pair (the LCS length and its index)
  int i, idx = 0, maxLCP = -1;
  for (i = 1; i < n; i++)                         // O(n), start from i = 1
    if (owner(SA[i]) != owner(SA[i-1]) && LCP[i] > maxLCP)
      maxLCP = LCP[i], idx = i;
  return ii(maxLCP, idx);
}

int main()
{
  bool printed = false;
  while (true) {
    scanf("%d", &nr_life_forms);
    if (!nr_life_forms)
      break;
    if (printed)
      putchar('\n');
    else
      printed = true;
    if (nr_life_forms == 1) {
      scanf("%s", T);
      puts(T);
      continue;
    }
    n = 0;
    for (int i = 0; i < nr_life_forms; i++) {
      scanf("%s", T + n);
      lengths[i] = strlen(T + n);
      n += lengths[i];
      T[n++] = '.';
    }
    T[n] = '\0';
    constructSA(); // O(n log n)
    computeLCP(); // O(n)
    for (int i = 0; i < n; i++)
      Owners[i] = owner(SA[i]);
#ifdef DEBUG
    printf("\nThe LCP information of '%s':\n", T);
    printf("i     SA[i] LCP[i] Owner Suffix\n");
    for (int k = 0; k < n; k++)
      printf("%4d  %4d  %4d   %4d  %s\n", k, SA[k], LCP[k], Owners[k], T + SA[k]);
#endif
    int lcs_length = 0;
    memset(counters, 0, sizeof(counters));
    for (int i = nr_life_forms, j = nr_life_forms, total = 0; j < n; ) {
      if (total <= nr_life_forms / 2) {
        if (!counters[Owners[j++]]++)
          ++total;
      }
      if (total > nr_life_forms / 2) {
        lcs_length = max(lcs_length, LCP[min_element(LCP + i + 1, LCP + j) - LCP]);
#ifdef DEBUG
        printf("LCS [%d, %d): %d\n", i, j, lcs_length);
#endif
        if (!--counters[Owners[i++]])
          --total;
      }
    }
    if (!lcs_length) {
      puts("?");
      continue;
    }
    int psa = -1;
    memset(counters, 0, sizeof(counters));
    for (int i = nr_life_forms, j = nr_life_forms, total = 0; j < n; ) {
      if (total <= nr_life_forms / 2) {
        if (!counters[Owners[j++]]++)
          ++total;
      }
      if (total > nr_life_forms / 2) {
        int k = min_element(LCP + i + 1, LCP + j) - LCP;
        if (LCP[k] == lcs_length &&
          (psa == -1 || strncmp(T + psa, T + SA[k], lcs_length))) {
          psa = SA[k];
          char c = T[psa + lcs_length];
          T[psa + lcs_length] = '\0';
#ifdef DEBUG
          printf("LCS [%d, %d): %s\n", i, j, T + psa);
#else
          puts(T + psa);
#endif
          T[psa + lcs_length] = c;
        }
        if (!--counters[Owners[i++]])
          --total;
      }
    }
  }
  return 0;
}