UVa 1209 - Wordfish

Accepted date: 2015-06-18
Ranking (as of 2015-06-18): 3 out of 191
Language: C++

/*
  UVa 1209 - Wordfish

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

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

const int nr_passwords = 21, nr_letters = 26, nr_chars_max = 20;

int main()
{
  char p[nr_chars_max + 1], passwords[nr_passwords][nr_chars_max + 1];
  while (scanf("%s", p) != EOF) {
    int n = strlen(p), i = nr_passwords / 2, psi, pei;
    strcpy(passwords[i], p);
    for (i++; i < nr_passwords && next_permutation(p, p + n); i++)
      strcpy(passwords[i], p);
    pei = i;
    i = nr_passwords / 2;
    strcpy(p, passwords[i]);
    for (i--; i >= 0 && prev_permutation(p, p + n); i--)
      strcpy(passwords[i], p);
    psi = i + 1;
#ifdef DEBUG
    for (i = psi; i < pei; i++)
      printf("%s, ", passwords[i]);
    putchar('\n');
#endif
    int max_min_d = 0, max_min_d_i;
    for (i = psi; i < pei; i++) {
      int min_d = nr_letters;
      char (&pp)[nr_chars_max + 1] = passwords[i];
      for (int j = 0; j < n - 1; j++)
        min_d = min(min_d, abs(pp[j + 1] - pp[j]));
#ifdef DEBUG
      printf("%s %d\n", passwords[i], min_d);
#endif
      if (min_d > max_min_d) {
        max_min_d = min_d;
        max_min_d_i = i;
      }
    }
    printf("%s%d\n", passwords[max_min_d_i], max_min_d);
  }
  return 0;
}

UVa 1262 - Password

Accepted date: 2015-06-17
Ranking (as of 2015-06-17): 2 out of 230
Language: C++

/*
  UVa 1262 - Password

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

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

const int nr_rows = 6, nr_columns = 5;

char first[nr_columns][nr_rows], second[nr_columns][nr_rows],
  common[nr_columns][nr_rows];
int K, lengths[nr_columns];

void read_grid(char grid[nr_columns][nr_rows])
{
  for (int i = 0; i < nr_rows; i++) {
    char s[nr_columns + 1];
    scanf("%s", s);
    for (int j = 0; j < nr_columns; j++)
      grid[j][i] = s[j];
  }
  for (int i = 0; i < nr_columns; i++) {
    char (&g)[nr_rows] = grid[i];
    sort(g, g + nr_rows);
#ifdef DEBUG
    printf("%c%c%c%c%c%c\n", g[0], g[1], g[2], g[3], g[4], g[5]);
#endif
  }
}

bool password(int ci, char s[nr_columns + 1])
{
  if (ci == nr_columns) {
    K--;
    return !K;
  }
  else {
    for (int i = 0; i < lengths[ci]; i++) {
      s[ci] = common[ci][i];
      if (password(ci + 1, s))
        return true;
    }
    return false;
  }
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &K);
    read_grid(first);
    read_grid(second);
    for (int i = 0; i < nr_columns; i++) {
      int l = 0;
      char (&f)[nr_rows] = first[i], (&s)[nr_rows] = second[i],
        (&c)[nr_rows] = common[i];
      for (int fi = 0, si = 0; fi < nr_rows && si < nr_rows; ) {
        char fc = f[fi], sc = s[si];
        if (fc == sc) {
          c[l++] = fc;
          for (fi++; fi < nr_rows && f[fi] == fc; fi++)
            ;
          for (si++; si < nr_rows && s[si] == sc; si++)
            ;
        }
        else if (fc < sc) {
          for (fi++; fi < nr_rows && f[fi] == fc; fi++)
            ;
        }
        else {
          for (si++; si < nr_rows && s[si] == sc; si++)
            ;
        }
      }
      lengths[i] = l;
    }
    int k = 1;
    for (int i = 0; i < nr_columns; i++)
      k *= lengths[i];
    if (k < K)
      puts("NO");
    else {
      char s[nr_columns + 1];
      s[nr_columns] = '\0';
      password(0, s);
      printf("%s\n", s);
    }
  }
  return 0;
}

UVa 11961 - DNA

Accepted date: 2015-06-15
Ranking (as of 2015-06-15): 85 out of 109
Language: C++

/*
  UVa 11961 - DNA

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

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

const int N_max = 15, nr_nucleotides = 4;
const char nucleotides[nr_nucleotides] = {'A', 'C', 'G', 'T'};

struct Dna {
  char s_[N_max + 1];
  bool operator<(const Dna& d) const {return strcmp(s_, d.s_) < 0;}
};

int main()
{
  int T;
  cin >> T;
  while (T--) {
    int N, K;
    cin >> N >> K;
    Dna d;
    cin >> d.s_;
    set<Dna> current;
    current.insert(d);
    while (K--) {
      set<Dna> next;
      for (set<Dna>::const_iterator ci = current.begin(), ce = current.end();
        ci != ce; ++ci) {
        Dna d = *ci;
        for (int i = 0; i < N; i++) {
          char nucleotide = d.s_[i];
          for (int j = 0; j < nr_nucleotides; j++)
            if (nucleotide != nucleotides[j]) {
              d.s_[i] = nucleotides[j];
              if (current.find(d) == ce)
                next.insert(d);
            }
          d.s_[i] = nucleotide;
        }
      }
      current.insert(next.begin(), next.end());
    }
    cout << current.size() << endl;
    for (set<Dna>::const_iterator ci = current.begin(), ce = current.end();
      ci != ce; ++ci)
      cout << ci->s_ << endl;
  }
  return 0;
}

UVa 12249 - Overlapping Scenes

Accepted date: 2015-06-08
Ranking (as of 2015-06-08): 7 out of 107
Language: C++

/*
  UVa 12249 - Overlapping Scenes

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

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

int main()
{
  const int n_max = 6, nr_chars_max = 10;
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int n;
    scanf("%d", &n);
    int scenes[n_max], scene_string_lengths[n_max], min_length = 0;
    char scene_strings[n_max][nr_chars_max + 1],
      merged_string[n_max * nr_chars_max + 1];
    for (int i = 0; i < n; i++) {
      scenes[i] = i;
      scanf("%s", scene_strings[i]);
      scene_string_lengths[i] = strlen(scene_strings[i]);
      min_length += scene_string_lengths[i];
    }
    do {
      strcpy(merged_string, scene_strings[scenes[0]]);
      for (int i = 1; i < n; i++) {
        int j, k = strlen(merged_string);
        for (j = 0; j < k; j++)
          if (!memcmp(&merged_string[j], &scene_strings[scenes[i]][0], k - j))
            break;
        strcat(merged_string, &scene_strings[scenes[i]][k - j]);
      }
#ifdef DEBUG
      printf("%s\n", merged_string);
#endif
      min_length = min(min_length, static_cast<int>(strlen(merged_string)));
    } while (next_permutation(scenes, scenes + n));
    printf("Case %d: %d\n", t, min_length);
  }
  return 0;
}

UVa 868 - Numerical Maze

Accepted date: 2015-06-05
Ranking (as of 2015-06-05): 19 out of 191
Language: C++

/*
  UVa 868 - Numerical Maze

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

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

struct path {
  int i_, j_;
  int next_, last_;

  path() {}
  path(int i, int j, int next, int last) : i_(i), j_(j), next_(next), last_(last) {}
};

void bfs(int r, int c, int cj, const vector< vector<int> >& maze, path& min_path)
{
  min_path.j_ = c;
  queue<path> q;
  q.push(path(0, cj, 1, 2));
  while (!q.empty()) {
    path p = q.front(); q.pop();
    if (p.i_ == r - 1) {
      if (p.j_ < min_path.j_)
        min_path = p;
    }
    else {
      for (int i = 0; i < nr_dirs; i++) {
        int ni = p.i_ + dirs[i].first, nj = p.j_ + dirs[i].second;
        if (ni >= 0 && ni < r && nj >= 0 && nj < c &&
          maze[ni][nj] == p.next_) {
          int next = p.next_, last = p.last_;
          if (next == last) {
            next = 1; last++;
          }
          else
            next++;
          q.push(path(ni, nj, next, last));
        }
      }
    }
  }
}

int main()
{
  int nr_cases;
  cin >> nr_cases;
  while (nr_cases--) {
    int N, M;
    cin >> N >> M;
    vector< vector<int> > maze(N, vector<int>(M));
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        cin >> maze[i][j];
    int min_j;
    path min_path;
    min_path.j_ = M;
    for (int j = 0; j < M; j++)
      if (maze[0][j] == 1) {
        path p;
        bfs(N, M, j, maze, p);
        if (p.j_ < min_path.j_) {
          min_j = j;
          min_path = p;
          break;
        }
      }
    cout << "1 " << min_j + 1 << endl;
    cout << N << ' ' << min_path.j_ + 1 << endl;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 234 - Switching Channels

Accepted date: 2015-06-04
Language: C++

/*
  UVa 234 - Switching Channels

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

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

const int p_max = 8, a_max = 8, il_max = 5;

int programs[p_max];

struct alignment_point {
  int il_, t_;
} alignment_points[a_max];

int main()
{
  for (int ds = 1; ; ds++) {
    int p, a;
    scanf("%d", &p);
    if (!p)
      break;
    for (int i = 0; i < p; i++)
      scanf("%d", &programs[i]);
    scanf("%d", &a);
    int il = 0; // inportance level
    for (int i = 0; i < a; i++) {
      scanf("%d %d", &alignment_points[i].il_, &alignment_points[i].t_);
      il = max(il, alignment_points[i].il_);
    }
    sort(programs, programs + p);
    int min_err = -1, min_programs[p_max], min_miss_times[il_max + 1];
    do {
      int tm = 0, times[p_max + 1], miss_times[il_max + 1], err = 0;
      for (int i = 0; i < p; i++) {
        times[i] = tm;
        tm += programs[i];
      }
      times[p] = tm;
      memset(miss_times, 0, sizeof(miss_times));
      for (int i = 0; i < a; i++) {
        int t = alignment_points[i].t_, il = alignment_points[i].il_,
          mt = numeric_limits<int>::max();
        for (int j = 0; j <= p; j++)
          mt = min(mt, abs(times[j] - t));
        miss_times[il] += mt;
        err += mt;
      }
#ifdef DEBUG
        for (int i = 0; i < p; i++)
          printf("%d%c", programs[i], ((i < p - 1) ? ' ' : ':'));
        putchar(' ');
        for (int i = 1; i <= il; i++)
          printf("%d%c", miss_times[i], ((i < il) ? ' ' : ':'));
        printf(" %d", err);
#endif
      bool better = false;
      if (min_err == -1)
        better = true;
      else {
        for (int i = 1; i <= il; i++) {
          if (miss_times[i] < min_miss_times[i]) {
            better = true; break;
          }
          else if (miss_times[i] > min_miss_times[i])
            break;
        }
      }
#ifdef DEBUG
      puts((better) ? " better" : "");
#endif
      if (better) {
        min_err = err;
        memcpy(min_programs, programs, sizeof(int) * p);
        memcpy(min_miss_times, miss_times, sizeof(int) * (il + 1));
#ifndef DEBUG
        if (!min_err)
          break;
#endif
      }
    } while (next_permutation(programs, programs + p));
    printf("Data set %d\n", ds);
    printf("Order: ");
    for (int i = 0; i < p; i++)
      printf("%d%c", min_programs[i], ((i < p - 1) ? ' ' : '\n'));
    printf("Error: %d\n", min_err);
/*
    printf("Data set %d\n", ds);
    printf("  Order: ");
    for (int i = 0; i < p; i++)
      printf("%d%c", min_programs[i], ((i < p - 1) ? ' ' : '\n'));
    printf("  Error: %d\n", min_err);
*/
  }
  return 0;
}

UVa 830 - Shark

Accepted date: 2015-06-01
Ranking (as of 2015-06-01): 33 out of 160
Language: C++

/*
  UVa 830 - Shark

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

#include <cstdio>
#include <cstring>
#include <cctype>

enum {sardine, mackerel, salmon, grouper, turtle, dolphin, whale, shark};
#ifdef DEBUG
const char* names[] = {"sardine", "mackerel", "salmon", "grouper", "turtle",
  "dolphin", "whale", "shark"};
#endif
const int nr_shapes = shark - sardine + 1;
const int L_max = 64, C_max = 64;
char grid[L_max][C_max + 1];

int clear_shape(int L, int C, int ls, int cs, int w, int c)
{
  int i, j, h = 0;
  for (i = ls; i < L; i++, h++)
    for (j = cs; j < cs + w; j++) {
      if (grid[i][j] != c)
        return h;
      grid[i][j] = '\0';
    }
  return h;
}

int shape(int L, int C, int ls, int cs)
{
  int j, w = 1, h;
  char c = grid[ls][cs];
  for (j = cs + 1; j < C; j++, w++)
    if (grid[ls][j] != c)
      break;
  switch (w) {
  case 1:
    if (ls + 1 < L && cs && cs + 1 < C && grid[ls + 1][cs - 1] == c &&
      grid[ls + 1][cs] == c && grid[ls + 1][cs + 1] == c) {
      grid[ls][cs] = '\0';
      clear_shape(L, C, ls + 1, cs - 1, 3, c);
      return shark;
    }
    else {
      h = clear_shape(L, C, ls, cs, 1, c);
      return (h > 2) ? salmon : ((h == 2) ? mackerel : sardine);
    }
  case 2:
    h = clear_shape(L, C, ls, cs, 2, c);
    return ((h > 2) ? grouper : (h == 2) ? turtle : mackerel);
  case 3:
    h = clear_shape(L, C, ls, cs, 3, c);
    if (h > 3) {
      if (ls + h < L && grid[ls + h][cs + 1] == c) {
        grid[ls + h][cs + 1] = '\0';
        return shark;
      }
      else
        return dolphin;
    }
    else
      return (h == 3) ? turtle : ((h == 2) ? grouper : salmon);
  case 4:
    h = clear_shape(L, C, ls, cs, 4, c);
    if (h > 4)
      return whale;
    else if (h == 3) {
      if (cs && grid[ls + 1][cs - 1] == c) {
        grid[ls + 1][cs - 1] = '\0';
        return shark;
      }
      else if (cs + 4 < C && grid[ls + 1][cs + 4] == c) {
        grid[ls + 1][cs + 4] = '\0';
        return shark;
      }
      else
        return dolphin;
    }
    else
      return (h == 4) ? turtle : ((h == 2) ? grouper : salmon);
  default:
    h = clear_shape(L, C, ls, cs, w, c);
    if (h > 4)
      return turtle;
    else if (h == 3) {
      if (cs && grid[ls + 1][cs - 1] == c) {
        grid[ls + 1][cs - 1] = '\0';
        return shark;
      }
      else if (cs + 4 < C && grid[ls + 1][cs + 4] == c) {
        grid[ls + 1][cs + 4] = '\0';
        return shark;
      }
      else
        return dolphin;
    }
    else
      return (h == 4) ? whale : ((h == 2) ? grouper : salmon);
  }
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int L, C;
    scanf("%d %d", &L, &C);
    for (int i = 0; i < L; i++)
      scanf("%s", grid[i]);
    int shapes[nr_shapes];
    memset(shapes, 0, sizeof(shapes));
    for (int i = 0; i < L; i++)
      for (int j = 0; j < C; j++)
        if (islower(grid[i][j])) {
          int s = shape(L, C, i, j);
#ifdef DEBUG
          printf("(%2d, %2d) %s\n", i, j, names[s]);
#endif
          shapes[s]++;
        }
    for (int i = 0; i < nr_shapes; i++)
      printf("%d%c", shapes[i], ((i < nr_shapes - 1) ? ' ' : '\n'));
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}