UVa 276 - Egyptian Multiplication

Accepted date: 2016-03-31
Run Time: 0.000
Ranking (as of 2016-03-31): 12 out of 385
Language: C++

/*
  UVa 276 - Egyptian Multiplication

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

#include <cstdio>

const int nr_chars_max = 5 * (9 + 1);

int read_egyptian_number(const char* s)
{
  static const int values[] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1000, 100, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0,
    0, 0, 10000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0
  };
  int n = 0;
  for (; *s; s++)
    n += values[*s];
  return n;
}

char* print_egyptian_number(int n, char* s)
{
  static const char* symbols = "r89n|";
  const char* ps = symbols;
  char* p = s + nr_chars_max;
  *--p = '\0';
  bool first_printed = false;
  for (int d = 10000; d; d /= 10, ps++) {
    bool printed = false;
    while (n >= d) {
      if (!printed) {
        printed = true;
        if (first_printed)
          *--p = ' ';
        else
          first_printed = true;
      }
      *--p = *ps;
      n -= d;
    }
  }
  return p;
}

int main()
{
  char s[nr_chars_max + 1], t[nr_chars_max + 1], u[nr_chars_max * 2 + 1];
  while (gets(s) && s[0]) {
    int a = read_egyptian_number(s), b = read_egyptian_number(gets(s));
    long long ia = a;
    for (int i = 1, ib = b; ib; i <<= 1, ia <<= 1, ib >>= 1) {
      char* p = print_egyptian_number(i, s);
      sprintf(u, "%-34s%s", p, print_egyptian_number(static_cast<int>(ia % 100000), t));
      if (ib & 1)
        u[s + nr_chars_max - p] = '*';
      puts(u);
    }
    printf("The solution is: %s\n",
      print_egyptian_number(static_cast<int>(static_cast<long long>(a) * b % 100000), s));
  }
  return 0;
}

UVa 11327 - Enumerating Rational Numbers

Accepted date: 2016-03-25
Run Time: 0.049
Ranking (as of 2016-03-25): 16 out of 573
Language: C++

/*
  UVa 11327 - Enumerating Rational Numbers

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

#include <algorithm>
#include <iterator>
#include <cstdio>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int n_max = 200000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int phis[n_max + 1]; // phis[i] is Euler's totient (or phi) function's values, i.e., 
  // number the positive integers up to a given number i that are relatively prime to i
long long sum_of_phis[n_max + 1];
  // sum_of_phits[i] is the sum of phis[j] where j is from 0 up to i

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

int gcd(int x, int y)
{
  if (x < y)
    return gcd(y, x);
  else
      return y == 0 ? x : gcd(y, x % y);
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  sieve_of_eratosthenes();
  phis[0] = 1;
  for (int i = 1; i <= n_max; i++)
    phis[i] = i;
  for (int i = 1; i <= n_max; i++)
        if (!not_primes[i])
      for (int j = i; j <= n_max; j += i)
        phis[j] -= phis[j] / i;
  sum_of_phis[0] = 1;
  for (int i = 1; i <= n_max; i++)
    sum_of_phis[i] = sum_of_phis[i - 1] + phis[i];
#ifdef DEBUG
  printf("%lld\n", sum_of_phis[n_max]);
#endif
  while (true) {
    long long k;
    scanf("%lld", &k);
    if (!k)
      break;
    int d = distance(sum_of_phis, lower_bound(sum_of_phis, sum_of_phis + n_max, k)), n = 0;
    if (d) {
      k -= sum_of_phis[d - 1];
      for (n++; ; n++)
        if (gcd(n, d) == 1 && !--k)
          break;
    }
    else
      d = 1;
    printf("%d/%d\n", n, d);
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 12155 - ASCII Diamond

Accepted date: 2016-03-22
Run Time: 0.006
Ranking (as of 2016-03-22): 5 out of 114
Language: C++

/*
  UVa 12155 - ASCII Diamond

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

const int nr_letters = 'z' - 'a' + 1, col_max = 20000;
char buff[col_max + 2];

#include <cstdio>
#include <cstdlib>

int main()
{
  for (int serial = 1; ; serial++) {
    int N, row1, col1, row2, col2;
    scanf("%d %d %d %d %d", &N, &row1, &col1, &row2, &col2);
    if (!N)
      break;
    printf("Case %d:\n", serial);
    int size = 2 * N - 1, center = N - 1;
    buff[col2 - col1 + 1] = '\0';
    for (int r = row1; r <= row2; r++) {
      char* p = buff;
      for (int c = col1; c <= col2; c++, p++) {
        int i = abs(r % size - center) + abs(c % size - center);
        *p = (i < N) ? 'a' + i % nr_letters: '.';
      }
      puts(buff);
    }
  }
  return 0;
}

UVa 1215 - String Cutting

Accepted date: 2016-03-15
Run Time: 0.000
Ranking (as of 2016-03-15): 5 out of 141
Language: C++11

/*
  UVa 1215 - String Cutting

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

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

const int n_max =  10000, k_max = 1000, nr_letters = 'z' - 'a' + 1;
char s[n_max];
int cuts[k_max];
bool l_letters[nr_letters], h_letters[nr_letters];

int main()
{
  int nr_sets;
  scanf("%d", &nr_sets);
  while (nr_sets--) {
    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; i++)
      scanf("%d", &cuts[i]);
    scanf("%s", s);
    int length = 0;
    for (char* p = s; *p; p++, length++)
      *p -= 'a';
    vector<int> positions;
    positions.push_back(0);
    positions.push_back(length);
    int cost = 0;
    for (int i = 0; i < k; i++) {
      int m = cuts[i];
      vector<int>::iterator pi = lower_bound(positions.begin(), positions.end(), m);
      int l = *prev(pi), h = *pi;
      memset(l_letters, 0, sizeof(l_letters));
      for (int j = l; j < m; j++)
        l_letters[s[j]] = true;
      memset(h_letters, 0, sizeof(h_letters));
      for (int j = m; j < h; j++)
        h_letters[s[j]] = true;
      for (int i = 0; i < nr_letters; i++)
        if (l_letters[i] ^ h_letters[i])
          cost++;
      positions.insert(pi, m);
    }
    printf("%d\n", cost);
  }
  return 0;
}

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