102 - Ecological Bin Packing

[konsept]

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]

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]

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]

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){
return total-bin[1][r1]-bin[2][r2]-bin[3][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]

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>

[Adrian Kuegel]

Your output is correct.

[FireDragon]

Thank you.

[jydy]

The following is my code
but I get WA's
please advise, thanks!
[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]

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]

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]

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]

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]

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..

[Stefan Pochmann]

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]

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.