## 102 - Ecological Bin Packing

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Contact:
Can someone please tell what is wrong with this problem, because I can't figure out why the online judge fails to accept it.

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

int box[4][4];

int bestcost;
char bestbin[16];

int check( int a,int b,int c ){
int cost=0;

cost+=box[1][1]+box[1][2]+box[1][3]-box[1][a];
cost+=box[2][1]+box[2][2]+box[2][3]-box[2];
cost+=box[3][1]+box[3][2]+box[3][3]-box[3][c];

return cost;
}

void main( void ){

while ( scanf( "%d %d %d", &box[1][1],&box[1][2],&box[1][3] )>0 ){
scanf( "%d %d %d", &box[2][1],&box[2][2],&box[2][3] );
scanf( "%d %d %d", &box[3][1],&box[3][2],&box[3][3] );

bestcost=1000000;

if ( check(1,3,2)<bestcost ){
bestcost=check(1,3,2);
strcpy( bestbin, "BCG" );
}

if ( check(1,2,3)<bestcost ){
bestcost=check(1,2,3);
strcpy( bestbin, "BGC" );
}

if ( check(3,1,2)<bestcost ){
bestcost=check(3,1,2);
strcpy( bestbin, "CBG" );
}

if ( check(3,2,1)<bestcost ){
bestcost=check(3,2,1);
strcpy( bestbin, "CGB" );
}

if ( check(2,1,3)<bestcost ){
bestcost=check(2,1,3);
strcpy( bestbin, "GBC" );
}

if ( check(2,3,1)<bestcost ){
bestcost=check(2,3,1);
strcpy( bestbin, "GCB" );
}

printf( "%s %dn", bestbin, bestcost );
}

}

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am
We thought we got it but the judges did not.
I am trying all the six different possibilities.
I still donot understand why they talk about dynamic programming at the beginning of the problem.

#include<iostream.h>

int main()
{
long int b1,g1,c1;
long int b2,g2,c2;
long int b3,g3,c3;
long int sum[7];
int i;
int indexofmin;
long int min;

while(cin>>b1)
{
cin>>g1>>c1;
cin>>b2>>g2>>c2;
cin>>b3>>g3>>c3;

sum[1] = c1+g1+b2+c2+b3+g3;
sum[2] = g1+c1+b2+g2+b3+c3;
sum[3] = b1+g1+g2+c2+b3+c3;
sum[4] = b1+g1+b2+c2+g3+c3;
sum[5] = b1+c1+g2+c2+b3+g3;
sum[6] = b1+c1+g2+b2+g3+c3;

min = sum[1];
indexofmin = 1;
for(i = 2; i<=6;i++)
{
if( min>=sum)
{
min = sum;
indexofmin = i;

}
}
switch(indexofmin)
{
case 1:
cout<<"BGC "<<min<<endl;
break;
case 2:
cout<<"BCG "<<min<<endl;
break;
case 3:
cout<<"CBG "<<min<<endl;
break;
case 4:
cout<<"CGB "<<min<<endl;
break;
case 5:
cout<<"GBC "<<min<<endl;
break;
case 6:
cout<<"GCB "<<min<<endl;
break;
}
}

return 0;
}

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi

I know what's wrong with your program.

If there are two posibilities you have to print this one which is earlier in alphabetical order.

And your program will write BGC instead of BCG. (if they have the same values).
You have to change 2 cases (1 and 2) in your program and everything will be OK.

FireDragon
New poster
Posts: 4
Joined: Fri Apr 05, 2002 2:00 am
Location: HeBei,China
Can someone tell me what is wrong with the program.If there are two posibilities I do print the one which is earlier in alphabetical order.
Thank you.

#include<stdio.h>
#include<iostream.h>
long r1,r2,r3;
long bin[4][4];
long total;
char mark[5]=" BCG";

long count(long r1,long r2,long r3){
}

void main(){
while(!feof(stdin)){
long i,j,o,t,min=2147483647;
for (i=1;i<=3;i++) t=scanf("%ld%ld%ld",&bin[1],&bin[3],&bin[2]);//Not the ori_order
if (t!=3) break;
total=0;
for (i=1;i<=3;i++) for (j=1;j<=3;j++) total+=bin[j];
for (i=1;i<4;i++)
for (j=1;j<4;j++)
if (i!=j) for (o=1;o<4;o++) if (o!=i&&o!=j)
if ((t=count(i,j,o))<min) {
min=t;
r1=i;r2=j;r3=o;
}
cout<<mark[r1]<<mark[r2]<<mark[r3]<<' '<<min<<endl;
}
}

<font size=-1>[ This Message was edited by: FireDragon on 2002-04-05 17:30 ]</font>

FireDragon
New poster
Posts: 4
Joined: Fri Apr 05, 2002 2:00 am
Location: HeBei,China
I still don't know why I got WA.
Here are some of my test data.

1 2 3 4 5 6 7 8 9
1000 200 1500 350 5000 1000 1000 2000 13000
5 10 5 20 10 5 10 20 10
60 20 1000 1000 60 20 10000 20 500
20 1000 50 2000 50 500 1500 20 3000
20 1000 50 2000 50 5000 1500 20 300

And My output.
BCG 30
BGC 6050
CBG 50
CGB 1620
GBC 2140
GCB 2440

_________________
I failed over and over and over again.
And that's why I succeed.

<font size=-1>[ This Message was edited by: FireDragon on 2002-04-06 17:59 ]</font>

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Your output is correct.

FireDragon
New poster
Posts: 4
Joined: Fri Apr 05, 2002 2:00 am
Location: HeBei,China

### Thank you.

Thank you.

jydy
New poster
Posts: 5
Joined: Sun Apr 07, 2002 2:00 am

### prob 102

The following is my code
but I get WA's
[c]#include<stdio.h>
#define MAX 32767
int main()
{
int b1,b2,b3;
int g1,g2,g3;
int c1,c2,c3;
int moves[6],min;
int i, switcher;

while(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9)
{
min=MAX;

moves[0]=b1+c1+b2+g2+g3+c3;
moves[1]=b1+c1+g2+c2+b3+g3;
moves[2]=b1+g1+b2+c2+g3+c3;
moves[3]=b1+g1+g2+c2+b3+c3;
moves[4]=g1+c1+b2+c2+b3+g3;
moves[5]=g1+c1+b2+g2+b3+c3;

for(i=0;i<6;i++)
{
if(min>=moves)
{
min=moves;
switcher=i;
}
}

switch(switcher)
{
case 0:
printf("GCB %d",min);
break;
case 1:
printf("GBC %d",min);
break;
case 2:
printf("CGB %d",min);
break;
case 3:
printf("CBG %d",min);
break;
case 4:
printf("BGC %d",min);
break;
case 5:
printf("BCG %d",min);
break;
}

}

return 0;
}[/c]

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Maybe it's because you assume a fairly small maximum. Read the problem statement again, it says "The total
number of bottles will never exceed 2^31".

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### What is the fastest way of input/output? (102)

My program runs 5000 times faster than input/output. Is there any way to fix it????

I/O works 2 times faster after I've changed cin/cout to scanf/prinf, but it is still too slow.........

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### Anybody knows fast way of input??

This code (just input) takes 0.140s, while the best time for this problem is 0.010s.

(output works quite fast)

[cpp]#include <stdio.h>

int main(){

unsigned long data00,data01,data02;
unsigned long data10,data11,data12;
unsigned long data20,data21,data22;

while(scanf("%d %d %d %d %d %d %d %d %d",&data00,
&data01,&data02,&data10,&data11,&data12,&data20,
&data21,&data22) == 9){};

return 0;
}[/cpp]

Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

### iostream vs stdio?

I don't know how some people solved this problem just in 0.010s. But honestly to say, your time still fast since mine is 0.380s. From my experince, 'cin' is much faster than 'scanf' but 'cout' is slower than 'printf' so use 'cin' for input and 'printf' for output. For those who solved this problem in 0.010s, plz share your algo with us.

-novice

zerocool
New poster
Posts: 7
Joined: Wed May 15, 2002 10:30 am
Location: Kaohsiung,Taiwan
Contact:

### 102 - Ecological Bin Packing

The following my source code for P.102
[cpp]
#include <iostream>
using namespace std ;
void main()
{
unsigned long k1=0, data[9]={0} ;
char *c ;
while ( cin >> data[0] ) {
double min=2147483648 , sum=0 ;
sum += data[0] ;
for( k1=1 ; k1<9 ; k1++ ) {
cin >> data[k1] ;
sum += data[k1] ;
}
if ( min >= (sum-data[1]-data[5]-data[6]) )
c = "GCB " ,
min = sum-data[1]-data[5]-data[6] ;
if ( min >= (sum-data[1]-data[3]-data[8]) )
c = "GBC " ,
min = sum-data[1]-data[3]-data[8] ;
if ( min >= (sum-data[2]-data[4]-data[6]) )
c = "CGB " ,
min = sum-data[2]-data[4]-data[6] ;
if ( min >= (sum-data[2]-data[3]-data[7]) )
c = "CBG " ,
min = sum-data[2]-data[3]-data[7] ;
if ( min >= (sum-data[0]-data[4]-data[8]) )
c = "BGC " ,
min = sum-data[0]-data[4]-data[8] ;
if ( min >= (sum-data[0]-data[5]-data[7]) )
c = "BCG " ,
min = sum-data[0]-data[5]-data[7] ;
cout << c << min << endl;
}
}
[/cpp]
I cannot find any bug in it, but the judge always says "Wrong answer".
Anybody could help me what happen ?
Thanks..
A mediocrityboy

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
My guess is that they optimized IO by reading/writing large blocks of data in raw format and parsing/printing it on their own. Since I'm too old for that kind of optimization, I'm happy with my much slower (but still way under the limit) time using simple cin/cout/scanf/printf...

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Stefan absolutely right -- if you want fast I/O then forget about cin/scanf. Use at least gets(), it works much faster. And parse input by your own (again, without something like strtok()). I've used read()/write() in my solution, however, I don't know is it the fastest way possible -- I haven't got 0.010... yet.