UVa 10855 - Rotated square

Accepted date: 2014-07-04
Ranking (as of 2014-07-04): 97 out of 689
Language: C++

/*
  UVa 10855 - Rotated square

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

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

void rotate_square(const vector< vector<char> >& s,
  vector< vector<char> >& t) // rotate clockwise by 90 degrees
{
  size_t n = s.size();
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < n; j++)
      t[i][j] = s[n - j - 1][i];
#ifdef DEBUG
  for (size_t i = 0; i < n; i++)
    printf("%s\n", &t[i][0]);
#endif
}

int count_squares(const vector< vector<char> >&big_square,
  const vector< vector<char> >&small_square)
{
  int count = 0;
  size_t N = big_square.size(), n = small_square.size();
  for (size_t i = 0; i < N - n + 1; i++)
    for (size_t j = 0; j < N - n + 1; j++) {
      size_t k, l;
      for (k = 0; k < n; k++) {
        for (l = 0; l < n; l++)
          if (big_square[i + k][j + l] != small_square[k][l])
            break;
        if (l < n)
          break;
      }
      if (k == n && l == n)
        count++;
    }
  return count;
}

int main()
{
  while (true) {
    int N, n;
    scanf("%d %d", &N, &n);
    if (!N && !n)
      break;
    vector< vector<char> > big_square(N, vector<char>(N + 1)),
      small_square(n, vector<char>(n + 1));
    for (int i = 0; i < N; i++)
      scanf("%s", &big_square[i][0]);
    for (int i = 0; i < n; i++)
      scanf("%s", &small_square[i][0]);
    int counts[4];
    counts[0] = count_squares(big_square, small_square);
    vector< vector<char> > rotated_square(n, vector<char>(n + 1));
    rotate_square(small_square, rotated_square);
    counts[1] = count_squares(big_square, rotated_square);
    rotate_square(rotated_square, small_square);
    counts[2] = count_squares(big_square, small_square);
    rotate_square(small_square, rotated_square);
    counts[3] = count_squares(big_square, rotated_square);
    printf("%d %d %d %d\n", counts[0], counts[1], counts[2], counts[3]);
  }
  return 0;
}

UVa 10017 - The Never Ending Towers of Hanoi

Accepted date: 2014-07-01
Ranking (as of 2014-07-03): 260 out of 654
Language: C++

/*
  UVa 10017 - The Never Ending Towers of Hanoi

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

#include <iostream>
#include <list>
using namespace std;

void print_peg(char p, const list<int>& l)
{
  cout << p << "=>";
  if (!l.empty()) {
    cout << "  ";
    for (list<int>::const_iterator i = l.begin(), e = l.end(); i != e; ++i)
      cout << ' ' << *i;
  }
  cout << endl;
}

void print_pegs(const list<int>& a, const list<int>& b, const list<int>& c)
{
  print_peg('A', a);
  print_peg('B', b);
  print_peg('C', c);
  cout << endl;
}

void move_between_pegs(list<int>& i, list<int>& j)
{
  if (i.empty()) {
    i.push_back(j.back()); j.pop_back();
  }
  else if (j.empty()) {
    j.push_back(i.back()); i.pop_back();
  }
  else if (i.back() > j.back()) {
    i.push_back(j.back()); j.pop_back();
  }
  else {
    j.push_back(i.back()); i.pop_back();
  }
}

void tower_of_hanoi_even_disks(list<int>& a, list<int>& b, list<int>& c, int m)
{
  while (true) {
    if (m--) {
      move_between_pegs(a, b); // make the legal move between pegs A and B
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(a, c); // make the legal move between pegs A and C
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(b, c); // make the legal move between pegs B and C
      print_pegs(a, b, c);
    }
    else
      break;
  }
}

void tower_of_hanoi_odd_disks(list<int>& a, list<int>& b, list<int>& c, int m)
{
  while (true) {
    if (m--) {
      move_between_pegs(a, c); // make the legal move between pegs A and C
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(a, b); // make the legal move between pegs A and B
      print_pegs(a, b, c);
    }
    else
      break;
    if (m--) {
      move_between_pegs(b, c); // make the legal move between pegs C and B
      print_pegs(a, b, c);
    }
    else
      break;
  }
}

int main()
{
  for (int p = 1; ; p++) {
    int n, m;
    cin >> n >> m;
    if (!n && !m)
      break;
    cout << "Problem #" << p << endl << endl;
    list<int> a, b, c;
    for (int i = 1; i <= n; i++)
      a.push_front(i);
    print_pegs(a, b, c);
    if (n & 1)
      tower_of_hanoi_odd_disks(a, b, c, m);
    else
      tower_of_hanoi_even_disks(a, b, c, m);
  }
  return 0;
}

UVa 775 - Hamiltonian Cycle

Accepted date: 2014-06-30
Ranking (as of 2014-07-01): 45 out of 272
Language: C++

/*
  UVa 775 - Hamiltonian Cycle

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

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

const int n_max = 256;

vector<int> edges[n_max + 1];
bool visited[n_max + 1];
int path[n_max + 1];

bool hamiltonian_cycle(int n, int ni, int vi)
{
  if (ni == n) {
    const vector<int>& e = edges[path[ni - 1]];
    for (size_t i = 0; i < e.size(); i++)
      if (e[i] == 1) {
        path[ni] = 1;
        return true;
      }
    return false;
  }
  else {
    const vector<int>& e = edges[vi];
    for (size_t i = 0; i < e.size(); i++)
      if (!visited[e[i]]) {
        path[ni] = e[i];
        visited[e[i]] = true;
        if (hamiltonian_cycle(n, ni + 1, e[i]))
          return true;
        visited[e[i]] = false;
      }
    return false;
  }
}

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    getchar();
    for (int i = 1; i <= n; i++) {
      edges[i].clear();
      visited[i] = false;
    }
    char c;
    while ((c = getchar()) != '%') {
      ungetc(c, stdin);
      int u, v;
      scanf("%d %d", &u, &v);
      edges[u].push_back(v);
      edges[v].push_back(u);
      getchar();
    }
    path[0] = 1;
    visited[1] = true;
    if (hamiltonian_cycle(n, 1, 1)) {
      for (int i = 0; i <= n; i++)
        printf("%d%c", path[i], ((i < n) ? ' ' : '\n'));
    }
    else
      puts("N");
  }
  return 0;
}

UVa 10475 - Help the Leaders

Accepted date: 2014-06-28
Ranking (as of 2014-06-28): 43 out of 302
Language: C++

/*
  UVa 10475 - Help the Leaders

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

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

const int t_max = 16, nr_chars_max = 15;

struct topic {
  int length_;
  char s_[nr_chars_max + 1];
  topic() : length_(0) {}
  topic(const char* s)
    : length_(strlen(s))
  {
    transform(s, s + length_, s_, (int(*)(int))toupper);
    s_[length_] = '\0';
  }
} topics[t_max];

int compare_topic(const void* i, const void* j)
{
  const topic *ti = reinterpret_cast<const topic*>(i),
    *tj = reinterpret_cast<const topic*>(j);
  return (ti->length_ != tj->length_) ?
    tj->length_ - ti->length_ : strcmp(ti->s_, tj->s_);
}

bool prohibited_pairs[t_max][t_max];

void help_leader(int t, int s, int ti, int si, int group[])
{
  if (si == s) {
    for (int i = 0; i < s; i++)
      printf("%s%c", topics[group[i]].s_, (i < s - 1) ? ' ' : '\n');
  }
  else if (t - ti > s - si) {
    for (int i = ti + 1; i < t; i++) {
      int j;
      for (j = 0; j < si; j++)
        if (prohibited_pairs[i][group[j]])
          break;
      if (j == si) {
        group[si] = i;
        help_leader(t, s, i, si + 1, group);
      }
    }
  }
}

int main()
{
  int n;
  scanf("%d", &n);
  for (int sn = 1; sn <= n; sn++) {
    int t, p, s;
    scanf("%d %d %d", &t, &p, &s);
    for (int i = 0; i < t; i++) {
      scanf("%s", topics[i].s_);
      topics[i] = topics[i].s_;
    }
    qsort(topics, t, sizeof(topic), compare_topic);
    for (int i = 0; i < t; i++)
      for (int j = 0; j < t; j++)
        prohibited_pairs[i][j] = false;
    for (int i = 0; i < p; i++) {
      topic ti, tj;
      scanf("%s %s", ti.s_, tj.s_);
      ti = ti.s_; tj = tj.s_;
      int pi = reinterpret_cast<topic*>(
        bsearch(&ti, topics, t, sizeof(topic), compare_topic)) - topics,
        pj = reinterpret_cast<topic*>(
          bsearch(&tj, topics, t, sizeof(topic), compare_topic)) - topics;
      prohibited_pairs[pi][pj] = prohibited_pairs[pj][pi] = true;
    }
    printf("Set %d:\n", sn);
    for (int i = 0; i < t - s + 1; i++) {
      int group[t_max]; // array of topic indices
      group[0] = i;
      help_leader(t, s, i, 1, group);
    }
    putchar('\n');
  }
  return 0;
}

UVa 10460 - Find the Permuted String

Accepted date: 2014-06-27
Ranking (as of 2014-06-28): 450 out of 524
Language: C++

/*
  UVa 10460 - Find the Permuted String

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int i;
    cin >> i;
    i--;
    int n = static_cast<int>(s.length());
    vector<int> indices(n);
    for (int j = n; j; j--) {
      indices[j - 1] = i % j;
      i /= j;
    }
    vector<char> ps;
    for (int j = 0; j < n; j++)
      ps.insert(ps.begin() + indices[j], s[j]);
    for (int i = 0; i < n; i++)
      cout << ps[i];
    cout << endl;
  }
  return 0;
}

UVa 487 - Boggle Blitz

Accepted date: 2014-06-25
Ranking (as of 2014-06-25): 98 out of 352
Language: C++

/*
  UVa 487 - Boggle Blitz

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

#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int n_max = 20, nr_dirs = 8;
const int dirs[nr_dirs][2] = {
  {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}
};
char table[n_max][n_max + 1];

struct word {
  int i_, j_;
  int length_;
  char s_[n_max * n_max + 1];
  word() : i_(-1), j_(-1), length_(0) {}
  word(int i, int j) : i_(i), j_(j), length_(0) {}
  word(const word& w) : i_(w.i_), j_(w.j_), length_(w.length_)
    {memcpy(s_, w.s_, w.length_);}
  word& operator=(const word& w)
    {i_ = w.i_; j_ = w.j_; length_ = w.length_; memcpy(s_, w.s_, w.length_);
    return *this;}

  void push_back(char c) {s_[length_++] = c;}

  bool operator<(const word& w) const {
    return (length_ != w.length_) ? length_ < w.length_ : strcmp(s_, w.s_) < 0;}
};

set<word> words;

void bfs(int n, int si, int sj)
{
  word sw(si, sj);
  sw.push_back(table[si][sj]);
  queue<word> wq;
  wq.push(sw);
  while (!wq.empty()) {
    word w = wq.front(); wq.pop();
    if (w.length_ >= 3) {
      word nw(w);
      nw.push_back('\0');
      words.insert(nw);
    }
    for (int k = 0; k < nr_dirs; k++) {
      int i = w.i_ + dirs[k][0], j = w.j_ + dirs[k][1];
      if (i >= 0 && i < n && j >= 0 && j < n &&
        w.s_[w.length_ - 1] < table[i][j]) {
        word nw(w);
        nw.i_ = i; nw.j_ = j;
        nw.push_back(table[i][j]);
        wq.push(nw);
      }
    }
  }
}

int main()
{
  int nc;
  scanf("%d", &nc);
  while (nc--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%s", table[i]);
    words.clear();
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        bfs(n, i, j);
    for (set<word>::const_iterator i = words.begin(), e = words.end();
      i != e; ++i)
      printf("%s\n", i->s_);
    if (nc)
      putchar('\n');
  }
  return 0;
}

UVa 380 - Call Forwarding

Accepted date: 2014-06-24
Ranking (as of 2014-06-24): 369 out of 547
Language: C++

/*
  UVa 380 - Call Forwarding

  To build using Visucal Studio 2012:
    cl -EHsc UVa_380_Call_Forwarding.cpp
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
using namespace std;

struct call_forwarding {
  int t_; // target
  int st_, et_; // start time, end time

  call_forwarding(int t, int st, int et) : t_(t), st_(st), et_(et) {}
  bool operator<(const call_forwarding& cf) const {return st_ < cf.st_;}
};

struct request {
  bool f_; // true if forwarded
  vector<call_forwarding> forwardings_;
  request() : f_(false) {}
};

int call_forward(int t, int s, map<int, request>& requests)
{
  for (map<int, request>::iterator i = requests.begin(), e = requests.end();
    i != e; ++i)
    i->second.f_ = false;
  while (true) {
    map<int, request>::iterator i = requests.find(s);
    if (i == requests.end()) // forwarding is not registered
      return s;
    else if (i->second.f_) // already has been forwarded
      return 9999;
    else {
      i->second.f_ = true;
      s = -1;
      for (vector<call_forwarding>::const_iterator
        j = i->second.forwardings_.begin(), e = i->second.forwardings_.end();
        j != e; ++j)
        if (t >= j->st_ && t <= j->et_) {
          s = j->t_; break;
        }
      if (s == -1)
        return i->first;
    }
  }
}

int main()
{
  cout << "CALL FORWARDING OUTPUT\n";
  int nr_systems;
  cin >> nr_systems;
  for (int ns = 1; ns <= nr_systems; ns++) {
    map<int, request> requests;
    while (true) {
      int s, t, st, d;
      cin >> s;
      if (!s)
        break;
      cin >> st >> d >> t;
      pair<map<int, request>::iterator, bool> result =
        requests.insert(make_pair(s, request()));
      result.first->second.forwardings_.push_back(
        call_forwarding(t, st, st + d));
    }
    cout << "SYSTEM " << ns << endl;
    while (true) {
      int t, s;
      cin >> t;
      if (t == 9000)
        break;
      cin >> s;
      cout << "AT " << setfill('0') << setw(4) <<
        t << " CALL TO " << setw(4) << s << " RINGS " <<
        setw(4) << call_forward(t, s, requests) << endl;
    }
  }
  cout << "END OF OUTPUT\n";
  return 0;
}