UVa 11055 - Homogeneous squares

Accepted date: 2015-09-29
Ranking (as of 2015-09-29): 10 out of 412
Language: C++

/*
  UVa 11055 - Homogeneous squares

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

#include <cstdio>

const int n_max = 1000;
int diffs[n_max];

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    bool homogeneous = true;
    int i, j, k, pk;
    for (j = 0; j < n; j++, pk = k) {
      scanf("%d", &k);
      if (j)
        diffs[j] = k - pk;
    }
    for (i = 1; i < n; i++) {
      for (j = 0; j < n && homogeneous; j++, pk = k) {
        scanf("%d", &k);
        if (j && k - pk != diffs[j])
          homogeneous = false;
      }
      for ( ; j < n; j++)
        scanf("%*d");
    }
    puts((homogeneous) ? "homogeneous" : "not homogeneous");
  }
  return 0;
}

UVa 12027 - Very Big Perfect Squares

Accepted date: 2015-09-25
Ranking (as of 2015-09-25): 8 out of 228
Language: C++

/*
  UVa 12027 - Very Big Perfect Squares

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

#include <cstdio>
#include <cstring>
#include <cmath>

int main()
{
  const int sqrts[] = {
    0,
    1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4,
    4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
  };
  while (true) {
    const int nr_digits_max = 1001;
    char N[nr_digits_max + 1], A[nr_digits_max + 1];
    scanf("%s", N);
    if (N[0] == '0')
      break;
    int nr_digits = strlen(N), nr_zeros = (nr_digits - 1) / 2, n = N[0] - '0';
    if (!(nr_digits & 1)) {
      n *= 10;
      n += N[1] - '0';
    }
    A[0] = sqrts[n] + '0';
    memset(A + 1, '0', nr_zeros);
    A[nr_zeros + 1] = '\0';
    puts(A);
  }
  return 0;
}

UVa 11800 - Determine the Shape

Accepted date: 2015-09-16
Ranking (as of 2015-09-16): 7 out of 471
Language: C++

/*
  UVa 11800 - Determine the Shape

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

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

const int nr_points = 4;

struct point {
  int x_, y_;

  point() {}
  point(int x, int y) : x_(x), y_(y) {}
  point(const point &p) : x_(p.x_), y_(p.y_) {}
} points[nr_points];

bool left_lower(const point& p, const point& q)
{
  if (p.x_ < q.x_)
    return true;
  else if (p.x_ > q.x_)
    return false;
  else if (p.y_ < q.y_)
    return true;
  else
    return false;
}

int cross_product(const point& o, const point& p, const point& q)
{
  return (p.x_ - o.x_) * (q.y_ - o.y_) - (q.x_ - o.x_) * (p.y_ - o.y_);
}

bool ccw(const point& p, const point& q, const point& r)
{
  // see if the point r is to the left of p -> q (or, p - q - r are counter-clorkwise)
  return cross_product(p, q, r) > 0;
}

struct smaller_angle {
  const point& first;

  smaller_angle(const point& _first) : first(_first) {}
  bool operator() (const point& p, const point& q) const {return ccw(first, p, q);}
};

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

bool diagonals_bisect()
{
  return points[0].x_ + points[2].x_ == points[1].x_ + points[3].x_ &&
    points[0].y_ + points[2].y_ == points[1].y_ + points[3].y_;
}

bool diagonals_equal()
{
return square_distance(points[0], points[2]) == square_distance(points[1], points[3]);
}

bool adjacent_sides_equal()
{
return square_distance(points[0], points[1]) == square_distance(points[1], points[2]);
}

bool two_line_seguments_parallel(const point& lp, const point& lq,
  const point& mp, const point& mq)
{
  if (lp.x_ == lq.x_) // vertical line
    return mp.x_ == mq.x_;
  else if (mp.x_ == mq.x_)
    return lp.x_ == lq.x_;
  else
    return (lp.x_ - lq.x_) * (mp.y_ - mq.y_) == (mp.x_ - mq.x_) * (lp.y_ - lq.y_);
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    for (int i = 0; i < nr_points; i++)
      scanf("%d %d", &points[i].x_, &points[i].y_);
    sort(points, points + nr_points, left_lower);
      // sort the points in leftmost-lowest order
    sort(points + 1, points + nr_points, smaller_angle(points[0]));
      // sort the second and later points in increasing angular order
    printf("Case %d: ", t);
    if (diagonals_bisect()) {
      if (adjacent_sides_equal()) {
        if (diagonals_equal())
          puts("Square");
        else
          puts("Rhombus");
      }
      else if (diagonals_equal())
        puts("Rectangle");
      else
        puts("Parallelogram");
    }
    else if (two_line_seguments_parallel(points[0], points[1], points[2], points[3])
      || two_line_seguments_parallel(points[1], points[2], points[3], points[0]))
      puts("Trapezium");
    else
      puts("Ordinary Quadrilateral");
  }
  return 0;
}

UVa 11660 - Look-and-Say sequences

Accepted date: 2015-09-15
Ranking (as of 2015-09-15): 1 out of 275
Language: C++

/*
  UVa 11660 - Look-and-Say sequences

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

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

const int i_max = 1000;

void look_and_say_sequence(const char* s, char* t)
{
  int ctr = 1;
  char d = *s++;
  char* u = t;
  for ( ; *s; s++) {
    if (*s != d) {
      *t++ = ctr + '0';
      *t++ = d;
      if (t - u >= i_max) {
        *t = '\0';
        return;
      }
      ctr = 1;
      d = *s;
    }
    else
      ctr++;
  }
  *t++ = ctr + '0';
  *t++ = d;
  *t = '\0';
}

int main()
{
  while (true) {
    int i, j;
    char s[i_max + 1], t[i_max + 1];
    scanf("%s %d %d", s, &i, &j);
    if (s[0] == '0' && !i && !j)
      break;
    char *p = s, *q = t;
    for (int k = 1; k < i; k++) {
      look_and_say_sequence(p, q);
      swap(p, q);
#ifdef DEBUG
      printf("%s\n", p);
#endif
    }
    printf("%c\n", *(p + j - 1));
  }
  return 0;
}

UVa 11666 - Logarithms

Accepted date: 2015-09-14
Ranking (as of 2015-09-14): 3 out of 433
Language: C++

/*
  UVa 11666 - Logarithms

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

#include <cstdio>
#include <cmath>
#include <climits>

/*
  n / exp(L) = 1 - abs(x) < 1
  if x >= 0
    n / exp(L) = 1 - x < 1
  else if x < 0
    n / exp(L) = 1 - x > 1
  else
    n / exp(L) = 1
*/

int main()
{
  const int L_max = 21 /* static_cast<int>(log(static_cast<double>(INT_MAX))) */;
  double exp_Ls[L_max + 1];
  for (int i = 0; i <= L_max; i++)
    exp_Ls[i] = exp(static_cast<double>(i));
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    for (int L = 0; L <= L_max; L++) {
      double x = 1.0 - n / exp_Ls[L];
      if (fabs(x) < 1.0 &&
        (n < exp_Ls[L] && x > 0.0 || n > exp_Ls[L] && x < 0.0 ||
        n == exp_Ls[L] && x == 0.0)) {
        printf("%d %.8lf\n", L, x);
        break;
      }
    }
  }
  return 0;
}

UVa 11968 - In The Airport

Accepted date: 2015-09-14
Ranking (as of 2015-09-14): 4 out of 226
Language: C++

/*
  UVa 11968 - In The Airport

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

#include <cstdio>
#include <cstdlib>

const int N_max = 1000;
int prices[N_max];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    long long s = 0;
    for (int i = 0; i < N; i++) {
      scanf("%d", &prices[i]);
      s += prices[i];
    }
    int ci = 0, di = M;
    long long n = N, dc = llabs(n * prices[ci] - s), dd = llabs(n * prices[di] - s);
    for (int i = 1; i < M; i++) {
      long long d = llabs(n * prices[i] - s);
      if (d < dc || d == dc && prices[i] < prices[ci]) {
        ci = i;
        dc = d;
      }
    }
    for (int i = M + 1; i < M + K; i++) {
      long long d = llabs(n * prices[i] - s);
      if (d < dd || d == dd && prices[i] < prices[di]) {
        di = i;
        dd = d;
      }
    }
    printf("Case #%d: %d %d\n", t, prices[ci], prices[di]);
  }
  return 0;
}

UVa 12461 - Airplane

Accepted date: 2015-09-03
Ranking (as of 2015-09-03): 63 out of 769
Language: C++

/*
  UVa 12461 - Airplane

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

/*
    probability = 2^(n - 2) / 2^(n - 1) = 1/2

n: 2
  1 2
  2 1 *
                  1/2
n: 3
  1 2 3
  2 1 3
  2 3 1 *
  3 2 1 *
                  2/4

n: 4
  1 2 3 4
  2 1 3 4
  2 3 1 4
  2 3 4 1 *
  2 4 3 1 *
  3 2 1 4
  3 2 4 1 *
  4 2 3 1 *
                  4/8

n: 5
  1 2 3 4 5
  2 1 3 4 5
  2 3 1 4 5
  2 3 4 1 5
  2 3 4 5 1 *
  2 3 5 4 1 *
  2 4 3 1 5
  2 4 3 5 1 *
  2 5 3 4 1 *
  3 2 1 4 5
  3 2 4 1 5
  3 2 4 5 1 *
  3 2 5 4 1 *
  4 2 3 1 5
  4 2 3 5 1 *
  5 2 3 4 1 *
                  8/16

n: 6
  1 2 3 4 5 6
  2 1 3 4 5 6
  2 3 1 4 5 6
  2 3 4 1 5 6
  2 3 4 5 1 6
  2 3 4 5 6 1 *
  2 3 4 6 5 1 *
  2 3 5 4 1 6
  2 3 5 4 6 1 *
  2 3 6 4 5 1 *
  2 4 3 1 5 6
  2 4 3 5 1 6
  2 4 3 5 6 1 *
  2 4 3 6 5 1 *
  2 5 3 4 1 6
  2 5 3 4 6 1 *
  2 6 3 4 5 1 *
  3 2 1 4 5 6
  3 2 4 1 5 6
  3 2 4 5 1 6
  3 2 4 5 6 1 *
  3 2 4 6 5 1 *
  3 2 5 4 1 6
  3 2 5 4 6 1 *
  3 2 6 4 5 1 *
  4 2 3 1 5 6
  4 2 3 5 1 6
  4 2 3 5 6 1 *
  4 2 3 6 5 1 *
  5 2 3 4 1 6
  5 2 3 4 6 1 *
  6 2 3 4 5 1 *
                  16/32

*/

#include <cstdio>

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    puts("1/2");
  }
  return 0;
}