UVa 10443 - Rock

Accepted date: 2013-07-27
Ranking (as of 2013-07-27): 181 out of 1122
Language: C++

/*
  UVa 10443 - Rock

  To build using Visual Studio 2010:
    cl -EHsc -O2 UVa_10443_Rock.cpp
*/

#include <cstdio>

const int r_max = 100, c_max = 100;
char grids[2][r_max][c_max + 1];

char war(char ci, char cj)
{
/*
  P Q R S
P P - P S
Q - - - -
R P - R R
S S - R S
*/
  const char wars[4][4] = {
    // wars[ci][cj] is the result of war between (ci - 'P') and (cj - 'P')
    {'P', '\0', 'P', 'S'},
    {'\0', '\0', '\0', '\0'},
    {'P', '\0', 'R', 'R'},
    {'S', '\0', 'R', 'S'}
  };
  return wars[ci - 'P'][cj - 'P'];
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int r, c, n;
    scanf("%d %d %d", &r, &c, &n);
    for (int i = 0; i < r; i++)
      scanf("%s", grids[0][i]);
    for (int k = 1; k <= n; k++) {
      int ck = k % 2, pk = (k - 1) % 2;
      for (int i = 0; i < r ; i++)
        for (int j = 0; j < c; j++) {
          char cc, pc = grids[pk][i][j];
          if (i && (cc = war(pc, grids[pk][i - 1][j])) != pc ||
            i < r - 1 && (cc = war(pc, grids[pk][i + 1][j])) != pc ||
            j && (cc = war(pc, grids[pk][i][j - 1])) != pc ||
            j < c - 1 && (cc = war(pc, grids[pk][i][j + 1])) != pc)
            grids[ck][i][j] = cc;
          else
            grids[ck][i][j] = pc;
        }
    }
    for (int i = 0; i < r; i++) {
      grids[n % 2][i][c] = '\0';
      puts(grids[n % 2][i]);
    }
    if (t)
      putchar('\n');
  }
  return 0;
}

UVa 11988 - Broken Keyboard (a.k.a. Beiju Text)

Accepted date: 2013-07-20
Ranking (as of 2013-07-20): 28 out of 915
Language: C++

/*
  UVa 11988 - Broken Keyboard (a.k.a. Beiju Text)

  To build using Visual Studio 2010:
    cl -EHsc -O2 UVa_11988_Broken_Keyboard.cpp
*/

#include <cstdio>

const int nr_chars_max = 100000;
char s[nr_chars_max];

struct cnode { // doubly-linked list node
  char c_;
  cnode *prev_, *next_;
};

cnode cnodes[nr_chars_max];

int main()
{
  while (gets(s)) {
    cnode head;
    head.prev_ = head.next_ = &head;
    char* p;
    cnode* pcnode = &head;
    int cni = 0;
    for (p = s; *p; p++) {
      if (*p == '[')
        pcnode = &head;
      else if (*p == ']')
        pcnode = head.prev_;
      else {
        cnode* pcn = &cnodes[cni++];
        pcn->c_ = *p;
        pcn->prev_ = pcnode; pcn->next_ = pcnode->next_;
        pcnode->next_->prev_ = pcn; pcnode->next_ = pcn;
        pcnode = pcn;
      }
    }
    p = s;
    for (pcnode = head.next_; pcnode != &head; pcnode = pcnode->next_)
      *p++ = pcnode->c_;
    *p = '\0';
    puts(s);
  }
  return 0;
}

UVa 585 - Triangles

Accepted date: 2013-07-18
Ranking (as of 2013-07-20): 326 out of 890
Language: C++

Used brute-force search.

/*
  UVa 585 - Triangles

  To build using Visual Studio 2010:
    cl -EHsc -O2 UVa_585_Triangles.cpp
*/

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

const int n_max = 100;
char triangles[n_max][n_max * 2];

int largest_triangle(int n, int ti, int tj)
{
  int nr = 0;
  for (int k = 1; ti < n; k++, ti++) {
    if (tj - k < ti + 1 || tj + k > 2 * n - ti - 3)
      return nr;
    for (int j = tj - k; j <= tj + k; j++)
      if (triangles[ti][j] != '-')
        return nr;
    nr += 2 * k + 1;
  }
  return nr;
}

int largest_inverted_triangle(int n, int ti, int tj)
{
  int nr = 0;
  for (int k = 1; ti >= 0; k++, ti--) {
    if (tj - k < ti || tj + k > 2 * n - ti - 2)
      return nr;
    for (int j = tj - k; j <= tj + k; j++)
      if (triangles[ti][j] != '-')
        return nr;
    nr += 2 * k + 1;
  }
  return nr;
}

int main()
{
  for (int nr = 1; ; nr++) {
    int n;
    scanf("%d", &n);
    getchar(); // skip '\n'
    if (!n)
      break;
    for (int i = 0; i < n; i++)
      gets(triangles[i]);
    int largest = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1, jh = 2 * n - i - 1; j < jh; j += 2)
        if (triangles[i][j] == '-')
          largest = max(largest, 1 + largest_triangle(n, i + 1, j));
    for (int i = n - 1; i >= 0; i--)
      for (int j = i, jh = 2 * n - i - 1; j < jh; j += 2)
        if (triangles[i][j] == '-')
          largest = max(largest, 1 + largest_inverted_triangle(n, i - 1, j));
    printf("Triangle #%d\nThe largest triangle area is %d.\n\n", nr, largest);
  }
  return 0;
}

UVa 704 - Colour Hash

Accepted date: 2011-10-12
Ranking (as of 2013-07-13): 148 out of 708
Language: C++

/*
  UVa 704 - Colour Hash

  To build using Visual Studio 2008:
    cl -EHsc -O2 colour_hash.bfs.cache.cpp
*/

#include <iostream>
#include <map>
#include <deque>
#include <queue>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

enum rotation { // rotations
  unknown = 0,
  left_clockwise = 1, // left wheel clockwise
  right_clockwise = 2, // right wheel clockwise
  left_counterclockwise = 3, // left wheel counterclockwise
  right_counterclockwise = 4, // right wheel counterclockwise
};

typedef pair<unsigned long long, unsigned long long> wheels;
/*
  wheels.first consists of left wheel numbers and 
    wheels.second consists of right wheel numbers.
  i-th (i >= 0) number occupies between (47 - i * 4)-th and 
    (44 - i * 4)-th bits of wheels.first/wheels.second.
  The final condition of wheels are represented as 
    wheels(0x034305650121, 0x078709a90121).
*/

const size_t numbers_per_wheel = 12;
  // count of numbers (triangle/separator) per wheel
const size_t max_movements = 16; // max. number of movements
const wheels wheels_solved(0x034305650121, 0x078709a90121);
  // the final condition of wheels

map< wheels, deque<char> > latter_half_cache;
  // key is a state, value is the sequence of movements 
  // that leads to the final state

wheels rotate_wheel(rotation r, const wheels& w)
{
  const unsigned long long mask_8_bits = 0xff, mask_12_bits = 0xfff;
  unsigned long long left = w.first, right = w.second;
  unsigned long long b;
  switch (r) {
  case left_clockwise: // left wheel clockwise
    b = left & mask_8_bits; left >>= 8; left |= b << 40;
    right &= ~mask_12_bits; right |= left & mask_12_bits;
    break;
  case right_clockwise: // right wheel clockwise
    b = (right & mask_8_bits << 40) >> 40;
    right &= ~(mask_8_bits << 40); right <<= 8; right |= b;
    left &= ~mask_12_bits; left |= right & mask_12_bits;
    break;
  case left_counterclockwise: // left wheel counterclockwise
    b = (left & mask_8_bits << 40) >> 40;
    left &= ~(mask_8_bits << 40); left <<= 8; left |= b;
    right &= ~mask_12_bits; right |= left & mask_12_bits;
    break;
  case right_counterclockwise: // right wheel counterclockwise
    b = right & mask_8_bits; right >>= 8; right |= b << 40;
    left &= ~mask_12_bits; left |= right & mask_12_bits;
    break;
  }
  return wheels(left, right);
}

bool rotate_wheel_and_cache(rotation r, const wheels& w, const deque<char>& m,
  queue<wheels>& q)
{
  wheels nw = rotate_wheel(r, w);
  if (latter_half_cache.find(nw) != latter_half_cache.end())
    return false;
  rotation nr;
  switch (r) {
  case left_clockwise:
    nr = left_counterclockwise; break;
  case right_clockwise:
    nr = right_counterclockwise; break;
  case left_counterclockwise:
    nr = left_clockwise; break;
  case right_counterclockwise:
    nr = right_clockwise; break;
  }
  deque<char> nm(m);
  nm.push_front(nr);
  latter_half_cache.insert(make_pair(nw, nm));
  q.push(nw);
  return true;
}

void generate_state_cache()
{
/*
  Starting from the final state (configuration), 
  do a BFS (Breadth First Search) and cache the states that can be reached 
  in 8 steps (movements) or less.
*/
  latter_half_cache.insert(make_pair(wheels_solved, deque<char>()));
  queue<wheels> q;
  q.push(wheels_solved);
  while (!q.empty()) {
    wheels w = q.front(); q.pop();
    deque<char> m = latter_half_cache[w];
    if (m.size() < max_movements / 2) {
      for (int r = left_clockwise; r <= right_counterclockwise; r++)
        rotate_wheel_and_cache(static_cast<rotation>(r), w, m, q);
    }
  }
#ifdef DEBUG
  cerr << "number of latter_half_cache entries = " <<
    latter_half_cache.size() << endl;
#endif
}

bool rotate_wheel_and_cache(rotation r, const wheels& w, const deque<char>& m,
  queue<wheels>& q, map< wheels, deque<char> >& cache)
{
  wheels nw = rotate_wheel(r, w);
  if (cache.find(nw) != cache.end())
    return false;
  deque<char> nm(m);
  nm.push_back(r);
  cache.insert(make_pair(nw, nm));
  q.push(nw);
  return true;
}

bool solve_state(const wheels& w, deque<char>& mv)
{
  bool solved = false;
  map< wheels, deque<char> > cache;
  cache.insert(make_pair(w, deque<char>()));
  queue<wheels> q;
  q.push(w);
  map< wheels, deque<char> >::const_iterator lhce = latter_half_cache.end();
  while (!q.empty()) {
    wheels w = q.front(); q.pop();
    deque<char>& m = cache[w];
    map< wheels, deque<char> >::const_iterator lhci = latter_half_cache.find(w);
    if (lhci != lhce) {
      solved = true;
      mv = m;
      mv.insert(mv.end(), lhci->second.begin(), lhci->second.end());
      break;
    }
    else if (m.size() < max_movements / 2) {
      for (int r = left_clockwise; r <= right_counterclockwise; r++)
        rotate_wheel_and_cache(static_cast<rotation>(r), w, m, q, cache);
    }
  }
  return solved;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  generate_state_cache();
  int n;
  cin >> n;
  while (n--) {
    int nr;
    wheels w(0, 0);
    for (size_t i = 0; i < numbers_per_wheel; i++) {
      cin >> nr;
      w.first <<= 4; w.first |= nr;
    }
    for (size_t i = 0; i < numbers_per_wheel; i++) {
      cin >> nr;
      w.second <<= 4; w.second |= nr;
    }
    deque<char> mv;
    if (solve_state(w, mv)) {
      if (mv.empty())
        cout << "PUZZLE ALREADY SOLVED\n";
      else {
        for (deque<char>::const_iterator i = mv.begin(), e = mv.end();
          i != e; ++i)
          cout << static_cast<int>(*i);
        cout << endl;
      }
    }
    else
      cout << "NO SOLUTION WAS FOUND IN 16 STEPS\n";
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

Uva 11198 - Dancing Digits

Accepted date: 2011-10-14
Ranking (as of 2013-07-13): 58 out of 212
Language: C++

/*
  Uva 11198 - Dancing Digits

  To build using Visual Studio 2008:
    cl -EHsc -O2 dancing_digits.cpp
*/

#include <iostream>
#ifdef DEBUG
#include <iomanip>
#endif
#include <queue>
#include <map>
#include <cstdlib>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int nr_digits = 8;

bool dancing_digits(int i, int j, long long digits, int nr_dances,
  queue<long long>& q, map<long long, int>& cache);
int dancing_digits(long long digits);

bool are_digits_sorted(long long digits) // see if the digits are sorted
{
  for (int i = 0; i < nr_digits; i++, digits >>= 8) {
    char d = static_cast<char>(digits & 0xff);
    if (abs(d) != i + 1) // see if d is at the right place
      return false;
  }
  return true;
}

int get_digit(int i, long long digits) // return i-th digit from digits
{
  char d = static_cast<char>((digits >> (i * 8)) & 0xff);
  return static_cast<int>(d);
}

long long set_digit(int i, int d, long long digits)
{
  long long mask = static_cast<long long>(0xff) << (i * 8);
  digits &= ~mask;
  digits |= static_cast<long long>(static_cast<unsigned char>(d)) << (i * 8);
  return digits;
}

bool are_dancing_pairs(int i, int j, long long digits)
{
  int d = get_digit(i, digits), e = get_digit(j, digits);
  if (d * e > 0)
    return false;
  d = abs(d); e = abs(e);
  return (d == 1 &&
      (e == 2 || e == 4 || e == 6) || d == 2 && (e == 1 || e == 3 || e == 5) ||
    d == 3 &&
      (e == 2 || e == 4 || e == 8) || d == 4 && (e == 1 || e == 3 || e == 7) ||
    d == 5 &&
      (e == 2 || e == 6 || e == 8) || d == 6 && (e == 1 || e == 5 || e == 7) ||
    d == 7 && (e == 4 || e == 6) || d == 8 && (e == 3 || e == 5));
}

long long insert_digit(int i, int j, long long digits)
  // insert i-th digit before j-th digit in digits
{
  if (i < j - 1) {
    int d = get_digit(i, digits);
    for ( ; i < j - 1; i++)
      digits = set_digit(i, get_digit(i + 1, digits), digits);
    digits = set_digit(j - 1, d, digits);
  }
  else if (i > j) {
    int d = get_digit(i, digits);
    for ( ; i > j; i--)
      digits = set_digit(i, get_digit(i - 1, digits), digits);
    digits = set_digit(j, d, digits);
  }
  return digits;
}

bool dancing_digits(int i, int j, long long digits, int nr_dances,
  queue<long long>& q, map<long long, int>& cache)
{
  digits = insert_digit(i, j, digits);
  pair<map<long long, int>::iterator, bool> result =
    cache.insert(make_pair(digits, nr_dances));
  if (result.second)
    q.push(digits);
  return result.second;
}

int dancing_digits(long long digits)
{
  map<long long, int> cache;
    // key is a state (digits), value is the number of dances that leads to it
  cache.insert(make_pair(digits, 0));
  queue<long long> q;
  q.push(digits);
  bool sorted;
  int nr_dances;
  while (!q.empty()) {
    digits = q.front(); q.pop();
    nr_dances = cache[digits];
    if (sorted = are_digits_sorted(digits))
      break;
    nr_dances++;
    for (int i = 0; i < nr_digits - 1; i++)
      for (int j = i + 1; j < nr_digits; j++)
        if (are_dancing_pairs(i, j, digits)) {
          if (j != i + 1) {
            dancing_digits(i, j, digits, nr_dances, q, cache);
            dancing_digits(j, i, digits, nr_dances, q, cache);
            dancing_digits(j, i + 1, digits, nr_dances, q, cache);
          }
          if (j < nr_digits - 1)
            dancing_digits(i, j + 1, digits, nr_dances, q, cache);
        }
  }
  return (sorted) ? nr_dances : -1;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int c = 1; ; c++) {
    int d;
    cin >> d;
    if (!d)
      break;
    long long digits = static_cast<unsigned char>(d);
      // i-th (i >= 0) digit occupies bit (i * 8) - (i * 8 + 7)
    for (int i = 1; i < nr_digits; i++) {
      cin >> d;
      digits |= static_cast<long long>(static_cast<unsigned char>(d)) << (8 * i);
    }
#ifdef DEBUG
    cout << hex << setfill('0') <<
      setw(16) << digits << dec << endl;
#endif
    cout << "Case " << c << ": " <<
      dancing_digits(digits) << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 270 - Lining Up

Accepted date: 2011-10-22<br/>
Ranking (as of 2013-07-13): 79 out of 991<br/>
Language: C++<br/>

<pre class="prettyprint">

/*
  UVa 270 - Lining Up

  To build using Visual Studio 2008:
    cl -EHsc -O2 lining_up.slope.cpp

  This implementation assumes that all points are unique.
*/

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cfloat>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

struct point {
  double x_, y_;

  point() : x_(0), y_(0) {}
  point(double x, double y) : x_(x), y_(y) {}
  point(const point &p) : x_(p.x_), y_(p.y_) {}
  bool operator==(const point& p) const {return x_ == p.x_ && y_ == p.y_;}
};

const int nr_points_max = 700;
point points[nr_points_max];
double slopes[nr_points_max];

double calculate_slope(const point& p1, const point& p2)
{
  double dx = p1.x_ - p2.x_, dy = p1.y_ - p2.y_;
  if (dx == 0.0)
    return FLT_MAX;
  return dy / dx;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int nr_cases;
  cin >> nr_cases;
  string line;
  getline(cin, line); // skip '\n'
  getline(cin, line); // skip a blank line
  while (nr_cases--) {
    int nr_points = 0;
    while (true) {
      getline(cin, line);
      if (line.empty())
        break;
      istringstream iss(line);
      int x, y;
      iss >> x >> y;
      points[nr_points].x_ = static_cast<double>(x);
      points[nr_points].y_ = static_cast<double>(y);
      nr_points++;
    }
    if (nr_points < 3)
      cout << nr_points << endl << endl;
    else {
      int max_nr_collinear = 2;
      for (int i = 0; i < nr_points; i++) {
        int j, k;
        for (j = 0, k = 0; j < i; j++, k++)
          slopes[k] = calculate_slope(points[i], points[j]);
        for (j = i + 1; j < nr_points; j++, k++)
          slopes[k] = calculate_slope(points[i], points[j]);
        sort(slopes, slopes + nr_points - 1);
        int nr_collinear = 0;
        for (j = 0, k = 1; k < nr_points - 1; k++)
          if (fabs(slopes[j] - slopes[k]) > FLT_EPSILON) {
            if (j + 1 < k)
              max_nr_collinear = max(max_nr_collinear, k - j + 1);
            j = k;
          }
        if (j + 1 < k)
          max_nr_collinear = max(max_nr_collinear, k - j + 1);
      }
      cout << max_nr_collinear << endl;
    }
    if (nr_cases)
      cout << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

</pre>

UVa 10057 - A mid-summer night's dream

Accepted date: 2011-10-25
Ranking (as of 2013-07-13): 385 out of 1001
Language: C++

/*
  UVa 10057 - A mid-summer night's dream

  To build using Visual Studio 2008:
    cl -EHsc -O2 summer_nights_dream.cpp
*/

#include <iostream>
#include <cstring>
using namespace std;

const int nr_max = 65536;
int counters[nr_max]; // counters[i] is the number of occurrences of i

int main()
{
  int n;
  while (cin >> n) {
    memset(counters, 0, sizeof(counters));
    int i;
    for (i = 0; i < n; i++) {
      int j;
      cin >> j;
      counters[j]++;
    }
    int median = 0, another_median = -1;
    if (n & 1) { // n is odd
      for (i = 0; ; median++) { // scan a median
        i += counters[median]; // accumulate the number of occurrences
        if (i > n / 2)
          break;
      }
    }
    else {
      for (i = 0; ; median++) {
        i += counters[median];
        if (i >= n / 2)
          break;
      }
      if (i < n / 2 + 1) {
        for (another_median = median + 1; ; another_median++)
          if (counters[another_median])
            break;
      }
    }
    if (another_median == -1) // median is unique
      cout << median << ' ' << counters[median] << ' ' << 1 << endl;
    else
      cout << median << ' ' <<
        counters[median] + counters[another_median] << ' ' <<
        another_median - median + 1 << endl;
  }
  return 0;
}

UVa 10487 - Closest Sums

Accepted date: 2011-10-29
Ranking (as of 2013-07-13): 264 out of 2245
Language: C++

/*
  UVa 10487 - Closest Sums

  To build using Visual Studio 2008:
    cl -EHsc -O2 closest_sums.cpp
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int nr_max = 1000;

int closest_sum(int n, const vector<int>& numbers, int s)
{
  int pcs, pd = -1;
  for (int i = 0, j = n - 1; i < j; ) {
    int cs = numbers[i] + numbers[j];
    if (cs == s)
      return cs;
    int d = abs(s - cs);
    if (cs > s)
      j--;
    else
      i++;
    if (pd == -1 || pd > d) {
      pcs = cs; pd = d;
    }
  }
  return pcs;
}

int main()
{
  vector<int> numbers(nr_max);
  for (int c = 1; ; c++) {
    int n;
    cin >> n;
    if (!n)
      break;
    for (int i = 0; i < n; i++)
      cin >> numbers[i];
    sort(numbers.begin(), numbers.begin() + n);
    cout << "Case " << c << ":\n";
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
      int s;
      cin >> s;
      cout << "Closest sum to " << s <<
        " is " << closest_sum(n, numbers, s) << ".\n";
    }
  }
  return 0;
}

UVa 10020 - Minimal coverage

Accepted date: 2011-11-05
Ranking (as of 2013-07-13): 620 out of 1913
Language: C++

/*
  UVa 10020 - Minimal coverage

  To build using Visual Studio 2008:
    cl -EHsc -O2 minimal_coverage.cpp
*/

#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <limits>
using namespace std;

const size_t nr_segments_max = 100000;
pair<int, int> segments[nr_segments_max + 1];
  // segments[i].first is i-th segment's left end, 
  // and segments[i].second is its right end
int chosen_segments[nr_segments_max];
  // indices of chosen segments from segments[]

bool compare_segment(const pair<int, int>& i, const pair<int, int>& j)
{
  if (i.first < j.first)
    return true;
  else if (i.first > j.first)
    return false;
  else
    return i.second > j.second;
}

int choose_segments(int m, int nr_segments)
{
  // sort the segments in ascending order of their left ends and 
  // for the ties in descending order of their right ends
  sort(segments, segments + nr_segments, compare_segment);
  // find the leftmost segment
  int si = 0, psi = -1;
  for ( ; si < nr_segments; si++) {
    if (segments[si].first > 0)
      break;
    else if (psi == -1 || segments[si].second > segments[psi].second)
      psi = si;
  }
  int ci = 0;
  chosen_segments[ci++] = psi;
  if (segments[psi].second >= m)
    return ci; // segment [0, m] is covered by only one segment
  for ( ; si < nr_segments; si++) {
    if (segments[psi].second < segments[si].first)
      // there is a segment that is not covered
      return 0;
    if (segments[psi].second >= segments[si].second)
      // segments[si] is completely covered by segments[psi]
      continue;
    if (segments[chosen_segments[ci - 1]].second < segments[si].first)
      ci++;
    chosen_segments[ci] = si;
    if (segments[si].second >= m)
      break;
    psi = si;
  }
  return ci + 1;
}

int main()
{
  int nr_cases;
  cin >> nr_cases;
  string s;
  getline(cin, s); // skip '\n'
  getline(cin, s); // skip a blank line
  while (nr_cases--) {
    getline(cin, s);
    istringstream iss(s);
    int m;
    iss >> m;
    iss.clear();
    int nr_segments = 0;
    int l_min = numeric_limits<int>::max(),
      r_max = numeric_limits<int>::min();
    while (true) {
      getline(cin, s);
      iss.str(s);
      pair<int, int> sg;
      iss >> segments[nr_segments].first >>
        segments[nr_segments].second;
      iss.clear();
      if (!segments[nr_segments].first && !segments[nr_segments].second)
        break;
      l_min = min(l_min, segments[nr_segments].first);
      r_max = max(r_max, segments[nr_segments].second);
      nr_segments++;
    }
    int nr_chosen_segments = (l_min > 0 || r_max < m) ?
      0 : choose_segments(m, nr_segments);
    cout << nr_chosen_segments << endl;
    for (int i = 0; i < nr_chosen_segments; i++)
      cout << segments[chosen_segments[i]].first << ' ' <<
        segments[chosen_segments[i]].second << endl;
    if (nr_cases) {
      cout << endl;
      getline(cin, s); // skip a line
    }
  }
  return 0;
}

UVa 10405 - Longest Common Subsequence

Accepted date: 2011-11-11
Ranking (as of 2013-07-13): 159 out of 6767
Language: C++

/*
  UVa 10405 - Longest Common Subsequence

  To build using Visual Studio 2008:
    cl -EHsc -O2 longest_common_subsequence.cpp
*/

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

const int nr_chars_max = 1024;
char first_s[nr_chars_max], second_s[nr_chars_max];
int lcs_c[2][nr_chars_max];

int lcs(int first_s_length, int second_s_length)
{
  memset(lcs_c[0], 0, sizeof(int) * (second_s_length + 1));
  memset(lcs_c[1], 0, sizeof(int) * (second_s_length + 1));
  for (int i = 1; i <= first_s_length; i++) {
    int ci = i % 2, pi = (i - 1) % 2;
    for (int j = 1; j <= second_s_length; j++) {
      if (first_s[i - 1] == second_s[j - 1])
        lcs_c[ci][j] = lcs_c[pi][j - 1] + 1;
      else
        lcs_c[ci][j] = max(lcs_c[ci][j - 1], lcs_c[pi][j]);
    }
  }
  return lcs_c[first_s_length % 2][second_s_length];
}

int main()
{
  while (gets(first_s)) {
    gets(second_s);
    printf("%d\n", lcs(strlen(first_s), strlen(second_s)));
  }
  return 0;
}

UVa 10465 - Homer Simpson

Accepted date: 2011-11-23
Ranking (as of 2013-07-13): 1685 out of 2392
Language: C++

/*
  UVa 10465 - Homer Simpson

  To build using Visual Studio 2008:
    cl -EHsc -O2 homer_simpson.cpp
*/

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

pair<int, int> how_many_burgers_to_eat(int m, int n, int t)
{
  vector< pair<bool, int> > burgers(t + 1, make_pair(false, 0));
    // burgers[i].first is true if time of i is realized
    // burgers[i].second is the number of bergers Homer can eat in time of i
  burgers[0].first = true;
  int i;
  for (i = min(m, n); i <= t; i++) {
    if (i >= m && i >= n) {
      if (burgers[i - m].first && burgers[i - n].first)
        burgers[i] = make_pair(true,
          max(burgers[i - m].second + 1, burgers[i - n].second + 1));
      else if (burgers[i - m].first)
        burgers[i] = make_pair(true, burgers[i - m].second + 1);
      else if (burgers[i - n].first)
        burgers[i] = make_pair(true, burgers[i - n].second + 1);
    }
    else if (i >= m) {
      if (burgers[i - m].first)
        burgers[i] = make_pair(true, burgers[i - m].second + 1);
    }
    else {
      if (burgers[i - n].first)
        burgers[i] = make_pair(true, burgers[i - n].second + 1);
    }
  }
  for (i = t; i; i--)
    if (burgers[i].first)
      break;
  return make_pair(burgers[i].second, t - i);
}

int main()
{
#ifdef __ELAPSED_TIME__
  time_t start = clock();
#endif
  int m, n, t;
  while (cin >> m >> n >> t) {
    pair<int, int> result = how_many_burgers_to_eat(m, n, t);
    cout << result.first;
    if (result.second)
      cout << ' ' << result.second;
    cout << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 128 - Software CRC

Accepted date: 2011-12-05
Ranking (as of 2013-07-13): 122 out of 3150
Language: C++

/*
  UVa 128 - Software CRC

  To build using Visual Studio 2008:
    cl -EHsc -O2 software_crc.cpp
*/

#include <cstdio>

unsigned int calculate_crd(const char* line)
{
  unsigned int g = 34943;
  unsigned int remainder = 0;
  for ( ; *line; line++, remainder <<= 8) {
    remainder |= *line;
    remainder %= g;
  }
  remainder <<= 8;
  unsigned int crc = 0;
  if (remainder % g) {
    unsigned int quotient = remainder / g;
    crc = g * (quotient + 1) & 0xffff;
  }
  return crc;
}

int main()
{
  while (true) {
    const int nr_chrs_max = 1024;
    char line[nr_chrs_max + 1];
    gets(line);
    if (line[0] == '#')
      break;
    unsigned int crc = calculate_crd(line);
    printf("%02X %02X\n", (crc & 0xff00) >> 8, crc & 0xff);
  }
  return 0;
}

UVa 106 - Fermat vs. Pythagoras

Accepted date: 2011-12-07
Ranking (as of 2013-07-13): 97 out of 3493
Language: C++

For more information, see:
Pythagorean triple - Wikipedia, the free encyclopedia
Tree of primitive Pythagorean triples - Wikipedia, the free encyclopedia
Formulas for generating Pythagorean triples - Wikipedia, the free encyclpedia

/*
  UVa 106 - Fermat vs. Pythagoras

  To build using Visual Studio 2008:
    cl -EHsc -O2 fermat_vs_pythagoras.cpp
*/

#include <iostream>
#include <vector>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

int calculate_pythagorean_triples(int n, int x, int y, int z,
  vector<bool>& triples)
{
  if (x > n || y > n || z > n)
    return 0;
#ifdef DEBUG
  cerr << x << ' ' << y << ' ' << z << endl;
#endif
  for (int nx = x, ny = y, nz = z; nx <= n && ny <= n && nz <= n;
    nx += x, ny += y, nz += z)
    triples[nx] = triples[ny] = triples[nz] = true;
  const int nr_triples = 3;
  const int matrices[nr_triples][nr_triples][nr_triples] = {
    {{-1, 2, 2}, {-2, 1, 2}, {-2, 2, 3}},
    {{1, 2, 2}, {2, 1, 2}, {2, 2, 3}},
    {{1, -2, 2}, {2, -1, 2}, {2, -2, 3}}
  };
  int nr_pt = 0;
  for (int i = 0; i < nr_triples; i++) {
    int cx = matrices[i][0][0] * x + matrices[i][0][1] * y +
      matrices[i][0][2] * z,
      cy = matrices[i][1][0] * x + matrices[i][1][1] * y +
        matrices[i][1][2] * z,
      cz = matrices[i][2][0] * x + matrices[i][2][1] * y +
        matrices[i][2][2] * z;
    nr_pt += calculate_pythagorean_triples(n, cx, cy, cz, triples);
  }
  return nr_pt + 1;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int n;
  while (cin >> n) {
    if (n < 5)
      cout << 0 << ' ' << n << endl;
    else {
      vector<bool> triples(n + 1, false);
      int nr_primitive_triples =
        calculate_pythagorean_triples(n, 3, 4, 5, triples);
      int nr_not_triples = 0;
      for (int i = 1; i <= n; i++)
        if (!triples[i])
          nr_not_triples++;
      cout << nr_primitive_triples << ' ' << nr_not_triples << endl;
    }
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 10717 - Mint

Accepted date: 2011-12-15
Ranking (as of 2013-07-13): 186 out of 793
Language: C++

/*
  UVa 10717 - Mint

  To build using Visual Studio 2008:
    cl -EHsc -O2 mint.cpp
*/

#include <iostream>
#include <vector>
#include <set>
#include <limits>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

/*
  lcm(a, b) = (a * b) / gcd(a, b)
  lcm(a, b, c) = lcm(a, lcm(b, c))
  lcm(a, b, c, d) = lcm(a, lcm(b, c, d))
*/

long long calculate_gcd(long long a, long long b)
{
  if (a < b)
    return calculate_gcd(b, a);
  if (!b)
    return a;
  else
    return calculate_gcd(b, a % b);
}

long long calculate_lcm(long long a, long long b)
{
    return (a * b) / calculate_gcd(a, b);
}

void calculate_lcms(int n, const vector<int>& coins, set<long long>& lcms)
{
  // C(50, 4) = 50! / {(50 - 4)!4!} = (50 * 49 * 48 * 47) / (4 * 3 * 2 * 1) = 
  //   50 * 49 * 2 * 47 = 230,300
  for (int i = 0; i < n - 3; i++)
    for (int j = i + 1; j < n - 2; j++) {
      long long lcm_i_j = calculate_lcm(coins[i], coins[j]);
      for (int k = j + 1; k < n - 1; k++) {
        long long lcm_i_j_k = calculate_lcm(lcm_i_j, coins[k]);
        for (int l = k + 1; l < n; l++)
          lcms.insert(calculate_lcm(lcm_i_j_k, coins[l]));
      }
    }
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  while (true) {
    int n, t;
    cin >> n >> t;
    if (!n && !t)
      break;
    vector<int> coins(n), tables(t);
    for (int i = 0; i < n; i++)
      cin >> coins[i];
    for (int i = 0; i < t; i++)
      cin >> tables[i];
    set<long long> lcms;
    calculate_lcms(n, coins, lcms);
    for (int i = 0; i < t; i++) {
      int table = tables[i];
      long long not_exceeding = numeric_limits<long long>::min(),
        not_less_than = numeric_limits<long long>::max();
      for (set<long long>::const_iterator j = lcms.begin(), e = lcms.end();
        j != e; ++j) {
        long long lcm = *j;
        long long ne = (table / lcm) * lcm;
        if (ne == table) {
          not_exceeding = not_less_than = table;
          break;
        }
        else {
          not_exceeding = max(not_exceeding, ne);
          not_less_than = min(not_less_than, ne + lcm);
        }
      }
      cout << not_exceeding << ' ' << not_less_than << endl;
    }
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 737 - Gleaming the Cubes

Accepted date: 2013-07-11
Ranking (as of 2013-07-11): 177 out of 860
Language: C++

/*
  UVa 737 - Gleaming the Cubes

  To build using Visual Studio 2010:
    cl -EHsc -O2 UVa_737_Gleaming_the_Cubes.cpp
*/

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

bool get_overlapped_range(const pair<int, int>& i, const pair<int, int>& j,
  pair<int, int>& k)
{
  k.first = max(i.first, j.first);
  k.second = min(i.second, j.second);
  return (k.first < k.second) ? true : false;
}

int main()
{
  while (true) {
    int n;
    cin >> n;
    if (!n)
      break;
    int d;
    pair<int, int> px, py, pz, cx, cy, cz, nx, ny, nz;
    cin >> px.first >> py.first >> pz.first >> d;
    px.second = px.first + d;
    py.second = py.first + d;
    pz.second = pz.first + d;
    bool intersection = true;
    while (--n) {
      cin >> cx.first >> cy.first >> cz.first >> d;
      if (intersection) {
        cx.second = cx.first + d;
        cy.second = cy.first + d;
        cz.second = cz.first + d;
        if (get_overlapped_range(px, cx, nx) &&
          get_overlapped_range(py, cy, ny) && get_overlapped_range(pz, cz, nz)) {
          px = nx; py = ny; pz = nz;
        }
        else
          intersection = false;
      }
    }
    if (intersection)
      cout << (px.second - px.first) *
        (py.second - py.first) * (pz.second - pz.first) << endl;
    else
      cout << 0 << endl;
  }
  return 0;
}