10420: List of Conquests

For this problem, a C++ standard map could be used where the country is used as the key and the number of women Don Giovanni loved in the corresponding country is used as the value. The C++ standard library map automatically sorts its key and value pairs in ascending order according to the keys. In effect, a straightforward iteration on the map yields an alphabetical traversal on the countries accumulated.

Here's a sample implementation:

000 #include <stdio.h>
001 #include <map>
002 #include <iostream>
003 #include <string>
004 
005 using namespace std;
006 
007 int main() {
008   char line[100], ctmp[100];
009   int n, i, j;
010   map<string, int> countries;
011   map<string, int>::iterator iter;
012   
013   fgets(line, 100, stdin);
014   sscanf(line, "%d", &n);
015   
016   for (i = 0; i < n; i += 1) { 
017     fgets(line, 100, stdin);
018     
019     for (j = 0; 1; j += 1) {
020       if (line[j] == ' ') {
021         break;
022       }
023       ctmp[j] = line[j];
024     }
025     ctmp[j] = 0;
026     
027     countries[ctmp] += 1;
028   }
029   
030   for (iter = countries.begin(); iter != countries.end(); ++iter) {
031     cout << iter->first << " " << iter->second << endl;
032   }
033 
034   return 0;
035 }

UVa problem 10260: sample algorithm sample code

To solve UVa problem 10260 (Soundex), one could use a map to map characters to their integer values.

001 #include "stdio.h"
002 #include "map"
003 
004 using namespace std;
005 
006 int main() {
007   char line[100], ctmp[100], dtmp[100];
008 
009   int i, j, prev, len, arr[20];
010 
011   map m;
012   map::iterator mi;
013 
014   m['B'] = 1;
015   m['F'] = 1;
016   m['P'] = 1;
017   m['V'] = 1;
018 
019   m['C'] = 2;
020   m['G'] = 2;
021   m['J'] = 2;
022   m['K'] = 2;
023   m['Q'] = 2;
024   m['S'] = 2;
025   m['X'] = 2;
026   m['Z'] = 2;
027 
028   m['D'] = 3;
029   m['T'] = 3;
030 
031   m['L'] = 4;
032 
033   m['M'] = 5;
034   m['N'] = 5;
035 
036   m['R'] = 6;
037 
038   while (fgets(line, 100, stdin)) {
039     for (i = 0, j = 0, prev = 0, len = 0; line[i] != 0; i++) {
040       mi = m.find(line[i]);
041       
042       if (mi != m.end()) {
043         j = (*mi).second;
044 
045         if (j == prev) {
046           continue;
047         }
048 
049         arr[len] = j;
050         len++;
051         prev = j;
052       }
053       else {
054         prev = 0;
055       }
056     }
057 
058     for (i = 0; i < len; i++) {
059       printf("%d", arr[i]);
060     }
061     printf("\n", ctmp);
062   }
063 
064   return 0;
065 }

UVa problem 10851: sample algorithm

In UVa problem 10851 (2D Hieroglyphs decoder), one could explore the advantage of using right bit-shifts instead of long-cut division for division by powers of 2. For example, to divide a number by 128 (which is 2 raised to the power of 7), one could simply shift the number 7 bits to the right.Definitely, this fact could give one an advantage as a bit-shift operation is so much simpler and faster than traditional division.

Moreover, the mod operation may be quite computationally expensive as well. Since a mod by 2 operation is only needed, one could simply check whether the last binary bit of a number is 0 or 1 in order to tell if the number is divisible by 2 or not.

For example, the number 15 when represented in binary is 1111. Since its last bit (the right-most) is 1, then it is not divisible by 2. The number 12 when represented in binary is 1100. Since the last bit is 0, then it is divisible by 2. Bitwise-ANDing the number with 1 will enable one to get the last bit of the number.

For this problem, one could build a lookup table for each of the 256 ASCII characters. One could explore the use of a C++ standard map, where the key is the encrypted character and the value is the actual ASCII character. For example, we could build a map like the following:

Key, Value
//\\//\/, L
\/////\/, A
…

And so when our program sees an encryption of //\\//\/, it can simply lookup the map and find that the encryption stands for the ASCII character L.