OJ Board

Have you noted follow sentence in problem?

If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.

I think you note the sentence , but your code got wrong order,
the write order to if() compares should be follow:
[cpp]
min = sum[2];
if(sum[1] < min)
{
min = sum[1];
j = 1;
}
if(sum[4] < min)
{
min = sum[4];
j = 4;
}
if(sum[6] < min)
{
min = sum[6];
j = 6;
}
if(sum[3] < min)
{
min = sum[3];
j = 3;
}
if(sum[5] < min)
{
min = sum[5];
j = 5;
}
[/cpp]
then try again

BTW. you should use a more readable style in your code, isn't the code in the follow more comprehensible ?
if you do so, we can read your code more easier, and you'll got more and useful help
[cpp]
// B is index 0
// G is index 1
// C is index 2

// here I use myMin because min is declared in C++ <algorithm> lib
int myMin = sum[0];

sum[1] = sum[0] - glass[0][0] - glass[1][2] - glass[2][1]; // BGC
sum[2] = sum[0] - glass[0][0] - glass[1][1] - glass[2][2]; // BCG
sum[3] = sum[0] - glass[0][2] - glass[1][0] - glass[2][1]; // CBG
sum[4] = sum[0] - glass[0][2] - glass[1][1] - glass[2][0]; // CGB
sum[5] = sum[0] - glass[0][1] - glass[1][0] - glass[2][2]; // GBC
sum[6] = sum[0] - glass[0][1] - glass[1][2] - glass[2][0]; // GCB

for(int i=1; i<=6; ++i)
{
if(sum < myMin)
{
myMin = sum;
j = i;
}
}

switch(j)
{
case 1:
printf("BCG");
break;
case 2:
printf("BGC");
break;
case 3:
printf("CBG");
break;
case 4:
printf("CGB");
break;
case 5:
printf("GBC");
break;
default:
printf("GCB");
}
printf(" %d\n", myMin);
[/cpp]

same error occurs more than once:

/*"BCG";*/
menora[0]=caixas[1]+caixas[2]+caixas[3]+caixas[4]+caixas[6]+caixas[8];
/*"BGC";*/
menora[5]=caixas[1]+caixas[2]+caixas[3]+caixas[5]+caixas[6]+caixas[7];
/*"CBG";*/
menora[1]=caixas[0]+caixas[1]+caixas[4]+caixas[5]+caixas[6]+caixas[8];
/*"CGB";*/
menora[4]=caixas[0]+caixas[1]+caixas[3]+caixas[5]+caixas[7]+caixas[8];
/*"GBC";*/
menora[3]=caixas[0]+caixas[2]+caixas[4]+caixas[5]+caixas[6]+caixas[7];
/*"GCB";*/
menora[2]=caixas[0]+caixas[2]+caixas[3]+caixas[4]+caixas[7]+caixas[8];

should be:

[cpp]
/*"BCG";*/
menora[0]=caixas[1]+caixas[2]+caixas[3]+caixas[4]+caixas[6]+caixas[8];
/*"BGC";*/
menora[1]=caixas[1]+caixas[2]+caixas[3]+caixas[5]+caixas[6]+caixas[7];
/*"CBG";*/
menora[2]=caixas[0]+caixas[1]+caixas[4]+caixas[5]+caixas[6]+caixas[8];
/*"CGB";*/
menora[3]=caixas[0]+caixas[1]+caixas[3]+caixas[5]+caixas[7]+caixas[8];
/*"GBC";*/
menora[4]=caixas[0]+caixas[2]+caixas[4]+caixas[5]+caixas[6]+caixas[7];
/*"GCB";*/
menora[5]=caixas[0]+caixas[2]+caixas[3]+caixas[4]+caixas[7]+caixas[8];
[/cpp]

hi,

I'm trying to solve problem 102 , but I'm getting wrong answer and I
don't know why , it seem to be correct ...
I'm sendind the source code, please, if someone can help me ...

thank's ..
[/c]

passwd wrote: hi,

I'm trying to solve problem 102 , but I'm getting wrong answer and I
don't know why , it seem to be correct ...
I'm sendind the source code, please, if someone can help me ...

Code: Select all

[c]
    min=bcg;
    if(bgc<min) { min=bgc; seq[0]='B'; seq[1]='G'; seq[2]='C'; };
    if(cbg<min) { min=cbg; seq[0]='C'; seq[1]='B'; seq[2]='G'; };
    if(cgb<min) { min=cgb; seq[0]='C'; seq[1]='G'; seq[2]='B'; };
    if(gbc<min) { min=gbc; seq[0]='G'; seq[1]='B'; seq[2]='C'; };
    if(gcb<min) { min=gbc; seq[0]='G'; seq[1]='C'; seq[2]='B'; };

[/c]

thank's ..
[/c]

the problem says

If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.

i think u can smell it

I know that the problem says if more than one order of brown, green,
and clear bins yields the minimum number of movements then
the alphabetically first string representing a minimal configuration
should be printed

but I don

[quote="passwd"]
but I don

I don't quite understand why I got this result...

[c]
#include<stdio.h>
#include<string.h>
void main()
{
int k;
long sum,tmp;
long B[3],G[3],C[3];
while(scanf("%D%D%D%D%D%D%D%D%D",&B[0],&G[0],&C[0],&B[1],&G[1],&C[1],&B[2],&G[2],&C[2])!=EOF)
{
sum=B[1]+B[2]+C[0]+C[2]+G[0]+G[1];
tmp=sum;
k=1;
sum=B[1]+B[2]+G[0]+G[2]+C[0]+C[1];
if(tmp>sum)
{
tmp=sum;
k=2;
}
sum=C[1]+C[2]+B[0]+B[2]+G[0]+G[1];
if(tmp>sum)
{
tmp=sum;
k=3;
}
sum=C[1]+C[2]+G[0]+G[2]+B[0]+B[1];
if(tmp>sum)
{
tmp=sum;
k=4;
}
sum=G[1]+G[2]+B[0]+B[2]+C[0]+C[1];
if(tmp>sum)
{
tmp=sum;
k=5;
}
sum=G[1]+G[2]+C[0]+C[2]+B[0]+B[1];
if(tmp>sum)
{
tmp=sum;
k=6;
}
switch(k)
{
case 1:
printf("BCG");
break;
case 2:
printf("BGC");
break;
case 3:
printf("CBG");
break;
case 4:
printf("CGB");
break;
case 5:
printf("GBC");
break;
case 6:
printf("GCB");
break;
default:
printf("\0");
}
printf(" %ld\n",tmp);
}
}[/c][/c]

the printf("\0"); is a bit weird, but i wouldn't mind about it.

did you consider the fact that scanf could never return EOF, but could return ERROR instead?
try to use something like while(scanf(......) == 9) instead of != EOF

also.. you do not solve all the problem. what happens if several solutions are as good as one another? you should pick up the one that comes first alphabetically. i don't see it in your program.

plus, your program is ugly imagine if there were 10 bins. would you really write 10! tests like this in sequence?

good luck

Can I ask a small question?What does "scanf(....)==9" means?Doesnt that means I read 9 stuff with the function scanf?Or 9 is a special constant?(I really don't know this )

scanf returns the number of things scanned in, so if you were to scan in 2 things, you would have this:

while ( 2 == scanf( "%d %d", &a, &b ) )

ya.I got it.Sorry for asking such a stupid question like this.(I didn't read it very carefully )

Yeah,epsilon.I tried what you said,and I got accepted.
Because the algrithm is easy,I just used an direct program(sure an ugly one).I will try to simplify my program after then.

Thanks for your help !!

i got AC using the above ugly method.
can u tell me what a better method wud be..

you could read my code. note that it's still not very elegant, since i handtyped the table of permutations... if there were more bin, i'd rather generate this table at run time (which is not difficult).

[c]/* Ecological Bin Packing */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BROWN 0
#define GREEN 1
#define CLEAR 2

char colors[] = "BGC";

int perms[6][3] = { {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };

void get_opti(int *bottles, char *order, int *min)
{
int i,j;
int moves;
char tmp_order[4];
*min = -1;
for (i=0; i<6; i++)
{
moves = bottles[3 + perms[0]] + bottles[6 + perms[0]]
+ bottles[perms[1]] + bottles[6 + perms[1]]
+ bottles[perms[2]] + bottles[3 + perms[2]];

for (j=0;j<3;j++)
tmp_order[j] = colors[perms[j]];
tmp_order[3] = '\0';

if (*min == -1 || moves < *min)
{
*min = moves;
strcpy(order,tmp_order);
}
else if (moves == *min)
if (strcmp(order, tmp_order) > 0)
strcpy(order,tmp_order);
}
}

int main()
{
int bottles[9];
int min;
char order[4];
while(scanf("%d %d %d %d %d %d %d %d %d", &bottles[0], &bottles[1], &bottles[2],
&bottles[3], &bottles[4], &bottles[5],
&bottles[6], &bottles[7], &bottles[8]) == 9)
{
get_opti(bottles,order,&min);
printf("%s %d\n",order,min);
}
return EXIT_SUCCESS;
}
[/c]

the idea behind generating a table of all possible permutations is to use a recursive function, along with a table that you pass as an argument, and which tells you what item has already been used.

such code would look like:

char sequence[] = "0123456789";

void make_perms()
{
char table[10] = {0,0,0,0,0,0,0,0,0,0};
make_perms_2(table,0);
}

void make_perms_2(char *tab, int n)
{
int i;
char new_table[10];
if (n == 10)
{
printf("%s\n",sequence);
return;
}
for (i=0; i<10; i++)
if (!tab)
{
memcpy(new_table,tab,10);
new_table = 1;
sequence[n] = '0'+i;
make_perms_2(new_table,n+1);
}
}

it should print all permutations of numbers 0-9 ... it's easy to modify this code to works with any number of items... please note that i just typed this code, without testing it

thanx for ur reply and data on how to generate permutations
but then my query was r u supposed to do n! permutations and check up or is there a better method.