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 }

An easier way to find easy problems

An easier way to find easy problems in the UVa Online Judge is to use Steven Halim's World of Seven website. His website can be easily searched through Google. Figure 1 shows an excerpt from his website.


Figure 1. Illustration from World of Seven website for finding easy problems.

From Figure 1, we see that some problems are rated 7.0, 8.0, 2.0, 5.5, 2.5, etc. Generally, the lower the rating the easier the problem is. So if you want to find an easy problem, choose a rating number that is as close to 0 as possible.

UVa problem 10469: sample algorithm, sample code

To solve 10469 (To carry or not to carry), one needs to be able to discover that in order to get the sum without the carry-bits, one simply has to perform a bitwise xor operation on the two numbers.

XOR is simply the following formulat:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 1

For example, for 4 XOR 6, we have to represent them in binary as follows:
4: 100
6: 110
______
2: 010

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int i, j;
007 
008   while (fgets(line, 100, stdin)) {
009     sscanf(line, "%d %d", &i, &j);
010     printf("%d\n", i ^ j);
011   }
012 
013   return 0;
014 }

UVa problem 100: sample code, sample algorithm

UVa problem 100 (3n + 1) is a pretty straightforward problem. There is one tricky part though. That i is not necessarily always less than j. So one needs to watch out for the case when i is greater than or equal to j.

Also one, can speed things a little bit by using the bit-shift operator for division or multiplication. A division by 2 is similar to a right bit-shift by 1 bit. A multiplication by 2 is equivalent to a left bit-shift by 1 bit.

That is, x / 2 is equivalent to x >> 1; x * 2 is equivalent to x << 1.

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   i
007       , j
008       , n
009       , n0
010       , m
011       , cycle
012       , max
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d %d", &i, &j);
017 
018     if (i <= j) {
019       for (n0 = i, max = 1; n0 <= j; n0++) {
020         n = n0;
021         for (cycle = 1; n != 1; cycle++) {
022           m = n & 1;
023           if (m) {
024             m = n << 1;
025             n = m + n + 1;
026           }
027           else {
028             n >>= 1;
029           } 
030         }
031         if (cycle > max) {
032           max = cycle;
033         }
034       }
035     }
036     else {
037       for (n0 = j, max = 1; n0 <= i; n0++) {
038         n = n0;
039         for (cycle = 1; n != 1; cycle++) {
040           m = n & 1;
041           if (m) {
042             m = n << 1;
043             n = m + n + 1;
044           }
045           else {
046             n >>= 1;
047           } 
048         }
049         if (cycle > max) {
050           max = cycle;
051         }
052       }
053     }
054 
055     printf("%d %d %d\n", i, j, max);
056   }
057 
058   return 0;
059 }

UVa problem 10696: sample code, sample algorithm

To solve this problem, one needs to be able to discover the observation that:
if N is greater than 100, the output is N - 10; otherwise it is always 91.

One can discover this observation by running a simple simulation of the recursive F91 function:

001 #include "stdio.h"
002 
003 int f91(int n) {
004   if (n <= 100) {
005     return f91(f91(n + 11));
006   }
007   else {
008     return n - 10;
009   }
010 }
011 
012 int main() {
013   char line[100];
014 
015   int n;
016 
017   while (fgets(line, 100, stdin)) {
018     sscanf(line, "%d", &n);
019  
020     if (n == 0) {
021       break;
022     }
023 
024     printf("%d\n", f91(n));
025   }
026 
027   return 0;
028 }

After discovering the pattern, one can then simplify his code like as follows:

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005   int   n
006       , n1;
007 
008   while(fgets(line, 100, stdin)) {
009     sscanf(line, "%d", &n);
010 
011     if (n == 0) {
012       break;
013     }
014 
015     if (n > 100) {
016       n1 = n - 10;
017     }
018     else {
019       n1 = 91;
020     }
021 
022     printf("f91(%d) = %d\n", n, n1); 
023   }
024 
025   return 0;
026 }