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

Post Reply
konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Location: Waterloo, Canada
Contact:

Post by konsept » Wed Dec 19, 2001 8:32 pm

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

Post by bigredteam2000 » Thu Dec 20, 2001 5:18 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

Post by cyfra » Thu Dec 20, 2001 1:09 pm

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

Post by FireDragon » Fri Apr 05, 2002 5:21 pm

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
New poster
Posts: 4
Joined: Fri Apr 05, 2002 2:00 am
Location: HeBei,China

Post by FireDragon » Sat Apr 06, 2002 5:58 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Apr 07, 2002 12:26 pm

Your output is correct.

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

Thank you.

Post by FireDragon » Tue Apr 09, 2002 3:38 am

Thank you.

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

prob 102

Post by jydy » Sat Apr 27, 2002 4:45 am

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Apr 27, 2002 7:37 am

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)

Post by minskcity » Wed May 15, 2002 10:34 am

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

Post by minskcity » Wed May 15, 2002 12:32 pm

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?

Post by Fresh » Wed May 15, 2002 4:48 pm

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 :wink:

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

102 - Ecological Bin Packing

Post by zerocool » Thu May 16, 2002 9:06 am

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:

Post by Stefan Pochmann » Thu May 16, 2002 10:27 am

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

Post by Ivan Golubev » Fri May 17, 2002 2:59 am

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.

Post Reply

Return to “Volume 1 (100-199)”