UVa 11326 - Laser Pointer

Accepted date: 2018-01-01
Run Time: 0.020
Ranking (as of 2018-01-02): 12 out of 394
Language: C++11

/*
  UVa 11326 - Laser Pointer

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_11326_Laser_Pointer.cpp
*/

#include <limits>
#include <cstdio>
#include <cmath> // C++11
using namespace std;

int main()
{
  const double pi = 2.0 * acos(0.0);
  const double epsilon = numeric_limits<double>::epsilon();
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    double L, W, theta;
    scanf("%lf %lf %lf", &L, &W, &theta);
    double t = tan(theta * pi / 180.0), r = 1.0;
    if (t > W / L) {
      double x = W / t, y, A;
      int n = static_cast<int>(L / x + epsilon);
      if (n & 1) {
        y = (n + 1) * W - L * t;
        A = (n + 1) * hypot(x, W) - hypot((n + 1) * x - L, y);
      }
      else {
        y = L * t - W * n;
        A = hypot(x, W) * n + hypot(L - n * x, y);
      }
      r = A / hypot(L, y);
    }
    printf("%.3lf\n", r);
  }
  return 0;
}

UVa 11270 - Tiling Dominoes

Accepted date: 2017-12-31
Run Time: 0.000
Ranking (as of 2018-01-02): 25 out of 411
Language: C++

About the formula to calculate the number of tilings, see Domino tiling - Wikipedia.

/*
  UVa 11270 - Tiling Dominoes

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_11270_Tiling_Dominoes.cpp
*/

#include <cstdio>
#include <cmath>

int main()
{
  const double pi = 2.0 * acos(0.0);

  int m, n;
  while (scanf("%d %d", &m, &n) != EOF) {
    double nr_tilings = 1.0;
    for (int j = 1; j <= (m + 1) / 2; j++) {
      double d = cos(pi * j / (m + 1));
      for (int k = 1; k <= (n + 1) / 2; k++) {
        double e = cos(pi * k / (n + 1));
        nr_tilings *= 4.0 * (d * d + e * e);
      }
    }
    printf("%.0lf\n", nr_tilings);
  }
  return 0;
}

UVa 1727 - Counting Weekend Days

Accepted date: 2017-12-30
Run Time: 0.000
Ranking (as of 2018-01-02): 357 out of 429
Language: C++

/*
  UVa 1727 - Counting Weekend Days

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_1727_Counting_Weekend_Days.cpp
*/

#include <cstdio>
#include <cstring>

const int nr_days_of_week = 7, nr_months = 12;

int get_day_of_week(const char* d)
{
  const char* days_of_week[] = {
    "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"
  };

  for (int i = 0; i < nr_days_of_week; i++)
    if (!strcmp(d, days_of_week[i]))
      return i;
  return -1;
}

int get_days_of_month(const char* m)
{
  const struct month {
    const char* name_;
    int nr_days_;
  } months[] = {
    {"JAN", 31}, {"FEB", 28}, {"MAR", 31}, {"APR", 30},
    {"MAY", 31}, {"JUN", 30}, {"JUL", 31}, {"AUG", 31},
    {"SEP", 30}, {"OCT", 31}, {"NOV", 30}, {"DEC", 31}
  };

  for (int i = 0; i < nr_months; i++)
    if (!strcmp(m, months[i].name_))
      return months[i].nr_days_;
  return -1;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    char MTH[3 + 1], DAY[3 + 1];
    scanf("%s %s", MTH, DAY);
    int m = get_days_of_month(MTH), d = get_day_of_week(DAY);
    int nr = (m + d) / nr_days_of_week + (m + d + 1) / nr_days_of_week;
    if (d == 6) // "SAT"
      nr--;
    printf("%d\n", nr);
  }
  return 0;
}

UVa 810 - A Dicey Problem

Accepted date: 2017-12-29
Run Time: 0.010
Ranking (as of 2018-01-02): 58 out of 401
Language: C++

A cumbersome DFS problem.
I wrote the solution while watching a real die in hand.

/*
  UVa 810 - A Dicey Problem

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_810_A_Dicey_Problem.cpp
*/

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

const int nr_sides = 6, nr_chars_max = 20, R_max = 10, C_max = 10;

enum {start, up, down, left, right};

int R, C, sr, sc, maze[R_max][C_max];

struct state {
  int dir_, t_, f_; // direction, top, face
} states[R_max][C_max][nr_sides + 1][nr_sides + 1];
  // states[r][c][t][f].t_ is non-zero 
  // if postion (r, c) has been visited with the die of top t and face f

const struct {
  int l_, r_;
} next_tops[nr_sides + 1][nr_sides + 1] = // next_tops[t][f]
{
  {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}},
  {{0, 0}, {0, 0}, {3, 4}, {5, 2}, {2, 5}, {4, 3}, {0, 0}},
  {{0, 0}, {4, 3}, {0, 0}, {1, 6}, {6, 1}, {0, 0}, {3, 4}},
  {{0, 0}, {2, 5}, {6, 1}, {0, 0}, {0, 0}, {1, 6}, {5, 2}},
  {{0, 0}, {5, 2}, {1, 6}, {0, 0}, {0, 0}, {6, 1}, {2, 5}},
  {{0, 0}, {3, 4}, {0, 0}, {6, 1}, {1, 6}, {0, 0}, {4, 3}},
  {{0, 0}, {0, 0}, {4, 3}, {2, 5}, {5, 2}, {3, 4}, {0, 0}}
};

int nr_paths;
struct {
  int r_, c_;
} paths[R_max * C_max * nr_sides * nr_sides];

int movable(int r, int c, int t)
{
  if (r < 0 || r >= R || c < 0 || c >= C)
    return -1;
  if (maze[r][c] == -1 || maze[r][c] == t)
    return (r == sr && c == sc) ? 1 : 0;
  else
    return -1;
}

void print_path()
{
  printf("  ");
  for (int count = 9; nr_paths; ) {
    printf("(%d,%d)", paths[nr_paths - 1].r_ + 1, paths[nr_paths - 1].c_ + 1);
    if (!--nr_paths)
      putchar('\n');
    else {
      putchar(',');
      if (!--count) {
        printf("\n  ");
        count = 9;
      }
    }
  }
}

bool trace_back_path(int r, int c, int t, int f, int dir)
{
  paths[nr_paths].r_ = r, paths[nr_paths].c_ = c;
  nr_paths++;
  int pr, pc, pt, pf;
  switch (dir) {
  case start:
    print_path();
    return true;
  case up:
    pr = r + 1, pc = c, pt = abs(nr_sides + 1 - f), pf = t;
    break;
  case down:
    pr = r - 1, pc = c, pt = f, pf = abs(nr_sides + 1 - t);
    break;
  case left:
    pr = r, pc = c + 1, pt = next_tops[t][f].r_, pf = f;
    break;
  case right:
    pr = r, pc = c - 1, pt = next_tops[t][f].l_, pf = f;
    break;
  }
  return trace_back_path(pr, pc, pt, pf, states[pr][pc][pt][pf].dir_);
}

bool dfs(int r, int c, int t, int f, int dir)
{
  state& s = states[r][c][t][f];
  if (s.t_)
    return false;
  s.dir_ = dir, s.t_ = t, s.f_ = f;
  int m;
  if ((m = movable(r - 1, c, t)) >= 0) { // up
    if (m)
      return trace_back_path(r - 1, c, f, abs(nr_sides + 1 - t), up);
    if (dfs(r - 1, c, f, abs(nr_sides + 1 - t), up))
      return true;
  }
  if ((m = movable(r + 1, c, t)) >= 0) { // down
    if (m)
      return trace_back_path(r + 1, c, abs(nr_sides + 1 - f), t, down);
    if (dfs(r + 1, c, abs(nr_sides + 1 - f), t, down))
      return true;
  }
  if ((m = movable(r, c - 1, t)) >= 0) { // left
    if (m)
      return trace_back_path(r, c - 1, next_tops[t][f].l_, f, left);
    if (dfs(r, c - 1, next_tops[t][f].l_, f, left))
      return true;
  }
  if ((m = movable(r, c + 1, t)) >= 0) { // right
    if (m)
      return trace_back_path(r, c + 1, next_tops[t][f].r_, f, right);
    if (dfs(r, c + 1, next_tops[t][f].r_, f, right))
      return true;
  }
  return false;
}

int main()
{
  while (true) {
    char name[nr_chars_max + 1];
    scanf("%s", name);
    if (!strcmp(name, "END"))
      break;
    int t, f;
    scanf("%d %d %d %d %d %d", &R, &C, &sr, &sc, &t, &f);
    sr--, sc--;
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++)
        scanf("%d", &maze[r][c]);
    memset(states, 0, sizeof(states));
    nr_paths = 0;
    printf("%s\n", name);
    if (dfs(sr, sc, t, f, start))
      ;
    else
      puts("  No Solution Possible");
  }
  return 0;
}

UVa 12694 - Meeting Room Arrangement

Accepted date: 2017-12-26
Run Time: 0.000
Ranking (as of 2017-12-26): 169 out of 391
Language: C++

A straight-forward interval scheduling problem.

/*
  UVa 12694 - Meeting Room Arrangement

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_12694_Meeting_Room_Arrangement.cpp
*/

/*
  A straight forward interval scheduling problem.
*/

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

const int nr_events_max = 20;

struct event {
  int s_, f_;

  bool operator<(const event& e) const {return f_ < e.f_;}
} events[nr_events_max];

int main()
{
  int n;
  scanf("%d", &n);
  while (n--) {
    int nr_events = 0;
    for ( ; ; nr_events++) {
      scanf("%d %d", &events[nr_events].s_, &events[nr_events].f_);
      if (!events[nr_events].s_ && !events[nr_events].f_)
        break;
    }
    int max_nr_events = 0;
    if (nr_events) {
      sort(events, events + nr_events);
        // sort the events in ascending order of their finish times
      max_nr_events = 1;
      int f = events[0].f_;
      for (int i = 1; i < nr_events; i++)
        if (events[i].s_ >= f) {
          max_nr_events++;
          f = events[i].f_;
        }
    }
    printf("%d\n", max_nr_events);
  }
  return 0;
}

UVa 1231 - ACORN

Accepted date: 2017-07-13
Run Time: 0.260
Ranking (as of 2017-07-13): 114 out of 373
Language: C++

/*
  UVa 1231 - ACORN

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_1231_ACORN.cpp

  This is an accepted solution.
*/

#include <algorithm>
#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int t_max = 2000, h_max = 2000;

int acorns[t_max][h_max + 1];
  // acorns[i][j] is the number of acorns at height j on the i-th tree
int collections[t_max][h_max + 1];
  // collections[i][j] is the max. number of acorns collected at height j on the i-th tree
int max_collections[h_max + 1];
  // max_collections[j] is the max. number of acorns collected at height j

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int c;
  scanf("%d", &c);
  while (c--) {
    int t, h, f;
    scanf("%d %d %d", &t, &h, &f);
    for (int j = 1; j <= h; j++) {
      for (int i = 0; i < t; i++)
        acorns[i][j] = collections[i][j] = 0;
      max_collections[j] = 0;
    }
    for (int i = 0; i < t; i++) {
      int a;
      scanf("%d", &a);
      while (a--) {
        int n;
        scanf("%d", &n);
        acorns[i][n]++;
      }
    }
    for (int j = 1; j <= h; j++)
      for (int i = 0; i < t; i++) {
        collections[i][j] = collections[i][j - 1];
        if (j > f)
          collections[i][j] = max(collections[i][j], max_collections[j - f]);
        collections[i][j] += acorns[i][j];
        max_collections[j] = max(max_collections[j], collections[i][j]);
      }
    printf("%d\n", max_collections[h]);
  }
  scanf("%*d");
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0; // discard "0"
}

UVa 13130 - Cacho

Accepted date: 2017-07-08
Run Time: 0.000
Ranking (as of 2017-07-08): 336 out of 384
Language: C++

/*
  UVa 13130 - Cacho

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_13130_Cacho.cpp
*/

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int a1, a2, a3, a4, a5;
    scanf("%d %d %d %d %d", &a1, &a2, &a3, &a4, &a5);
    puts(
      (a1 == 1 && a2 == 2 && a3 == 3 && a4 == 4 && a5 == 5 ||
      a1 == 2 && a2 == 3 && a3 == 4 && a4 == 5 && a5 == 6) ? "Y" : "N");
  }
  return 0;
}