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.

UVa problem 10851: sample code

001 #include "stdio.h"
002 #include "string"
003 #include "map"
004 #include "iostream"
005 
006 using namespace std;
007 
008 int main() {
009   char   line[100]
010        , ctmp[100]
011        , dtmp[100]
012        , input[10][100]
013        ;
014   int   num_msg
015       , i
016       , ii
017       , j
018       , k
019       , b
020       , c
021       , m
022       , n
023       , p
024       , msg_len;
025       ;
026 
027   map imap;
028   map::iterator iter;
029 
030   for (c = 0; c < 256; c += 1) {
031     ctmp[0] = '/';
032     ctmp[9] = '/';
033 
034     for (i = 1; i < 9; i += 1) {
035       ii = i - 1;
036 
037       b = c >> ii;
038       b &= 1;
039 
040       ctmp[i] = b == 0 ? '/' : '\\';
041     }
042 
043     ctmp[10] = 0;
044 
045     imap.insert(pair(ctmp, c));
046   }
047 
048   fgets(line, 100, stdin);
049   sscanf(line, "%d\n", &num_msg);
050 
051   for (i = 0; i < num_msg; ++i) {
052     for (j = 0; j < 10; ++j) {
053       fgets(line, 100, stdin);
054       sscanf(line, "%s\n", &input[j]);
055     }
056 
057     fgets(line, 100, stdin);
058 
059     msg_len = strlen(input[0]) - 2;
060 
061     for (m = 1, p = 0; m <= msg_len; m += 1, p += 1) {
062       for (n = 0; n < 10; n += 1) {
063         ctmp[n] = input[n][m];
064       }
065       ctmp[n] = 0;
066 
067       iter = imap.find(ctmp);
068       dtmp[p] = iter->second;
069     }
070     dtmp[p] = 0;
071 
072     printf("%s\n", dtmp);
073   }
074 
075   return 0;
076 }