11044: Searching for Nessy

000 #include <stdio.h>
001 
002 int main() {
003   char line[100];
004   int i, t, n, m, nq, mq, nr, mr, s;
005 
006   fgets(line, 100, stdin);
007   sscanf(line, "%d", &t);
008 
009   for (i = 0; i < t; i += 1) {
010     fgets(line, 100, stdin);
011     sscanf(line, "%d %d", &n, &m);
012 
013     n -= 2;
014     nq = n / 3;
015     nr = n % 3;
016     if (nr) {
017       nq += 1;
018     }
019 
020     m -= 2;
021     mq = m / 3;
022     mr = m % 3;
023     if (mr) {
024       mq += 1;
025     }
026 
027     s = nq * mq;
028     printf("%d\n", s);
029   }
030 
031   return 0;
032 }

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 }

10361: Automatic Poetry

#include "stdio.h"

int main() {
  char line[100], s1[100], s2[100], s3[100], s4[100], s5[100];
  char l1[100], l2[100];
  int i, j, k, n, q;
  
  fgets(line, 100, stdin);
  sscanf(line, "%d", &n);
  
  for (i = 0; i < n; i += 1) {
    s1[0] = 0;
    s2[0] = 0;
    s3[0] = 0;
    s4[0] = 0;
    s5[0] = 0; 

    fgets(line, 100, stdin);
    
    for (j = 0, k = 0, q = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '<') {
        break;
      }
      s1[k] = line[j];
      l1[q] = line[j];      
    }
    s1[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '>') {
        break;
      }
      s2[k] = line[j];
      l1[q] = line[j];      
    }
    s2[k] = 0;
    j += 1;

    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '<') {
        break;
      }
      s3[k] = line[j];
      l1[q] = line[j];      
    }
    s3[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '>') {
        break;
      }
      s4[k] = line[j];
      l1[q] = line[j];      
    }
    s4[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '0' || line[j] == '\n') {
        break;
      }
      s5[k] = line[j];
      l1[q] = line[j];      
    }
    s5[k] = 0;
    l1[q] = 0;
    
    fgets(line, 100, stdin);
    
    for (j = 0; 1; j += 1) {
      if (line[j] == '.') {
        break;
      }
      l2[j] = line[j];
    }
    l2[j] = 0;
    
    printf("%s\n", l1);
    printf("%s%s%s%s%s\n", l2, s4, s3, s2, s5);   
  }

  return 0;
}

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.