102 - Ecological Bin Packing

[58050zz]

thanks ...
but why ?

search ..i will get much

[59557RC]

why i get WA by this.anyone pls help me.



#include<stdio.h>

int main(void)
{
unsigned long int b[3],g[3],c[3],total[6],min[6],i,j,k,temp;

while ( scanf("%lu %lu %lu %lu %lu %lu %lu %lu %lu",&b[0],&g[0],&c[0],&b[1],&g[1],&c[1],&b[2],&g[2],&c[2])==9 ) {
for(i=0;i<6;i++){

/* BCG */

if(i==0) {
total=b[1]+b[2]+c[0]+c[2]+g[0]+g[1];

}

/* BGC */

else if(i==1){
total=b[1]+b[2]+g[0]+g[2]+c[0]+c[1];



}
/* CBG */
else if(i==2){
total=b[0]+b[2]+g[0]+g[1]+c[1]+c[2];



}

/* CGB */
else if(i==3){
total=b[1]+b[0]+g[0]+g[2]+c[2]+c[1];




}
/* GBC */
else if(i==4){
/* GBC */
total=b[0]+b[2]+g[1]+g[2]+c[0]+c[1];

}
/* GCB */
else if(i==5){
/* GCB */
total=b[0]+b[1]+g[1]+g[2]+c[0]+c[2];

}


min=total;
}

for (i=1;i<6;i++)
for (j=5;j>=i;j--){
if(total[j-1] > total[j]){
temp=total[j-1];
total[j-1]=total[j];
total[j]=temp;}
}
for(k=0;k<6;k++){
if (min[k]==total[0]) {

switch( k) {
case 0 : printf("BCG %lu",min[k]);k=6;break;
case 1 : printf("BGC %lu",min[k]);k=6;break;
case 2 : printf("CBG %lu",min[k]);k=6;break;
case 3 : printf("CGB %lu",min[k]);k=6;break;
case 4 : printf("GBC %lu",min[k]);k=6;break;
case 5 : printf("GCB %lu",min[k]);k=6;break; }

}

}


} return 0;
}

[tan_Yui]

Hi, 59557RC.
Your C code should output one answer for each line,
so you have to insert '\n' into printf commands.
This may be only the improvement on avoiding 'Presentation Error'.

Except for above problem, your code outputs same answer as my AC code in the case of some input set.

First of all, try to improve printf commands.

Thank you.

[ahmad_h]

I keep getting WA for this simple problem....plz help me out...plzz cause this is getting frustrating

Code: Select all

/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: 45253TH 102 C++ "3'rd problem solved" */

#include <iostream>
using namespace std;

int main()
{	   
    char bin_comb[6][4] = {"021", "012", "201", "210", "102", "120"};
	unsigned long bins[3][3];
	unsigned long temp, no_shifts;
	char smallest;

	while(cin)
	{
		no_shifts = 0;
		smallest = 0;

		char i;
		for(i = 0; i < 9; i++)
			cin>>bins[i / 3][i % 3];
		
		for(i = 0; i < 3; i++)
		{
			temp = bins[i][0] + bins[i][1] + bins[i][2];
			no_shifts += temp - bins[i][bin_comb[0][i] - 48];
		}

		for(i = 1; i < 6; i++)
		{
			temp = 0;
			char k;
			for(k = 0; k < 3; k++)
			{
				temp += bins[k][0] + bins[k][1] + bins[k][2];
				temp = temp - bins[k][bin_comb[i][k] - 48];
			}

			if(temp < no_shifts)
			{
				no_shifts = temp;
				smallest = i;
			}
		}
		for(i = 0; i < 3; i++)
		{
			char out = (bin_comb[smallest][i] == 48)? 'B' : ((bin_comb[smallest][i] == 49)? 'G' : 'C');
			cout<<out;
		}
		cout<<" "<<no_shifts<<endl;
	}

	return 0;
}

/* @END_OF_SOURCE_CODE */

[Raj Ariyan]

Hi,
I think ur minimum cost generating calculation is not ok. This is a easy problem. Well there is six combination right ? so just check in which combination u get the minimum value and flag those combination. At last print the minimum value and those combination. Hope it helps. Dont make it complex, just check six combination.Thanx.

[ahmad_h]

Thank you Ariyan for looking into my problem....my code is doing exactly the same thing as you are saying. I calculate my cost like this for eg if you have this line...4 3 5 8 1 4 2 4 6...and the combination i'm looking at is BGC...my calculation comes out to be (3 + 5) + (8 + 4) + (2 + 4), I have commented my code, I'll be glad if somebody can take another look:

Code: Select all

/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: 45253TH 102 C++ "3'rd problem solved" */

#include <iostream>
using namespace std;

int main()
{
	//All possible 6 combinations where 0 - Brown, 1 - Green, 2 - Clear
	//In lexicographical order
	char bin_comb[6][4] = {"021", "012", "201", "210", "102", "120"};
	unsigned long bins[3][3];
	unsigned long temp, no_shifts;
	char smallest;

	while(cin)
	{
		//The minimum no. of shifts
		no_shifts = 0;
		//And its corresponding array loc in bin_comb
		smallest = 0;

		char i;
		for(i = 0; i < 9; i++)
			cin>>bins[i / 3][i % 3];
		
		//Setting bins as BCG - 021 (bin_comb[0], we calculate no. of shifts
		for(i = 0; i < 3; i++)
		{
			temp = bins[i][0] + bins[i][1] + bins[i][2];
			no_shifts += temp - bins[i][bin_comb[0][i] - 48];
		}
		
		//Running rest of the algo for rest 5 combinations
		for(i = 1; i < 6; i++)
		{
			temp = 0;
			char k;
			//Finding no of shifts for each combination
			for(k = 0; k < 3; k++)
			{
				temp += bins[k][0] + bins[k][1] + bins[k][2];
				temp = temp - bins[k][bin_comb[i][k] - 48];
			}

			//Setting new smallest no. of shifts if the combination leads to a lesser no. of shifts
			if(temp < no_shifts)
			{
				no_shifts = temp;
				smallest = i;
			}
		}
		//Printing the output remember 0 - Brown, 1 - Green, 2 - Clear
		for(i = 0; i < 3; i++)
		{
			char out = (bin_comb[smallest][i] == 48)? 'B' : ((bin_comb[smallest][i] == 49)? 'G' : 'C');
			cout<<out;
		}
		cout<<" "<<no_shifts<<endl;
	}

	return 0;
}

/* @END_OF_SOURCE_CODE */

[Iqram Mahmud]

/*COded on 23.02.05
By Fahim, NDC #102# */

#include <stdio.h>

long long sort();
long long ans[6];

void main() {
long long int a[3],b[3],c[3];
long long min;

while(scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld",&a[0], &a[1], &a[2],&b[0],&b[1],&b[2],&c[0],&c[1],&c[2])==9){
min=0;
ans[0]=b[0]+c[0]+a[2]+c[2]+a[1]+b[1];
ans[1]=b[0]+c[0]+a[1]+c[1]+a[2]+b[2];
ans[2]=b[2]+c[2]+a[0]+c[0]+a[1]+b[1];
ans[3]=b[2]+c[2]+a[1]+c[1]+a[0]+b[0];
ans[4]=b[1]+c[1]+a[0]+c[0]+a[2]+b[2];
ans[5]=b[1]+c[1]+a[2]+c[2]+a[0]+b[0];
min=sort();
if (min==ans[0]) printf("BCG %lld\n",min);
else if (min==ans[1]) printf("BGC %lld\n",min);
else if (min==ans[2]) printf("CBG %lld\n",min);
else if (min==ans[3]) printf("CGB %lld\n",min);
else if (min==ans[4]) printf("GBC %lld\n",min);
else if (min==ans[5]) printf("GCB %lld\n",min);
}
}


long long sort() {

int j;
long long key,min=10000000;

for(j=0;j<6;j++) {
key=ans[j];
if(key<min) min = key;
}
return min;

}

Code: Select all

[quote]I am confused what is my fault?[/quote]

[gladiatorcn]

did u alphabetically list ur first answer? note that the order of input s bgc rather than bcg.
here s my codes, wishing to help:
#include <stdio.h>

int main()
{
long b[3][3];
int i,j,k;
long move,minmove;
char s[4];

while(scanf("%d%d%d%d%d%d%d%d%d",
&b[0][0],&b[0][2],&b[0][1],&b[1][0],&b[1][2],&b[1][1],&b[2][0],&b[2][2],&b[2][1])==9)
{
minmove=2147483647;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
for(k=0;k<3;k++)
{
if(i==j||k==i||j==k) continue;
move=b[1]+b[2]+b[0][j]+b[2][j]+b[0][k]+b[1][k];
if(move<minmove)
{
minmove=move;
s[0]=i==0?'B':(i==1?'C':'G');
s[1]=j==0?'B':(j==1?'C':'G');
s[2]=k==0?'B':(k==1?'C':'G');
s[3]='\0';
}
}
printf("%s %d\n",s,minmove);
}
return 0;
}

[nch_prakash]

I don't understand the problem with this code.. Can someone help please...

Code: Select all

#include <stdio.h>

int main(void)
{
	int b[3];
	int g[3];
	int c[3];

	int m, l = 321222, i = 0;

	char s[][4] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};
	
	while(1)
	{
		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]);
		if (feof(stdin))
			break;
		
		m = b[1]+b[2]+c[0]+c[2]+g[0]+g[1];	
		if (l > m) { l = m; i = 0; }		
		m = b[1]+b[2]+g[0]+g[2]+c[0]+c[1];	
		if (l > m) { l = m; i = 1; }		
		m = c[1]+c[2]+b[0]+b[2]+g[0]+g[1];	
		if (l > m) { l = m; i = 2; }		
		m = c[1]+c[2]+g[0]+g[2]+b[0]+b[1];	
		if (l > m) { l = m; i = 3; }		
		m = g[1]+g[2]+b[0]+b[2]+c[0]+c[1];	
		if (l > m) { l = m; i = 4; }		
		m = g[1]+g[2]+c[0]+c[2]+b[0]+b[1];	
		if (l > m) { l = m; i = 5; }		

		printf("%s %d\n", s[i], l);
		l = 321222;
		i = 0;
	}	
}

[jakabjr]

you problem might be the break. if there aren't any triling blank spaces in the input, your code will break before processing the last input line (I'm not sure it's the case though). Generally, I test the scanf if it has read all it's variables (==9 in this case).

Hope that helps.

[Gustavo]

This is my code for de 102 problem!!!! I sure it's right but always say W.A!!!! Can some one help me!!!!!!

Here is my code!!!!!


#include<stdio.h>

void main(){
long i, m[9],config;
long t,T,g,b,c,xx;
do{
xx = scanf("%d %d %d %d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5],&m[6],&m[7],&m[8]);
if(xx!=EOF){
T=2200000000;
for(i=0;i<6;i++){
if(i==0){
b=m[3]+m[6];
c=m[2]+m[8];
g=m[1]+m[4];
t=g+b+c;
if(t<T){
T=t;
config=0;
}
continue;
}
if(i==1){
b=m[3]+m[6];
g=m[1]+m[7];
c=m[2]+m[5];
t=g+b+c;
if(t<T){
config=1;
T=t;
}
continue;
}
if(i==2){
c=m[5]+m[8];
b=m[0]+m[6];
g=m[1]+m[4];
t=g+b+c;
if(t<T){
T=t;
config=2;
}
continue;
}
if(i==3){
c=m[5]+m[8];
g=m[1]+m[7];
b=m[0]+m[3];
t=g+b+c;
if(t<T){
T=t;
config=3;
}
continue;
}
if(i==4){
g=m[4]+m[7];
b=m[0]+m[6];
c=m[2]+m[5];
t=g+b+c;
if(t<T){
T=t;
config=4;
}
continue;
}
if(i==5){
g=m[4]+m[7];
c=m[2]+m[8];
b=m[0]+m[3];
t=g+b+c;
if(t<T){
T=t;
config=5;
}
continue;
}
}
if(config==0)
printf("BCG");
if(config==1)
printf("BGC");
if(config==2)
printf("CBG");
if(config==3)
printf("CGB");
if(config==4)
printf("GBC");
if(config==5)
printf("GCB");
printf(" %d\n",T);
}
}while(xx!=EOF);
}

[jakabjr]

First of all, the way you posted the code is making it difficult to read. Next time enclose it within [code and [/code (with ending ]).
I've rea your code, and can't find an output mistake. I can tell you though you don't need the for and if's it encloses (your code runs the same without them), your code is too long and variable names are all unexpressive. If you can spare some time, look at this topic:
http://online-judge.uva.es/board/viewtopic.php?t=8033

By the way, pease check if there are allready opened topics that relate to your problem, and write there if they exist.
Also if you give me a mail adress I could send you an e-book I'm reading about 'how' to code (good book so far).

Bottom line is I'm sorry I can't find an error, but if you write shorter, more expressive code, it will be easier to debug.

[KvaLe]

I don't know what mistake is in your code, but I prefare U to solve this problem with recursion. I wrote it and it's length isn't more then 30 lines.

[Roby]

Help me please!
What's wrong with my code?

Here my code:

Code: Select all

// Problem #102 Volume 2 - Ecological Bin Packing, UVa Online Judge
// Created by Roby on May 27, 2005

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

typedef struct data * ptr;
typedef struct data
{
 char bins[4];
 long total;
 ptr next;
};

ptr head, curr, tail;

void Create( void )
{
 head = curr = tail = NULL;
}

void Popall( void )
{
 if ( head != NULL )
 {  curr = head;
    while ( head != NULL )
    {  head = head->next;
       free( curr );
       curr = head;
    }
 }
}

void Insert( char bin1, char bin2, char bin3, long total )
{
 ptr p = NULL;
 curr = ( ptr ) malloc ( sizeof ( data ) );

 curr->bins[0] = bin1;
 curr->bins[1] = bin2;
 curr->bins[2] = bin3;
 curr->bins[3] = '\x0';
 curr->total = total;
 curr->next = NULL;

 if ( head == NULL )
    head = tail = curr;
 else
 {
    if ( ( curr->total ) < ( head->total ) )
    {
       curr->next = head;
       head = curr;
    }

    else if ( ( curr->total ) > ( tail->total ) )
    {
       tail->next = curr;
       tail = curr;
    }
    else
    {
       // find the suitable position
       for ( p = head; strcmp( curr->bins, p->next->bins ) > 0; p = p->next );

       // insert the curr
       curr->next = p->next;
       p->next = curr;
    }
 }
}

int main()
{
 #ifndef ONLINE_JUDGE
    freopen( "102.IN", "r", stdin );
    freopen( "102.OUT", "w", stdout );
 #endif

 long i = 0, j = 0, k = 0, total = 0, ctr = 0, ti = 0, tj = 0, tk = 0;
 long bin1[3] = { 0 }, bin2[3] = { 0 }, bin3[3] = { 0 };

 while ( scanf( "%ld%ld%ld%ld%ld%ld%ld%ld%ld", &bin1[0], &bin2[0], &bin3[0], &bin1[2], &bin2[2], &bin3[2], &bin1[1], &bin2[1], &bin3[1] ) == 9 )
 {
    Create();

    // permutate all the combination ( i realize it only 6 )
    for ( i = 0; i < 3; i++ )
       for ( j = 0; j < 3; j++ )
	  for ( k = 0; k < 3; k++ )
	     if ( j != i && k != i && k != j )
	     {  total = bin2[i] + bin3[i] + bin1[j] + bin3[j] + bin1[k] + bin2[k];
		switch ( i )
		{  case 0 : ti = i + 66; break;
		   case 1 : ti = i + 66; break;
		   case 2 : ti = i + 69; break;
		}
		switch ( j )
		{  case 0 : tj = j + 66; break;
		   case 1 : tj = j + 66; break;
		   case 2 : tj = j + 69; break;
		}
		switch ( k )
		{  case 0 : tk = k + 66; break;
		   case 1 : tk = k + 66; break;
		   case 2 : tk = k + 69; break;
		}
		Insert( ti, tj, tk, total );
	     }

    if ( ctr > 0 )
       printf( "\n" );

    printf( "%s %ld", head -> bins, head -> total ); ctr++;

    Popall();
 }

 return 0;
}

I got this Runtime Error (SIGSEGV)[/code]

[jakabjr]

the problem is it's too long & too complicated
pls see this: http://online-judge.uva.es/board/viewtopic.php?t=8033