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 }

## Sunday, November 1, 2009

### 11044: Searching for Nessy

### 10420: List of Conquests

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;

}

## Friday, January 30, 2009

### UVa problem 10260: sample algorithm sample code

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 mapm;

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

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

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

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 }

## Sunday, January 18, 2009

### UVa problem 10696: sample code, sample algorithm

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 }

## Saturday, January 17, 2009

### UVa problem 10783: sample algorithm

for (i = a, sum = 0; i <= b; i += 1) {

__j = i mod 2;

__if (j == 1) {

____sum += i;

__}

}

To hasten the computation, we can start at an odd number in the for-loop and add 2 to the iterator index for each iteration.

First we check if a is odd or even. If it is even, we increment it to make it odd. Then we go to the for-loop:

for (j = a, sum = 0; j <= b; j += 2) {

__sum += j;

}

### UVa problem 10783: sample code

001 #include "stdio.h"

002

003 int main() {

004 char line[100];

005

006 int num_cases

007 , i

008 , j

009 , k

010 , a

011 , b

012 , sum

013 ;

014

015 fgets(line, 100, stdin);

016 sscanf(line, "%d", &num_cases);

017

018 for (i = 1; i <= num_cases; i += 1) {

019 fgets(line, 100, stdin);

020 sscanf(line, "%d", &a);

021

022 fgets(line, 100, stdin);

023 sscanf(line, "%d", &b);

024

025 k = a & 1;

026 if (k == 0) {

027 a += 1;

028 }

029

030 for (j = a, sum = 0; j <= b; j += 2) {

031 sum += j;

032 }

033

034 printf("Case %d: %d\n", i, sum);

035 }

036

037 return 0;

038 }

### UVa problem 11231: sample algorithm

To solve UVa problem 11231 (Black and white painting), one has to distinguish between two cases: when the top left corner (first_box) is white, or black. After some analyses, one is able to find a way to determine if the first_box is white or black based on the given n, m and c. Figure 1 summarizes this.

Figure 1. Summary for determining if the top left corner is white or black given n, m and c.

In Figure 1, if n and m are of the same type, for example, both even or both odd, then the color of the bottom right corner (last_box) will be the same as the first_box. Otherwise, they will have opposite colors.

First, we tackle the case when the first_box is white (case_white). For case_white, there are two cases. Let us name them case_white1 and case_white2.

For case_white1, we take a look at the chess boards embedded within the painting. This is shown in Figure 2.

Figure 2. Chess boards embedded in the painting for case_white_1.

In Figure 2, passing lanes, both horizontal and vertical are shown. Only 4 passing lanes are shown to avoid clutter. A chess board is defined for each intersection between a horizontal passing lane and a vertical passing lane.

We define a chess board as having four coordinates: h1, h2, v1, v2. h1 stands for the lower-numbered row of the board, h2 stands for the higher-numbered row, v1 stands for the lower-numbered column and v2 stands for the higher-numbered column. A chess board will be designated (h1, h2, v1, v2) for brevity.

In Figure 2, then, there are 4 embedded chess boards as identified when a horizontal lane intersects a vertical lane:

(1, 8, 1, 8)

(1, 8, 3, 10)

(3, 10, 1, 8)

(3, 10, 3, 10)

To compute the number of embedded chess boards in case_white1, we need to obtain the total number of boards in each vertical passing lane. Let us call this number x. We also need to obtain the total number of boards in each horizontal passing lane, calling this number y. The product of x and y will give us the total number of boards for case_white1. Let us call this product, z.

By observing the patterns in case_white1, we arrive at a formula given by Equation 1.

[Equation 1]

x = (n - 6) / 2

y = (m - 6) / 2

z = x * y

Next, we tackle case_white2. Figure 3 shows the embedded boards for case_white2.

Figure 3. Chess boards embedded in the painting for case_white_2.

In Figure 3, the embedded boards have the following coordinates:

(2, 9, 2, 9)

(2, 9, 4, 11)

(4, 11, 2, 9)

(4, 11, 4, 11)

Taking the numbers of boards in the vertical lanes to be q, and the number of boards in the horizontal lanes to be r, we arrive at Equation 2, where s is the total number of boards for case_white2

[Equation 2]

q = (n - 7) / 2

r = (m - 7) / 2

s = q * r

Figure 4. Chess boards embedded in case_black_1.

In Figure 4, the boards have the following coordinates:

(2, 9, 1, 8)

(2, 9, 3, 10)

(4, 11, 1, 8)

(4, 11, 3, 10)

We also arrive at Equation 3, using the same analogy for the variable names as in Equation 1.

[Equation 3]

x = (n - 7) / 2

y = (m - 6) / 2

z = x * y

Figure 5 shows case_black_2.

Figure 5, chess boards embedded in case_black2.

In Figure 5, the following boards are defined:

(1, 8, 2, 9)

(1, 8, 4, 11)

(3, 10, 2, 9)

(3, 10, 4, 11)

Equation 4 is also derived using the same terminologies as used in Equation 2.

[Equation 4]

q = (n - 6) / 2

r = (m - 7) / 2

s = q * r