UVa 1592 - Database

Accepted date: 2018-01-09
Run Time: 0.770
Ranking (as of 2018-01-08): 34 out of 521
Language: C++11

/*
  UVa 1592 - Database

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

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

const int n_max = 10000, m_max = 10, nr_chars_max = 81;
char records[n_max][nr_chars_max + 1];
size_t values[n_max][m_max];

struct svalue {
  const char* s_;

  svalue(const char* s) : s_(s) {}

  bool operator<(const svalue& sv) const {return strcmp(s_, sv.s_) < 0;}
  bool operator==(const svalue& sv) const {return !strcmp(s_, sv.s_);}
};

int main()
{
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    while (getchar() != '\n')
      ;
    bool pnf = true;
    int r1, r2, c1, c2;
    if (m == 1) {
      for (int i = 0; i < n; i++)
#ifdef ONLINE_JUDGE
        fgets(records[i], nr_chars_max + 1, stdin);
#else
        gets_s(records[i], nr_chars_max + 1);
#endif
    }
    else {
      map<svalue, size_t> svalues;
      for (int i = 0; i < n; i++) {
#ifdef ONLINE_JUDGE
        fgets(records[i], nr_chars_max + 1, stdin);
#else
        gets_s(records[i], nr_chars_max + 1);
#endif
        char *p = records[i], *q = records[i];
        for (int j = 0; j < m; j++) {
          while (*p && *p != ',')
            p++;
          *p++ ='\0';
          pair<map<svalue, size_t>::iterator, bool> r = 
            svalues.insert(make_pair(svalue(q), svalues.size()));
          values[i][j] = r.first->second;
          q = p;
        }
      }
      for (int j = 0; j < m - 1 && pnf; j++)
        for (int k = j + 1; k < m && pnf; k++) {
          map<pair<size_t, size_t>, int> value_pairs;
          for (int i = 0; i < n && pnf; i++) {
            pair<map<pair<size_t, size_t>, int>::iterator, bool> r = 
              value_pairs.insert(make_pair(make_pair(values[i][j], values[i][k]), i));
            if (!r.second) {
              pnf = false;
              r1 = r.first->second + 1, r2 = i + 1;
              c1 = j + 1, c2 = k + 1;
            }
          }
        }
    }
    if (pnf)
      puts("YES");
    else
      printf("NO\n%d %d\n%d %d\n", r1, r2, c1, c2);
  }
  return 0;
}

UVa 1588 - Kickdown

Accepted date: 2018-01-08
Run Time: 0.000
Ranking (as of 2018-01-08): 658 out of 918
Language: C++11

/*
  UVa 1588 - Kickdown

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

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

int stripe(const char* s, int n, const char* t, int m)
{
  int i, j, l;
  for (i = 0; i < n; i++) {
    l = min(m, n - i);
    for (j = 0; j < l; j++)
      if (s[i + j] == '2' && t[j] == '2')
        break;
    if (j == l)
      return (l == m) ? n : n + m - l;
  }
  return n + m;
}

int main()
{
  const int nr_chars_max = 100;
  char master[nr_chars_max + 1], driven[nr_chars_max + 1];
  while (scanf("%s", master) != EOF) {
    scanf("%s", driven);
    int n = strlen(master), m = strlen(driven);
    int s = 
    printf("%d\n", min(stripe(master, n, driven, m), stripe(driven, m, master, n)));
  }
  return 0;
}

UVa 11487 - Gathering Food

Accepted date: 2018-01-07
Run Time: 0.000
Ranking (as of 2018-01-07): 127 out of 380
Language: C++11

/*
  UVa 11487 - Gathering Food

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

#include <algorithm>
#include <queue>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

#include <algorithm>
#include <queue>
#include <utility>
#include <cstdio>
#include <cctype>
using namespace std;

const int N_max = 10, nr_foods_max = 'Z' - 'A' + 1, modulo = 20437;
const int nr_dirs = 4;
const pair<int, int> dirs[nr_dirs] = {
  make_pair(-1, 0), make_pair(1, 0), make_pair(0, -1), make_pair(0, 1)
};
char grid[N_max][N_max + 1];
int N, nr_foods;
pair<int, int>  food_positions[nr_foods_max];
int shortest_paths[nr_foods_max];
  // shortest_paths[f] is the length of shortest path 
  // from ('A' + f - 1) food to ('A' + f) food
bool visited[N_max][N_max];
int nr_shortest_paths[N_max][N_max][nr_dirs * N_max * N_max];
  // nr_shortest_paths[r][c][l] is the number of shortest paths 
  // from grid[r][c] with the path of l length

int bfs(int f) // calculate the the length of shortest path from ('A' + f - 1) to ('A' + f)
{
  const pair<int, int>& s = food_positions[f - 1], e = food_positions[f];
  memset(visited, 0, sizeof(visited));
  queue< pair<pair<int, int>, int> > q;
  visited[s.first][s.second] = true;
  q.push(make_pair(make_pair(s.first, s.second), 0));
  while (!q.empty()) {
    pair<pair<int, int>, int> p = q.front();
    q.pop();
    if (p.first == e)
      return p.second;
    for (int i = 0; i < nr_dirs; i++) {
      int r = p.first.first + dirs[i].first, c = p.first.second + dirs[i].second;
      if (r >= 0 && r < N && c >= 0 && c < N && grid[r][c] != '#' && !visited[r][c]) {
        if (isupper(grid[r][c])) {
          if (grid[r][c] - 'A' <= f) {
            visited[r][c] = true;
            q.push(make_pair(make_pair(r, c), p.second + 1));
          }
        }
        else {
          visited[r][c] = true;
          q.push(make_pair(make_pair(r, c), p.second + 1));
        }
      }
    }
  }
  return -1; // unreachable
}

int dp(int f, int r, int c, int l)
{
  int& nrsp = nr_shortest_paths[r][c][l];
  if (nrsp != -1)
    return nrsp;
  if (!l)
    nrsp = (r == food_positions[f].first && c == food_positions[f].second) ? 1 : 0;
  else {
    nrsp = 0;
    for (int i = 0; i < nr_dirs; i++) {
      int nr = r + dirs[i].first, nc = c + dirs[i].second;
      if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] != '#') {
        if (isupper(grid[nr][nc])) {
          if (grid[nr][nc] - 'A' <= f)
            nrsp += dp(f, nr, nc, l - 1);
        }
        else
          nrsp += dp(f, nr, nc, l - 1);
      }
    }
  }
  return nrsp;
}

int main()
{
  for (int cn = 1; ; cn++) {
    scanf("%d", &N);
    if (!N)
      break;
    nr_foods = 0;
    for (int r = 0; r < N; r++) {
      scanf("%s", grid[r]);
      for (int c = 0; c < N; c++) {
        if (isupper(grid[r][c])) {
          food_positions[grid[r][c] - 'A'] = make_pair(r, c);
          nr_foods = max(nr_foods, grid[r][c] - 'A' + 1);
        }
      }
    }
    pair<int, int> result = make_pair(-1, 0);
    if (nr_foods) {
      int f;
      for (f = 1; f < nr_foods; f++)
        if ((shortest_paths[f] = bfs(f)) == -1)
          break;
      if (f == nr_foods) {
        result = make_pair(0, 1);
        for (int f = 1; f < nr_foods; f++) {
          result.first += shortest_paths[f];
          memset(nr_shortest_paths, -1, sizeof(nr_shortest_paths));
          result.second *= dp(f, food_positions[f - 1].first, food_positions[f - 1].second, shortest_paths[f]);
          result.second %= modulo;
#ifdef DEBUG
          printf("%c: %d %d\n", 'A' + f, result.first, result.second);
#endif
        }
      }
    }
    printf("Case %d: ", cn);
    if (result.first != -1)
      printf("%d %d\n", result.first, result.second);
    else
      puts("Impossible");
  }
  return 0;
}

UVa 11615 - Family Tree

Accepted date: 2018-01-02
Run Time: 0.000
Ranking (as of 2018-01-02): 92 out of 383
Language: C++11

/*
  UVa 11615 - Family Tree

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

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

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    double A, B;
    scanf("%d %lf %lf", &N, &A, &B);
    int n = (1 << N) - 1;
    int m = static_cast<int>(max(log2(A), log2(B)));
    n -= (1 << (N - m)) - 2;
    printf("%d\n", n);
  }
  return 0;
}

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