UVa 11488 - Hyper Prefix Sets

Accepted date: 2017-03-30
Run Time: 0.110
Ranking (as of 2017-03-30): 64 out of 555
Language: C++

Used trie.
During the construction of trie, counted the number of occurrences of each trie node and also calculated the goodness for the node.

/*
  UVa 11488 - Hyper Prefix Sets

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

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

const int nr_letters = '1' - '0' + 1, nr_chars_max = 200;

struct trie_node {
  static int max_goodness;

  int ctr_;
  trie_node* children_[nr_letters];

  trie_node() : ctr_(0) {
    memset(children_, 0, sizeof(children_));
  }
  ~trie_node() {
    for (int i = 0; i < nr_letters; i++)
      delete children_[i];
  }
  void insert(const char* s);
  void calculate_goodness(int length);
};

int trie_node::max_goodness;

void trie_node::insert(const char* s)
{
  trie_node* p = this;
  for (int i = 0, length = strlen(s); i < length; i++) {
    int j = s[i] - '0';
    if (!p->children_[j])
      p->children_[j] = new trie_node();
    p = p->children_[j];
    p->ctr_++;
    max_goodness = max(max_goodness, (i + 1) * p->ctr_);
  }
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    trie_node::max_goodness = 0;
    trie_node* root = new trie_node();
    while (n--) {
      char s[nr_chars_max + 1];
      scanf("%s", s);
      root->insert(s);
    }
    printf("%d\n", trie_node::max_goodness);
    delete root;
  }
  return 0;
}

UVa 298 - Race Tracks

Accepted date: 2017-03-24
Run Time: 0.050
Ranking (as of 2017-03-24): 74 out of 369
Language: C++

/*
  UVa 298 - Race Tracks

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

#include <queue>
#include <limits>
#include <cstdio>
using namespace std;

const int infinite = numeric_limits<int>::max();
const int X_max = 30, Y_max = 30, v_min = -3, v_max = 3, vc_min = -1, vc_max = 1;
const int nr_vs = v_max - v_min + 1;

int nr_hops[X_max][Y_max][nr_vs][nr_vs];
  // nr_hops[x][y][vx - v_min][vy - v_min] is the number of hops at (x, y) 
  // with the velocity of (vx, vy)

bool obstacles[X_max][Y_max]; // obstacles[x][y] is true if there is an obstacle at (x, y)

struct path {
  int x_, y_, vx_, vy_, nr_;
  path(int x, int y, int vx, int vy, int nr) : x_(x), y_(y), vx_(vx), vy_(vy), nr_(nr) {}
};

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int X, Y;
    scanf("%d %d", &X, &Y);
    for (int i = 0; i < X; i++)
      for (int j = 0; j < Y; j++) {
        obstacles[i][j] = false;
        for (int vi = 0; vi < nr_vs; vi++)
          for (int vj = 0; vj < nr_vs; vj++)
            nr_hops[i][j][vi][vj] = infinite;
      }
    int sx, sy, fx, fy;
    scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
    int P;
    scanf("%d", &P);
    while (P--) {
      int x1, x2, y1, y2;
      scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
      for (int i = x1; i <= x2; i++)
        for (int j = y1; j <= y2; j++)
          obstacles[i][j] = true;
    }
    queue<path> q;
    nr_hops[sx][sy][-v_min][-v_min] = 0;
    q.push(path(sx, sy, -v_min, -v_min, 0));
    while (!q.empty()) {
      path p = q.front();
      q.pop();
#ifdef DEBUG
      printf("(%d, %d) with v(%d, %d): %d\n",
        p.x_, p.y_, p.vx_ + v_min, p.vy_ + v_min, p.nr_);
#endif
      int nr = p.nr_ + 1;
      for (int vcx = vc_min; vcx <= vc_max; vcx++) {
        int vx = p.vx_ + v_min + vcx;
        if (vx < v_min || vx > v_max)
          continue;
        int x = p.x_ + vx;
        if (x < 0 || x >= X)
          continue;
        for (int vcy = vc_min; vcy <= vc_max; vcy++) {
          int vy = p.vy_ + v_min + vcy;
          if (vy < v_min || vy > v_max)
            continue;
          int y = p.y_ + vy;
          if (y < 0 || y >= Y || obstacles[x][y])
            continue;
          if (nr_hops[x][y][vx - v_min][vy - v_min] <= nr)
            continue;
#ifdef DEBUG
      printf("  (%d, %d) with v(%d, %d): %d\n",
        x, y, vx + v_min, vy + v_min, nr);
#endif
          nr_hops[x][y][vx - v_min][vy - v_min] = nr;
          q.push(path(x, y, vx - v_min, vy - v_min, nr));
        }
      }
    }
    int nr = infinite;
    for (int vi = 0; vi < nr_vs; vi++)
      for (int vj = 0; vj < nr_vs; vj++)
        if (nr_hops[fx][fy][vi][vj] < nr)
          nr = nr_hops[fx][fy][vi][vj];
    if (nr < infinite)
      printf("Optimal solution takes %d hops.\n", nr);
    else
      puts("No solution.");
  }
  return 0;
}

UVa 1600 - Patrol Robot

Accepted date: 2017-03-21
Run Time: 0.000
Ranking (as of 2017-03-21): 211 out of 369
Language: C++

/*
  UVa 1600 - Patrol Robot

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

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

const int infinite = numeric_limits<int>::max();
const int m_max = 20, n_max = 20, k_max = 20;

const int nr_dirs = 4;
const int dirs[nr_dirs][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int obstacles[m_max][n_max];
  // obstacles[i][j] is 1 if there is an obstacle at cell(i, j), 0 otherwise
int nr_moves[m_max][n_max][k_max + 1];
  // nr_moves[i][j][k] is the minimum number of moves from (0, 0) to (i, j) 
  // with the turbo mode used for k cells

struct path {
  int i_, j_, k_, nr_;
  path(int i, int j, int k, int nr) : i_(i), j_(j), k_(k), nr_(nr) {}
};

int main()
{
  int ns;
  scanf("%d", &ns);
  while (ns--) {
    int m, n, k;
    scanf("%d %d", &m, &n);
    scanf("%d", &k);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        scanf("%d", &obstacles[i][j]);
        for (int l = 0; l <= k; l++)
          nr_moves[i][j][l] = infinite;
      }
    queue<path> q;
    nr_moves[0][0][0] = 0;
    q.push(path(0, 0, 0, nr_moves[0][0][0]));
    while (!q.empty()) {
      path p = q.front(); q.pop();
#ifdef DEBUG
      printf("[%d][%d][%d]: %d\n", p.i_, p.j_, p.k_, p.nr_);
#endif
      for (int d = 0; d < nr_dirs; d++) {
        int i = p.i_ + dirs[d][0], j = p.j_ + dirs[d][1], l = p.k_;
        if (i < 0 || i >= m || j < 0 || j >= n)
          continue;
        if (obstacles[i][j]) {
          if (l + 1 <= k && p.nr_ + 1 < nr_moves[i][j][l + 1]) {
            nr_moves[i][j][l + 1] = p.nr_ + 1;
            q.push(path(i, j, l + 1, nr_moves[i][j][l + 1]));
          }
        }
        else {
          if (p.nr_ + 1 < nr_moves[i][j][0]) {
            nr_moves[i][j][0] = p.nr_ + 1;
            q.push(path(i, j, 0, nr_moves[i][j][0]));
          }
        }
      }
    }
    int nr = infinite;
    for (int l = 0; l <= k; l++)
      if (nr_moves[m - 1][n - 1][l] < nr)
        nr = nr_moves[m - 1][n - 1][l];
    printf("%d\n", (nr < infinite) ? nr : -1);
  }
  return 0;
}

UVa 12893 - Count It

Accepted date: 2017-03-21
Run Time: 0.000
Ranking (as of 2017-03-21): 133 out of 364
Language: C++

/*
  UVa 12893 - Count It

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

#include <cstdio>

long long count_it(long long n)
{
  if (!n)
    return 0;
  long long cn = count_it(n / 2);
  if (n & 1)
    cn++;
  return cn;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    long long n;
    scanf("%lld", &n);
    printf("%lld\n", count_it(n));
  }
  return 0;
}

UVa 210 - Concurrency Simulator

Accepted date: 2017-03-21
Run Time: 0.260
Ranking (as of 2017-03-21): 211 out of 370
Language: C++

/*
  UVa 210 - Concurrency Simulator

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

#include <iostream>
#include <string>
#include <sstream>
#include <deque>
#include <cstring>
using namespace std;

const int nr_programs_max = 10, nr_statements_max = 26;

enum {st_assignment, st_output, st_lock, st_unlock, st_end};
const int nr_statement_types = st_end - st_assignment + 1;

struct statement {
  int type_;
  int variable_, value_;
};

struct program {
  int current_; // current statement
  int remaining_; // number of remaining statements
  statement statements_[nr_statements_max];
} programs[nr_programs_max];

const int nr_variables = 'z' - 'a' + 1;
int values[nr_variables];
int nr_programs, execution_times[nr_statement_types], quantum;

deque<int> ready_queue, blocked_queue;

int main()
{
  string s;
  getline(cin, s);
  istringstream iss(s);
  int nr_cases;
  iss >> nr_cases;
  iss.clear();
  while (nr_cases--) {
    getline(cin, s); // a blank line
    getline(cin, s);
    iss.str(s);
    iss >> nr_programs;
    for (int i = 0; i < nr_statement_types; i++)
      iss >> execution_times[i];
    iss >> quantum;
    iss.clear();
    memset(values, 0, sizeof(values));
    for (int i = 0; i < nr_programs; i++) {
      program& p = programs[i];
      p.current_ = p.remaining_ = 0;
      do {
        getline(cin, s);
        iss.str(s);
        string t, u;
        iss >> t;
        statement& st = p.statements_[p.remaining_++];
        if (t == "print") {
          iss >> u;
          st.type_ = st_output, st.variable_ = u[0] - 'a';
        }
        else if (t == "lock")
          st.type_ = st_lock;
        else if (t == "unlock")
          st.type_ = st_unlock;
        else if (t == "end")
          st.type_ = st_end;
        else {
          st.type_ = st_assignment, st.variable_ = t[0] - 'a';
          iss >> u >> st.value_;
        }
        iss.clear();
      } while (p.statements_[p.remaining_ - 1].type_ != st_end);
#ifdef DEBUG
      cout << i << ": " << p.remaining_ << " stateemtns\n";
#endif
      ready_queue.push_back(i);
    }
    bool locked = false;
    while (!ready_queue.empty()) {
      int i = ready_queue.front();
      ready_queue.pop_front();
      program& p = programs[i];
      int q = quantum;
      bool blocked = false;
      do {
        statement& st = p.statements_[p.current_];
        q -= execution_times[st.type_];
        switch (st.type_) {
        case st_assignment:
          values[st.variable_] = st.value_;
          p.current_++, p.remaining_--;
          break;
        case st_output:
          cout << i + 1 << ": " << values[st.variable_] << endl;
          p.current_++, p.remaining_--;
          break;
        case st_lock:
          if (locked) {
            blocked_queue.push_back(i);
            q = -1, blocked = true;
          }
          else {
            locked = true;
            p.current_++, p.remaining_--;
          }
          break;
        case st_unlock:
          if (!blocked_queue.empty()) {
            int j = blocked_queue.front();
            blocked_queue.pop_front();
            ready_queue.push_front(j);
          }
          locked = false;
          p.current_++, p.remaining_--;
          break;
        case st_end:
          p.current_++, p.remaining_--;
          break;
        }
#ifdef DEBUG
      cout << i + 1 << ": " << p.current_ << ' ' << p.remaining_ << ' ' << q << endl;
#endif
      } while (p.remaining_ && q > 0);
      if (p.remaining_&& !blocked)
        ready_queue.push_back(i);
    }
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 12908 - The book thief

Accepted date: 2017-03-20
Run Time: 0.070
Ranking (as of 2017-03-20): 80 out of 374
Language: C++

/*
  UVa 12908 - The book thief

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

#include <cstdio>
#include <cmath>

int main()
{
  while (true) {
    int s;
    scanf("%d", &s);
    if (!s)
       break;
    int n = static_cast<int>(ceil((-1.0 + sqrt(1.0 + 8.0 * s)) / 2.0));
    if (n * (n + 1) / 2 == s)
      n++;
    printf("%d %d\n", n * (n + 1) / 2 - s, n);
  }
  return 0;
}