UVa 11962 - DNA II

Accepted date: 2016-03-14
Run Time: 0.000
Ranking (as of 2016-03-14): 11 out of 250
Language: C++

/*
  UVa 11962 - DNA II

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

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    const int nr_dna_chars = 4, nr_chars_max = 30;
    const char dna_chars[] = {'A', 'C', 'G', 'T'};
    char s[nr_chars_max + 1];
    scanf("%s", s);
    int i, length = 0;
    long long index = 0;
    for (const char* p = s; *p; p++) {
      for (i = 0; /* i < nr_dna_chars */; i++)
        if (*p == dna_chars[i])
          break;
      if (length++)
        index *= 4;
      index += i;
    }
    printf("Case %d: (%d:%lld)\n", t, length, index);
  }
  return 0;
}

UVa 11452 - Dancing the Cheeky-Cheeky

Accepted date: 2016-03-12
Run Time: 0.000
Ranking (as of 2016-03-13): 47 out of 434
Language: C++

/*
  UVa 11452 - Dancing the Cheeky-Cheeky

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

#include <cstdio>
#include <cstring>

const int nr_steps_max = 2000;
char steps[nr_steps_max + 1];

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    scanf("%s", steps);
    int nr_steps = strlen(steps);
    for (int n = nr_steps / 2, m = (nr_steps + 2) / 3; n >= m; n--) {
      int i = nr_steps - 1, j = nr_steps - 1 - n, k = nr_steps - n;
      for ( ; i >= k; i--, j--)
        if (steps[i] != steps[j])
          break;
      if (i < k) {
        if (n < 8) {
          for (i = 0; i < 8; i++)
            putchar(steps[k + i % n]);
          puts("...");
        }
        else {
          steps[k + 8] = '\0';
          printf("%s...\n", &steps[k]);
        }
        break;
      }
    }
  }
  return 0;
}

UVa 1219 - Team Arrangement

Accepted date: 2016-03-09
Run Time: 0.000
Ranking (as of 2016-03-09): 4 out of 56
Language: C++

/*
  UVa 1219 - Team Arrangement

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

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

const int nr_players = 22, nr_chars_max = 31;

struct player {
  int nr_;
  char name_[nr_chars_max + 1];
  char role_;
  int record_;
} players[nr_players];

int nr_Gs, nr_Ds, nr_Ms, nr_Ss, nr_team_Ds, nr_team_Ms, nr_team_Ss;

int Gs[nr_players], Ds[nr_players], Ms[nr_players], Ss[nr_players];

bool read_players()
{
  string s;
  nr_Gs = nr_Ds = nr_Ms = nr_Ss = 0;
  for (int i = 0; i < nr_players; i++) {
    getline(cin, s);
    istringstream iss(s);
    player& p = players[i];
    iss >> p.nr_;
    if (!p.nr_)
      return false;
    iss >> p.name_ >> p.role_;
    switch (p.role_) {
    case 'G':
      Gs[nr_Gs++] = i; break;
    case 'D':
      Ds[nr_Ds++] = i; break;
    case 'M':
      Ms[nr_Ms++] = i; break;
    case 'S':
      Ss[nr_Ss++] = i; break;
    }
    int year1, year2;
    char c;
    p.record_ = 0;
    while (iss >> year1 >> c >> year2)
      p.record_ += year2 - year1 + 1;
#ifdef DEBUG
    cout << p.nr_ << ' ' << p.name_ << ' ' << p.role_ << ' ' << p.record_ << endl;
#endif
  }
  getline(cin, s);
  istringstream iss(s);
  char c;
  iss >> nr_team_Ds >> c >> nr_team_Ms >> c >> nr_team_Ss;
  return true;
}

bool compare_player(int i, int j)
{
  return players[i].nr_ < players[j].nr_;
}

void print_player(int i)
{
  const player& p = players[i];
  cout << p.nr_ << ' ' << p.name_ << ' ' << p.role_ << endl;
}

int main()
{
  while (read_players()) {
    if (!nr_Gs || nr_Ds < nr_team_Ds || nr_Ms < nr_team_Ms || nr_Ss < nr_team_Ss) {
      cout << "IMPOSSIBLE TO ARRANGE\n\n";
      continue;
    }
    sort(Gs, Gs + nr_Gs, compare_player);
    sort(Ds, Ds + nr_Ds, compare_player);
    sort(Ms, Ms + nr_Ms, compare_player);
    sort(Ss, Ss + nr_Ss, compare_player);
    int captain = Gs[0];
    int nr = players[captain].nr_, record = players[captain].record_;
    for (int i = 0; i < nr_team_Ds; i++) {
      int j = Ds[i];
      const player& p = players[j];
      if (p.record_ > record  || p.record_ == record && p.nr_ > nr) {
        captain = j;
        nr = p.nr_, record = p.record_;
      }
    }
    for (int i = 0; i < nr_team_Ms; i++) {
      int j = Ms[i];
      const player& p = players[j];
      if (p.record_ > record  || p.record_ == record && p.nr_ > nr) {
        captain = j;
        nr = p.nr_, record = p.record_;
      }
    }
    for (int i = 0; i < nr_team_Ss; i++) {
      int j = Ss[i];
      const player& p = players[j];
      if (p.record_ > record  || p.record_ == record && p.nr_ > nr) {
        captain = j;
        nr = p.nr_, record = p.record_;
      }
    }
    print_player(captain);
    if (Gs[0] != captain)
      print_player(Gs[0]);
    for (int i = 0; i < nr_team_Ds; i++)
      if (Ds[i] != captain)
        print_player(Ds[i]);
    for (int i = 0; i < nr_team_Ms; i++)
      if (Ms[i] != captain)
        print_player(Ms[i]);
    for (int i = 0; i < nr_team_Ss; i++)
      if (Ss[i] != captain)
        print_player(Ss[i]);
    cout << endl;
  }
  return 0;
}

UVa 330 - Inventory Maintenance

Accepted date: 2016-03-08
Run Time: 0.053
Ranking (as of 2016-03-08): 3 out of 141
Language: C++

/*
  UVa 330 - Inventory Maintenance

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

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

const int nr_chars_max = 15, nr_items_max = 200;

struct item_name {
   char name_[nr_chars_max + 1];

  bool operator<(const item_name& itn) const {return strcmp(name_, itn.name_) < 0;}
  bool operator==(const item_name& itn) const {return !strcmp(name_, itn.name_);}
};

struct item {
  bool deleted_;
  double cost_, price_;
  int in_stock_;
};

int main()
{
  map<item_name, item> items;
  char activity[nr_chars_max + 1];
  item_name itn;
  int quantity;
  double profit = 0.0;
  while (scanf("%s", activity) != EOF && activity[0] != '*') {
    switch (activity[0]) {
    case 'n':
    {
      item it;
      scanf("%s %lf %lf", itn.name_, &it.cost_, &it.price_);
      it.deleted_ = false, it.in_stock_ = 0;
      items[itn] = it;
    }
      break;
    case 'b':
      scanf("%s %d", itn.name_, &quantity);
      items[itn].in_stock_ += quantity;
      break;
    case 's':
    {
      scanf("%s %d", itn.name_, &quantity);
      item& it = items[itn];
      it.in_stock_ -= quantity;
      profit += (it.price_ - it.cost_) * quantity;
    }
      break;
    case 'd':
    {
      scanf("%s", itn.name_);
      item& it = items[itn];
      it.deleted_ = true;
            profit -= it.cost_ * it.in_stock_;
            it.in_stock_ = 0;
    }
      break;
    default: // report
      double total = 0.0;
      puts("                  INVENTORY REPORT");
      puts("Item Name     Buy At      Sell At      On Hand        Value");
      puts("---------     ------      -------      -------        -----");
      for (map<item_name, item>::const_iterator ii = items.begin(), ie = items.end();
        ii != ie; ++ii) {
        const item& it = ii->second;
        if (!it.deleted_) {
          double value = it.cost_ * it.in_stock_;
          printf("%-10s %9.2lf %12.2lf %12d %12.2lf\n",
            ii->first.name_, it.cost_, it.price_, it.in_stock_, value);
          total += value;
        }
      }
      puts("------------------------");
      printf("Total value of inventory                       %12.2lf\n", total);
      printf("Profit since last report                       %12.2lf\n\n", profit);
      profit = 0.0;
      break;
    }
  }
  return 0;
}

UVa 338 - Long Multiplication

Accepted date: 2016-03-02
Run Time: 0.013
Ranking (as of 2016-03-02): 1 out of 410
Language: C++

/*
  UVa 338 - Long Multiplication

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

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

const int nr_digits_max = 10, nr_chars_max = nr_digits_max * 2;

struct line {
  bool zero_;
  int start_, end_;
  char buff_[nr_chars_max + 1];
} x_line, y_line, horizontal_line, lines[nr_digits_max + 1];

void print_line(line& l, int min_start)
{
  memset(l.buff_ + min_start, ' ', l.start_ - min_start);
  puts(&l.buff_[min_start]);
}

void print_horizontal_line(int length, int min_start)
{
  horizontal_line.start_ = nr_chars_max - length;
  horizontal_line.end_ = nr_chars_max;
  memset(&horizontal_line.buff_[horizontal_line.start_], '-', length);
  print_line(horizontal_line, min_start);
}

int main()
{
  long long x, y;
  while (scanf("%lld %lld", &x, &y) == 2) {
    int min_start = nr_chars_max;
    // x
    x_line.zero_ = !x, x_line.start_ = x_line.end_ = nr_chars_max;
    do {
      x_line.buff_[--x_line.start_] = x % 10 + '0';
      x /= 10;
    } while (x);
#ifdef DEBUG
    puts(&x_line.buff_[x_line.start_]);
#endif
    min_start = min(min_start, x_line.start_);
    // y
    y_line.zero_ = !y, y_line.start_ = y_line.end_ = nr_chars_max;
    do {
      y_line.buff_[--y_line.start_] = y % 10 + '0';
      y /= 10;
    } while (y);
#ifdef DEBUG
    puts(&y_line.buff_[y_line.start_]);
#endif
    min_start = min(min_start, y_line.start_);

    if (x_line.zero_ || y_line.zero_) {
      print_line(x_line, min_start);
      print_line(y_line, min_start);
      print_horizontal_line(nr_chars_max - min_start, min_start);
      lines[0].start_ = nr_chars_max - 1, lines[0].end_ = nr_chars_max;
      lines[0].buff_[nr_chars_max - 1] = '0';
      print_line(lines[0], min_start);
      putchar('\n');
      continue;
    }

    int nr_lines = 0, nr_shift = 0;
    for (int i = y_line.end_ - 1; i >= y_line.start_; i--, nr_shift++) {
      line& l = lines[nr_lines];
      l.zero_ = true;
      l.start_ = l.end_ = nr_chars_max - nr_shift;
      l.buff_[l.end_] = '\0';
      int d = 0, dy = y_line.buff_[i] - '0';
      for (int j = x_line.end_ - 1; j >= x_line.start_; j--) {
        d += dy * (x_line.buff_[j] - '0');
        if ((l.buff_[--l.start_] = d % 10 + '0') != '0')
          l.zero_ = false;
        d /= 10;
      }
      while (d) {
        if ((l.buff_[--l.start_] = d % 10 + '0') != '0')
          l.zero_ = false;
        d /= 10;
      }
      if (!l.zero_) {
#ifdef DEBUG
        puts(&l.buff_[l.start_]);
#endif
        nr_lines++;
        min_start = min(min_start, l.start_);
      }
    }
    if (nr_lines > 1) {
      line& l = lines[nr_lines];
      l.start_ = l.end_ = nr_chars_max;
      int d = 0;
      for (int i = nr_chars_max - 1; i >= min_start; i--) {
        for (int j = 0; j < nr_lines; j++)
          if (!lines[j].zero_ && i >= lines[j].start_ && i < lines[j].end_)
            d += lines[j].buff_[i] - '0';
        l.buff_[--l.start_] = d % 10 + '0';
        d /= 10;
      }
      while (d) {
        l.buff_[--l.start_] = d % 10 + '0';
        d /= 10;
      }
#ifdef DEBUG
      puts(&l.buff_[l.start_]);
#endif
      min_start = min(min_start, l.start_);
      nr_lines++;
    }
    print_line(x_line, min_start);
    print_line(y_line, min_start);
    print_horizontal_line(
      max(x_line.end_ - x_line.start_, y_line.end_ - y_line.start_), min_start);
    if (nr_lines > 1) {
      for (int i = 0; i < nr_lines - 1; i++)
        if (!lines[i].zero_)
          print_line(lines[i], min_start);
      print_horizontal_line(nr_chars_max - min_start, min_start);
    }
    else {
      line& l = lines[0];
      memset(&l.buff_[l.end_], '0', nr_chars_max - l.end_);
    }
    print_line(lines[nr_lines - 1], min_start);
    putchar('\n');
  }
  return 0;
}

UVa 890 - Maze (II)

Accepted date: 2016-02-29
Run Time: 0.046
Ranking (as of 2016-02-29): 4 out of 62
Language: C++

/*
  UVa 890 - Maze (II)

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

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

const int M_max = 39, N_max = 39;

int M, N, nr_cells;
char maze[M_max + 1][2 * (N_max + 1)];
bool visited[M_max + 1][N_max + 1];
pair<int, int> cells[M_max * N_max];

inline bool unvisited(int r, int c)
{
  return r >= 0 && r < M && c >= 0 && c < N && !visited[r][c];
}

inline void add_cell(int r, int c)
{
  visited[r][c] = true;
  cells[nr_cells++] = make_pair(r, c);
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &M, &N);
    for (int i = 0; i <= M; i++) {
      int j, k = (i) ? 2 * N : 2 * N - 1;
      for (j = 0; j <= k; j++) {
        if (j & 1)
          maze[i][j] = '_';
        else if (i)
          maze[i][j] = '|';
        else
          maze[i][j] = ' ';
      }
      maze[i][j] = '\0';
    }
#ifdef DEBUG
    for (int i = 0; i <= M; i++)
      puts(maze[i]);
#endif
    nr_cells = 0;
    for (int i = 0; i < M; i++)
      for (int j = 0; j < N; j++)
        visited[i][j] = false;
    int r, c;
    scanf("%d %d", &r, &c);
    r = M - r, c--;
    add_cell(r, c);
    while (true) {
      for ( ; nr_cells; nr_cells--) {
        const pair<int, int>& cell = cells[nr_cells - 1];
        if (unvisited(cell.first - 1, cell.second) ||
          unvisited(cell.first + 1, cell.second) ||
          unvisited(cell.first, cell.second - 1) ||
          unvisited(cell.first, cell.second + 1))
          break;
      }
      if (!nr_cells)
        break;
      const pair<int, int>& cell = cells[nr_cells - 1];
      char command[2];
      scanf("%s", command);
      switch (command[0]) {
      case 'F':
      {
        int n;
        scanf("%d", &n);
        reverse(cells + (n - 1), cells + nr_cells);
      }
        break;
      case 'U':
        r = cell.first - 1, c = cell.second;
        maze[r + 1][c * 2 + 1] = ' ';
        add_cell(r, c);
        break;
      case 'D':
        r = cell.first + 1, c = cell.second;
        maze[r][c * 2 + 1] = ' ';
        add_cell(r, c);
        break;
      case 'L':
        r = cell.first, c = cell.second - 1;
        maze[r + 1][(c + 1) * 2] = ' ';
        add_cell(r, c);
        break;
      case 'R':
        r = cell.first, c = cell.second + 1;
        maze[r + 1][c * 2] = ' ';
        add_cell(r, c);
        break;
      }
#ifdef DEBUG
      for (int i = 0; i <= M; i++)
        puts(maze[i]);
#endif
    }
    for (int i = 0; i <= M; i++)
      puts(maze[i]);
    putchar('\n');
  }
  return 0;
}

UVa 11482 - Building a Triangular Museum

Accepted date: 2016-02-28
Run Time: 0.003
Ranking (as of 2016-02-28): 3 out of 347
Language: C++

/*
  UVa 11482 - Building a Triangular Museum

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

#include <cstdio>

const int M_max = 100, N_max = 100;
char buff[M_max * 2 * N_max + 1];

int main()
{
  for (int x = 1; ; x++) {
    int M, N;
    scanf("%d %d", &M, &N);
    if (!M)
      break;
    printf("Triangular Museum %d\n", x);
    for (int n = 1, indent = M * N - 1; n <= N; n++)
      for (int m = 0, s = 0, t = 2 * (M - 1); m < M; m++, indent--, s += 2, t -= 2) {
        char* p = buff;
        for (int i = 0; i < indent; i++)
          *p++ = ' ';
        for (int i = 0; i < n; i++) {
          *p++ = '/';
          char c = (m < M - 1) ? ' ' : '_';
          for (int j = 0; j < s; j++)
            *p++ = c;
          *p++ = '\\';
          if (i < n - 1)
            for (int j = 0; j < t; j++)
              *p++ = ' ';
        }
        *p = '\0';
        puts(buff);
      }
    putchar('\n');
  }
  return 0;
}