UVa problem 11231: sample code

001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        , first_box
006        , black
007        , white
008        ;
009 
010   int   n
011       , m
012       , c
013       , ne
014       , me
015       , code
016       , x
017       , y
018       , z
019       , q
020       , r
021       , s
022       , v
023       ;
024 
025   black = 'b';
026   white = 'w';
027 
028   while (fgets(line, 100, stdin)) {
029     sscanf(line, "%d %d %d", &n, &m, &c);
030 
031     if (n == 0 && m == 0 && c== 0) {
032       break;
033     }
034 
035     ne = n & 1;
036     me = m & 1;
037 
038     ne <<= 2;
039     me <<= 1;
040 
041     code = 0;
042     code = ne | me | c;
043 
044     if (code == 0) {
045       first_box = black;
046     }
047     else if (code == 1) {
048       first_box = white;
049     }
050     else if (code == 2) {
051       first_box = white;
052     }
053     else if (code == 3) {
054       first_box = black;
055     }
056     else if (code == 4) {
057       first_box = white;
058     }
059     else if (code == 5) {
060       first_box = black;
061     }
062     else if (code == 6) {
063       first_box = black;
064     }
065     else {
066       first_box = white;
067     }
068 
069     if (first_box == white) {
070       x = n - 6;
071       x >>= 1;
072 
073       y = m - 6;
074       y >>= 1;
075 
076       q = n - 7;
077       q >>= 1;
078 
079       r = m - 7;
080       r >>= 1;
081     }
082     else {
083       x = n - 7;
084       x >>= 1;
085 
086       y = m - 6;
087       y >>= 1;
088 
089       q = n - 6;
090       q >>= 1;
091 
092       r = m - 7;
093       r >>= 1;
094     }
095 
096     z = x * y;
097     s = q * r;
098 
099     v = z + s;
100 
101     printf("%d\n", v);
102   }
103 
104   return 0;
105 }

UVa problem 11417: sample algorithm

To solve problem 11417 (GCD), it would be beneficial if one knows about the Euclidean algorithm and division algorithm. One could search up "greatest common divisor" in Google and browse through the corresponding Wikipedia article.

The algorithm to get the greatest common divisor between two numbers i and j can be best explained through an example. Consider i = 18 and j = 84, to get the GCD:

84 / 18 = 4 R 12
18 / 12 = 1 R 6
12 / 6 = 2 R 0

GCD for 18 and 84 is then 6.

Another example: i = 16 and j = 56:

56 / 16 = 3 R 8
16 / 8 = 2 R 0

GCD for 16 and 56 is then 8.

In the process illustrated above, the divisor that caused the remainder to be 0 is the greatest common divisor.

UVa problem 11417: sample code

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   n
007       , g
008       , i
009       , j
010       , k
011       , i0
012       , j0
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d", &n);
017 
018     if (n == 0) {
019       break;
020     }
021 
022     for(i = 1, g = 0; i < n; i++) {
023       for(j = i + 1; j <= n; j++) {
024         i0 = i;
025         j0 = j;
026 
027         for (; 1; ) {
028           k = j % i;
029 
030           if (k == 0) {
031             break;
032           }
033 
034           j = i;
035           i = k;
036         }
037         g += i;
038 
039         j = j0;
040         i = i0;
041       }    
042     }
043 
044     printf("%d\n", g);
045   }
046 
047   return 0;
048 }

UVa problem 10300: sample algorithm

For problem 10300, Ecological Premium, for each farmer case, one is given three parameters: land area (land_area), number of animals (num_animals), and degree of environmental friendliness (degree_friendliness). The problem describes that the premium due to the farmer is calculated as Equation 1.

[Equation 1]
premium = (land_area / num_animals) * degree_friendliness * num_animals

But notice from Equation 1 that num_animals can be cancelled out to simplify the formula to Equation 2.

[Equation 2]
premium = land_area * degree_friendliness

In this case, the num_animals parameter is not needed and is used to confused the solver.

So, for a given test case, we calculate the premium for each farmer. Then we sum them up to obtain the burden due by the government.

UVa problem 10300: Sample code

001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        ;
006 
007   int   num_cases
008       , num_farmers
009       , i
010       , j
011       , area
012       , num_animals
013       , factor
014       , burden
015       ;
016 
017   fgets(line, 100, stdin);
018   sscanf(line, "%d", &num_cases);
019 
020   for (i = 0; i < num_cases; i += 1) {
021     fgets(line, 100, stdin);
022     sscanf(line, "%d", &num_farmers);
023 
024     for (j = 0, burden = 0; j < num_farmers; j += 1) {
025       fgets(line, 100, stdin);
026       sscanf(line, "%d %d %d", &area, &num_animals, &factor);
027 
028       burden += area * factor;
029     }
030 
031     printf("%d\n", burden);
032   }
033 
034   return 0;
035 }