Then I decided to search Google about the problem. Then upon first search, I saw the key words "Brute force". I thought about it a little and I thought that brute force may not be a bad idea after all. I counted the total number of brute force cases and there were only 6. So I decided to hard code them all since there were only 6 cases. For each case, compute for the number of movements. Then choose the case that has the minimum number of cases.

But there's a problem in choosing the case with the minimum number of movements. The problem constrains that the case chosen should be the one that comes out first in alphabetical sorting. Thus, I had to arrange the cases in such a way that the first case was the first in alphabetical order, and the last case was the last in alphabetical sorting. Here's my sample code:

#include

int main() {

char line[100];

int b0[3], b1[3], b2[3], x[6], i, j, min;

while (fgets(line, 100, stdin)) {

sscanf(line, "%d %d %d %d %d %d %d %d %d"

, &b0[0], &b0[1], &b0[2]

, &b1[0], &b1[1], &b1[2]

, &b2[0], &b2[1], &b2[2]

);

// B = 0; G = 1; C = 2

// 021 BCG

x[0] = (b1[0] + b2[0]) + (b0[2] + b2[2]) + (b0[1] + b1[1]);

// 012 BGC

x[1] = (b1[0] + b2[0]) + (b0[1] + b2[1]) + (b0[2] + b1[2]);

// 201 CBG

x[2] = (b1[2] + b2[2]) + (b0[0] + b2[0]) + (b0[1] + b1[1]);

// 210 CGB

x[3] = (b1[2] + b2[2]) + (b0[1] + b2[1]) + (b0[0] + b1[0]);

// 102 GBC

x[4] = (b1[1] + b2[1]) + (b0[0] + b2[0]) + (b0[2] + b1[2]);

// 120 GCB

x[5] = (b1[1] + b2[1]) + (b0[2] + b2[2]) + (b0[0] + b1[0]);

for (i = 4, j = 5, min = x[5]; i >= 0; i -= 1) {

if (x[i] <= min) {

min = x[i];

j = i;

}

}

// for (i = 0; i < 6; i += 1) {

// printf("%d: %d\n", i, x[i]);

// }

switch(j) {

case 0: printf("BCG %d\n", x[j]);

break;

case 1: printf("BGC %d\n", x[j]);

break;

case 2: printf("CBG %d\n", x[j]);

break;

case 3: printf("CGB %d\n", x[j]);

break;

case 4: printf("GBC %d\n", x[j]);

break;

case 5: printf("GCB %d\n", x[j]);

break;

}

}

return 0;

}

## No comments:

## Post a Comment