UVa 10815 - Andy's First Dictionary

Accepted date: 2012-02-14
Ranking (as of 2013-06-09): 237 out of 3312
Language: C++

/*
  UVa 10815 - Andy's First Dictionary

  To build using Visual Studio 2008:
    cl -EHsc -O2 andys_first_dictionary.cpp
*/

#include <string>
#include <set>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

int main()
{
  const int nr_chr_max = 256;
  char word[nr_chr_max + 1];
  set<string> words;
  while (scanf("%s", word) != EOF)
    for (int i = 0, length = strlen(word); i < length; /* i++ */) {
      while (i < length && !isalpha(word[i]))
        i++;
      if (i == length)
        break;
      int j = 0;
      char w[nr_chr_max + 1];
      for ( ; i < length && isalpha(word[i]); i++, j++)
        w[j] = static_cast<char>(tolower(word[i]));
      w[j] = '\0';
      words.insert(string(w));
    }
  for (set<string>::const_iterator i = words.begin(), e = words.end();
    i != e; ++i)
    printf("%s\n", (*i).c_str());
  return 0;
}

UVa 644 - Immediate Decodability

Accepted date: 2012-02-15
Ranking (as of 2013-06-09): 874 out of 2256
Language: C++

/*
  UVa 644 - Immediate Decodability

  To build using Visual Studio 2008:
    cl -EHsc -O2 immediate_decodability.cpp
*/

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

struct symbol
{
  int length_;
  int code_;
  symbol() : length_(-1), code_(0) {}
  symbol(int length, int code) : length_(length), code_(code) {}
  bool operator<(const symbol& s) const {return length_ < s.length_;}
};

bool is_immediate_decodable(int n, const symbol symbols[])
{
  int masks[] = {0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f,
    0x00ff, 0x01ff, 0x03ff};
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++) {
      int diff = symbols[i].code_ ^ symbols[j].code_;
      if (!(diff & masks[symbols[i].length_]))
        return false;
    }
  return true;
}

int main()
{
  const int nr_symbols_max = 8;
  string bc;
  for (int g = 1; cin >> bc; g++) {
    int nr_symbols = 0;
    symbol symbols[nr_symbols_max];
    do {
      int length = bc.length(), code = 0;
      for (int i = 0, b = 1; i < length; i++, b <<= 1)
        if (bc[i] == '1')
          code |= b;
      symbols[nr_symbols++] = symbol(length, code);
      cin >> bc;
    } while (bc != "9");
    sort(symbols, symbols + nr_symbols);
    cout << "Set " << g <<
      ((is_immediate_decodable(nr_symbols, symbols)) ?
      " is immediately decodable\n" : " is not immediately decodable\n");
  }
  return 0;
}

UVa 10115 - Automatic Editing

Accepted date: 2012-02-15
Ranking (as of 2013-06-09): 1037 out of 1867
Language: C++

/*
  UVa 10115 - Automatic Editing

  To build using Visual Studio 2008:
    cl -EHsc -O2 automatic_editing.cpp
*/

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

const int nr_rules_max = 10;
const int nr_rule_chrs_max = 80, nr_text_chrs_max = 255;

struct find_replace_rule {
  char find_[nr_rule_chrs_max + 1];
  char replace_[nr_rule_chrs_max + 1];
} rules[nr_rules_max];

void apply_rule(const find_replace_rule* rule, char* text)
{
  const char *f = rule->find_, *r = rule->replace_;
  int fl = strlen(rule->find_), rl = strlen(rule->replace_);
  for ( ; *text; )
    if (!strncmp(text, f, fl)) {
      memmove(text + rl, text + fl, strlen(text + fl) + 1);
      memcpy(text, r, rl);
    }
    else
      text++;
}

int main()
{
  while (true) {
    char text[nr_text_chrs_max + 1];
    gets(text);
    int nr_rules;
    sscanf(text, "%d", &nr_rules);
    if (!nr_rules)
      break;
    for (int i = 0; i < nr_rules; i++) {
      gets(rules[i].find_);
      gets(rules[i].replace_);
    }
    gets(text);
    for (int i = 0; i < nr_rules; i++)
      apply_rule(rules + i, text);
    printf("%s\n", text);
  }
  return 0;
}

UVa 400 - Unix ls

Accepted date: 2012-02-19
Ranking (as of 2013-06-09): 794 out of 3046
Language: C++

/*
  UVa 400 - Unix ls

  To build using Visual Studio 2008:
    cl -EHsc -O2 unix_ls.cpp
*/

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

int main()
{
  const int max_length = 60;
  int nr_names;
  while (cin >> nr_names) {
    vector<string> names(nr_names);
    int max_name_length = 0;
    for (int i = 0; i < nr_names; i++) {
      cin >> names[i];
      max_name_length =
        max(max_name_length, static_cast<int>(names[i].length()));
    }
    sort(names.begin(), names.end());
    int nr_columns = 1;
    for (int l = max_name_length * 2 + 2;
      l <= max_length; l += max_name_length + 2)
      nr_columns++;
    int nr_rows = (nr_names + nr_columns - 1) / nr_columns;
    cout << "------------------------------------------------------------\n";
    for (int i = 0; i < nr_rows; i++) {
      for (int j = 0; j < nr_columns; j++) {
        int ni = i + nr_rows * j;
        if (ni < nr_names) {
          cout << names[ni];
          int l = max_name_length - names[ni].length();
          if (j < nr_columns - 1)
            l += 2;
          for (int k = 0; k < l; k++)
            cout << ' ';
        }
        else
          break;
      }
      cout << endl;
    }
  }
  return 0;
}

UVa 123 - Searching Quickly

Accepted date: 2012-02-19
Ranking (as of 2013-06-09): 619 out of 2304
Language: C++

/*
  UVa 123 - Searching Quickly

  To build using Visual Studio 2008:
    cl -EHsc -O2 searching_quickly.cpp
*/

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;

int main()
{
  set<string> words_to_ignore;
  while (true) {
    string s;
    cin >> s;
    if (s == "::")
      break;
    words_to_ignore.insert(s);
  }
  int nr_titles = 0;
  vector<string> titles;
  multimap< string, pair<int, int> > words;
    // key is a word in a titile, 
    // and its values are pair of an index to the vector of titles and 
    // its position in a title
  string t;
  while (getline(cin, t)) {
    transform(t.begin(), t.end(), t.begin(), (int(*)(int))tolower);
    const char* p = t.c_str();
    for (const char* q = p; *q; ) {
      while (*q == ' ')
        q++;
      const char* r = q;
      while (*r && *r != ' ')
        r++;
      string w(q, r - q);
      set<string>::iterator i = words_to_ignore.find(w);
      if (i == words_to_ignore.end())
        words.insert(make_pair(w, make_pair(nr_titles, q - p)));
      q = r;
    }
    titles.push_back(t);
    nr_titles++;
  }
  for (multimap< string, pair<int, int> >::const_iterator i = words.begin(),
    e = words.end(); i != e; ++i) {
    int length = i->first.length();
    pair<int, int> p = i->second;
    string t(titles[p.first]);
    // convert the keyword to upper-case letters
    string::iterator j = t.begin(), k = t.begin();
    advance(j, p.second);
    advance(k, p.second + length);
    transform(j, k, j, (int(*)(int))toupper);
    cout << t << endl;
  }
  return 0;
}

UVa 755 - 487-3279

Accepted date: 2012-02-20
Ranking (as of 2013-06-09): 461 out of 1887
Language: C++

/*
  UVa 755 - 487-3279

  To build using Visual Studio 2008:
    cl -EHsc -O2 487_3279.cpp
*/

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <map>
#include <cctype>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  const int letters[] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 0, 7, 7,
    8, 8, 8, 9, 9, 9, 0};
  string line;
  istringstream iss(line);
  getline(cin, line);
  iss.str(line);
  int s;
  iss >> s;
  iss.clear();
  while (s--) {
    getline(cin, line); // skip a blank line
    getline(cin, line);
    iss.str(line);
    int n;
    iss >> n;
    iss.clear();
    map<int, int> tns;
      // key is a telephone number, value is its number of occurrences
    for (int i = 0; i < n; i++) {
      getline(cin, line);
      int tn = 0, j = 0;
      for (const char* p = line.c_str(); *p && j < 7; p++)
        if (isalnum(*p)) {
          if (j++)
            tn *= 10;
          if (isdigit(*p))
            tn += *p - '0';
          else
            tn += letters[*p - 'A'];
        }
      map<int, int>::iterator k = tns.find(tn);
      if (k == tns.end())
        tns.insert(make_pair(tn, 1));
      else
        k->second++;
    }
    bool duplicates = false;
    for (map<int, int>::const_iterator i = tns.begin(), e = tns.end();
      i != e; ++i)
      if (i->second > 1) {
        duplicates = true;
        cout << setfill('0') << setw(3) << i->first / 10000 <<
          '-' << setw(4) << i->first % 10000 <<
          ' ' << i->second << endl;
      }
    if (!duplicates)
      cout << "No duplicates.\n";
    if (s)
      cout << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 10785 - The Mad Numerologist

Accepted date: 2012-02-21
Ranking (as of 2013-06-08): 165 out of 848
Language: C++

/*
  UVa 10785 - The Mad Numerologist

  To build using Visual Studio 2008:
    cl -EHsc -O2 the_mad_numerologist.cpp
*/

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

int main()
{
  const int n_max = 210, vowels_usage_max = 21, consonants_usage_max = 5;
  const char vowel_letters[] = {'A', 'U', 'E', 'O', 'I'};
  const char consonant_letters[] = {'J', 'S', 'B', 'K', 'T', 'C', 'L', 'D',
    'M', 'V', 'N', 'W', 'F', 'X', 'G', 'P', 'Y', 'H', 'Q', 'Z', 'R'};
  int nr_cases;
  cin >> nr_cases;
  for (int c = 1; c <= nr_cases; c++) {
    int n;
    cin >> n;
    int nr_vowels = (n + 1) / 2, nr_consonants = n / 2;
    char vowels[n_max + 1], consonants[n_max + 1];

    for (int i = 0, j = 0; i < nr_vowels; j++) {
      int k = min(nr_vowels - i, vowels_usage_max);
      memset(vowels + i, vowel_letters[j], k);
      i += k;
    }
    for (int i = 0, j = 0; i < nr_consonants; j++) {
      int k = min(nr_consonants - i, consonants_usage_max);
      memset(consonants + i, consonant_letters[j], k);
      i += k;
    }
    sort(vowels, vowels + nr_vowels);
    sort(consonants, consonants + nr_consonants);
    char name[n_max + 1];
    for (int i = 0; i < nr_vowels; i++)
      name[2 * i] = vowels[i];
    for (int i = 0; i < nr_consonants; i++)
      name[2 * i + 1] = consonants[i];
    name[nr_vowels + nr_consonants] = '\0';
    cout << "Case " << c << ": " << name << endl;
  }
  return 0;
}