102 - Ecological Bin Packing
Moderator: Board moderators
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 );
}
}
#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 );
}
}
-
- 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;
}
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;
}
-
- 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){
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>
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>
-
- 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>
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
-
- New poster
- Posts: 4
- Joined: Fri Apr 05, 2002 2:00 am
- Location: HeBei,China
Thank you.
Thank you.
prob 102
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]
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]
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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.........
I/O works 2 times faster after I've changed cin/cout to scanf/prinf, but it is still too slow.........
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]
(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]
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
-novice
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..
[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
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
-
- 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.