UVa 760 - DNA Sequencing

Accepted date: 2016-02-14
Run Time: 0.000
Ranking (as of 2016-02-14): 26 out of 870
Language: C++

/*
  UVa 760 - DNA Sequencing

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

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

const int nr_chars_max = 300;

int lengths[nr_chars_max][nr_chars_max], indices[nr_chars_max];
char lcss[nr_chars_max][nr_chars_max + 1];

int compare_string(const void* i,const void* j)
{
  return strcmp(reinterpret_cast<const char*>(i),
    reinterpret_cast<const char*>(j));
}

int main()
{
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  while (true) {
    gets(s);
    gets(t);
    int m = strlen(s), n = strlen(t), longest = 0, nr_lcss;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        if (s[i] == t[j]) {
          if (i == 0 || j == 0)
            lengths[i][j] = 1;
          else
            lengths[i][j] = lengths[i - 1][j - 1] + 1;
          if (lengths[i][j] > longest) {
            longest = lengths[i][j];
            nr_lcss = 1;
            indices[0] = i;
          }
          else {
            if (lengths[i][j] == longest)
              indices[nr_lcss++] = i;
          }
        }
        else
          lengths[i][j] = 0;
      }
    if (longest) {
      for (int i = 0; i < nr_lcss; i++) {
        strncpy(lcss[i], s + indices[i] - longest + 1, longest);
        lcss[i][longest] = '\0';
      }
      qsort(lcss, nr_lcss, nr_chars_max + 1, compare_string);
      for (int i = 0, j = 0; i < nr_lcss; i++) {
        if (i) {
          if (strcmp(lcss[j], lcss[i])) {
            j = i;
            puts(lcss[i]);
          }
        }
        else
          puts(lcss[i]);
      }
    }
    else
      puts("No common sequence.");
    if (!gets(s))
      break;
    putchar('\n');
  }
  return 0;
}

UVa 11048 - Automatic Correction of Misspellings

Accepted date: 2016-02-13
Run Time: 0.066
Ranking (as of 2016-02-13): 48 out of 435
Language: C++

/*
  UVa 11048 - Automatic Correction of Misspellings

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

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

const int nr_words_max = 10000, nr_chars_max = 25;
char words[nr_words_max + 1][nr_chars_max + 1],
  sorted_words[nr_words_max + 1][nr_chars_max + 1];

int compare_word(const void* i, const void* j)
{
  return strcmp(reinterpret_cast<const char*>(i),
    reinterpret_cast<const char*>(j));
}

int correct_or_misspelling(const char* w, const char* s)
{
  while (*w && *s && *w == *s)
    w++, s++;
  if (!*w && !*s)
    return 1; // correct
  else if (!strcmp(w + 1, s) || !strcmp(w, s + 1) || !strcmp(w + 1, s + 1))
    return 0;
  else if (*(w + 1) == *s && *w == *(s + 1) && !strcmp(w + 2, s + 2))
    return 0;
  else
    return -1;
}

int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", words[i]);
    strcpy(sorted_words[i], words[i]);
  }
  qsort(sorted_words, n, nr_chars_max + 1, compare_word);
  int q;
  scanf("%d", &q);
  while (q--) {
    char s[nr_chars_max + 1];
    scanf("%s", s);
    if (bsearch(s, sorted_words, n, nr_chars_max + 1, compare_word))
      printf("%s is correct\n", s);
    else {
      int misspelling = -1;
      for (int i = 0; i < n; i++)
        if (correct_or_misspelling(words[i], s) == 0) {
          misspelling = i;
          break;
        }
      if (misspelling != -1)
        printf("%s is a misspelling of %s\n", s, words[misspelling]);
      else
        printf("%s is unknown\n", s);
    }
  }
  return 0;
}

UVa 10466 - How Far?

Accepted date: 2016-02-12
Run Time: 0.023
Ranking (as of 2016-02-12): 15 out of 470
Language: C++

/*
  UVa 10466 - How Far?

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

#include <cstdio>
#include <cmath>

int main()
{
  const double pi = 2.0 * acos(0.0);
  int n;
  double T;
  while (scanf("%d %lf", &n, &T) != EOF) {
    double angle, x = 0.0, y = 0.0, r, t;
    while (n--) {
      scanf("%lf %lf", &r, &t);
      angle = T * pi * 2.0 / t;
      x += r * cos(angle), y += r * sin(angle);
      printf("%.4lf%c", sqrt(x * x + y * y), ((n) ?  ' ' : '\n'));
    }
  }
  return 0;
}

UVa 10577 - Bounding box

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

/*
  UVa 10577 - Bounding box

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

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

const double pi = 2.0 * acos(0.0);

struct point {
  double x_, y_;
  point() {}
  point(double x, double y) : x_(x), y_(y) {}
};

double square_distance(const point& p, const point& q)
{
  double dx = p.x_ - q.x_, dy = p.y_ - q.y_;
  return dx * dx + dy * dy;
}

point rotate(const point& o, const point& p, double angle)
{
  // rotate p around o by angle
  double dx = p.x_ - o.x_, dy = p.y_ - o.y_;
  return point(o.x_ + dx * cos(angle) - dy * sin(angle),
    o.y_ + dx * sin(angle) + dy * cos(angle));
}

int main()
{
  for (int p = 1; ; p++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    const int nr_points = 3;
    point A, B, C;
    scanf("%lf %lf", &A.x_, &A.y_);
    scanf("%lf %lf", &B.x_, &B.y_);
    scanf("%lf %lf", &C.x_, &C.y_);
    double as = square_distance(B, C), bs = square_distance(C, A),
      cs = square_distance(A, B);
    double ad = bs + cs - as, bd = cs + as - bs, cd = as + bs - cs;
    double ud = as * ad + bs * bd + cs * cd;
    point cc; // circumcenter
    cc.x_ = (as * ad * A.x_ + bs * bd * B.x_ + cs * cd * C.x_) / ud;
    cc.y_ = (as * ad * A.y_ + bs * bd * B.y_ + cs * cd * C.y_) / ud;
    double angle = pi * 2.0 / n;
    double x_min = A.x_, x_max = A.x_, y_min = A.y_, y_max = A.y_;
    for (int i = 1; i < n; i++) {
      point p = rotate(cc, A, angle * i);
      x_min = min(x_min, p.x_), x_max = max(x_max, p.x_);
      y_min = min(y_min, p.y_), y_max = max(y_max, p.y_);
    }
    printf("Polygon %d: %.3lf\n", p, (x_max - x_min) * (y_max - y_min));
  }
  return 0;
}

UVa 11532 - Simple Adjacency Maximization

Accepted date: 2016-02-09
Run Time: 0.000
Ranking (as of 2016-02-09): 47 out of 441
Language: C++

/*
  UVa 11532 - Simple Adjacency Maximization

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

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

int main()
{
  int C, P, Q;
  scanf("%d", &C);
  while (C--) {
    scanf("%d %d", &P, &Q);
    int p = 0, q = 0;
    unsigned long long l = 0, b = 1;
    if (p < P) {
      p++;
      l |= b;
      b <<= 1;
    }
    if (q < Q) {
      q++;
      b <<= 1;
    }
    while (p < P || q < Q) {
      if (p < P) {
        p++;
        l |= b;
        b <<= 1;
      }
      if (p < P) {
        p++;
        l |= b;
        b <<= 1;
      }
      if (q < Q) {
        q++;
        b <<= 1;
      }
    }
    b >>= 1;
    unsigned long long rl = 0, rb = 1;
    for (int i = P + Q - 1; i >= 0; i--, b >>= 1, rb <<= 1)
      if (l & b)
        rl |= rb;
    printf("%llu\n", min(l, rl));
  }
  return 0;
}

UVa 11076 - Add Again

Accepted date: 2016-02-08
Run Time: 0.019
Ranking (as of 2016-02-09): 27 out of 787
Language: C++

/*
  UVa 11076 - Add Again

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

#include <cstdio>
#include <cstring>

const int nr_digits = '9' - '0' + 1, N_max = 12;
int freqs[nr_digits], factorials[N_max + 1];

int main()
{
  factorials[0] = factorials[1] = 1;
  for (int i = 2; i <= N_max; i++)
    factorials[i] = factorials[i - 1] * i;
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    memset(freqs, 0, sizeof(freqs));
    for (int i = 0; i < N; i++) {
      int d;
      scanf("%d", &d);
      freqs[d]++;
    }
    unsigned long long ds = 0;
    for (int i = 1; i < nr_digits; i++)
      if (freqs[i]) {
        int f = factorials[N - 1];
        for (int j = 0; j < nr_digits; j++)
          if (freqs[j]) {
            if (i == j)
              f /= factorials[freqs[j] - 1];
            else
              f /= factorials[freqs[j]];
          }
        ds += i * f;
#ifdef DEBUG
        printf("%d: %d %llu\n", i, i * f, ds);
#endif
      }
    unsigned long long s = 0;
    for (int i = 0; i < N; i++, ds *= 10)
      s += ds;
    printf("%llu\n", s);
  }
  return 0;
}

UVa 10060 - A hole to catch a man

Accepted date: 2016-02-03
Run Time: 0.000
Ranking (as of 2016-02-03): 31 out of 667
Language: C++

/*
  UVa 10060 - A hole to catch a man

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

#include <cstdio>
#include <cmath>

const double pi = 2.0 * acos(0.0);

double get_sheet_volume()
{
  double T, x0, y0;
  scanf("%lf %lf %lf", &T, &x0, &y0);
  double x = x0, y = y0, area = 0.0;
  while (true) {
    double nx, ny;
    scanf("%lf %lf", &nx, &ny);
    area += x * ny - nx * y;
    x = nx, y = ny;
    if (x == x0 && y == y0)
      break;
  }
  return T * fabs(area) / 2.0;
}

int main()
{
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    double sv = 0.0;
    while (N--)
      sv += get_sheet_volume();
    double R, T;
    scanf("%lf %lf", &R, &T);
    double cv = pi * R * R * T;
    printf("%d\n", static_cast<int>(sv / cv));
  }
  return 0;
}