## 102 - Ecological Bin Packing

Moderator: Board moderators

Anunnaki
New poster
Posts: 7
Joined: Thu Dec 25, 2008 11:14 pm

### Re: Wrong Answer for 102

Can someone explain to me why "CBG" is alphabetically superior to "BGC"?

Edit: Never mind, I was doing it wrong.

JINX
New poster
Posts: 3
Joined: Sat Jul 19, 2008 3:36 pm

### Re: 102, WA. Help me.

Hi,What's wrong with my code? I have got lots of WAs ,frustrated.
It seems the algo is right.

Code: Select all

``````#include <iostream>
#include <map>
using namespace std;

long long Color[3][3];
long long SumColor[3];
map<int ,char> M;

bool ColorUsed[3];
int	 BinColor[3];
//output
int  MinBinColor[3];
long long MinMove;

void GetInput()
{

for (int i = 0 ;i<3 ;i++)
{
SumColor[i] = 0;
ColorUsed[i] = false;
BinColor[i] = 0;
}

MinMove = (long long)1<<31 ;

for (int i = 0 ;i<3 ;i++)
{
cin>>Color[i][0]>>Color[i][2]>>Color[i][1];
SumColor[i] = Color[i][0]+Color[i][2]+Color[i][1];
}

}

void Process(int bin)
{
if( bin == 3 )
{
long long TmpMove =0;
for (int j = 0; j<3 ;j++)
{
TmpMove += SumColor[j]-Color[j][BinColor[j]];
}

if (TmpMove < MinMove)
{
MinMove = TmpMove;
for (int j = 0 ; j<3 ; j++)
{
MinBinColor[j] = BinColor[j];
}

}
return;
}

for (int i = 0 ; i<3 ; i++)
{
if(ColorUsed[i] == false)
{
ColorUsed[i] = true;
BinColor[bin] = i;
Process(bin+1);
ColorUsed[i] = false;
}

}

}

void SetOutput()
{
for (int i = 0 ; i<3 ; i++)
{
cout<<M[MinBinColor[i]];
}
cout<<' ';
cout<<MinMove;
cout<<endl;

}

int main()
{

M[0] = 'B';
M[1] = 'C';
M[2] = 'G';

while(!cin.eof())
{
GetInput();
Process(0);
SetOutput();
}

return 0;
}``````

ror
New poster
Posts: 2
Joined: Mon May 18, 2009 1:34 am

### 102, WA

Hi,

I keep getting a wrong answer for 102. I've even diffed my output with some of the other posts on this topic on the forum, to only find no difference. This is driving me crazy, I can't find the issue anywhere, all my solutions seem correct, which leaves me to believe it's a formatting issue somehow, but where? Have I got my alphabetization orders correct?

Code: Select all

``````#include <iostream>
#include <string>

using namespace std;
int solution (int a, int b, int c, const int (&solarray)[9]) {
return solarray[a]+solarray[b]+solarray[c];
};

string solution_id_to_string(int solID) {
string out;
switch (solID) {
case 1:
out="BCG";
break;
case 2:
out="BGC";
break;
case 3:
out="CBG";
break;
case 4:
out="CGB";
break;
case 5:
out="GBC";
break;
case 6:
out="GCB";
break;
default: out="";
}
return out;
};

int main () {
int input[9];
int line_max = 1000;
int solves[line_max][2];
int line_no=0;

while((cin >> input[0] >> input[1] >> input[2] >> input[3] >> input[4] >> input[5] >> input[6] >> input[7] >> input[8]) and (line_no < line_max)) {

int total = input[0]+input[1]+input[2]+input[3]+input[4]+input[5]+input[6]+input[7]+input[8];

int max = solution(0,5,7,input);
int solution_id=1;
if (max<solution(0,4,8,input)) {max=solution(0,4,8,input);solution_id=2;};
if (max<solution(2,3,7,input)) {max=solution(2,3,7,input);solution_id=3;};
if (max<solution(2,4,6,input)) {max=solution(2,4,6,input);solution_id=4;};
if (max<solution(1,3,8,input)) {max=solution(1,3,8,input);solution_id=5;};
if (max<solution(1,5,6,input)) {max=solution(1,5,6,input);solution_id=6;};

//cout << solution_id << "\t" << total -max <<endl;
solves[line_no][0]=solution_id;
solves[line_no][1]=total-max;
line_no++;
}

for(int i=0;i<line_no;i++) {
cout << solution_id_to_string(solves[i][0]) << " " << solves[i][1] << endl;
}

return 0;
}
``````

ror
New poster
Posts: 2
Joined: Mon May 18, 2009 1:34 am

### Re: 102, WA

OK well I've fixed it, I just had to re-write it so that output is concurrent with input. I don't know if this is a requirement, or whether I was simply getting my line maximum way too small (I did try some very large numbers though!) but just processing a line at a time has fixed this problem.

rahat089
New poster
Posts: 2
Joined: Sat May 02, 2009 5:03 pm

### Re: 102, WA

#include<stdio.h>
int bin[3][3]={0};
int moves[6]={0};
int main()
{
int min,i,index;
while(scanf("%d%d%d%d%d%d%d%d%d",&bin[0][0],&bin[0][1],&bin[0][2],&bin[1][0],&bin[1][1],&bin[1][2],&bin[2][0],&bin[2][1],&bin[2][2])==9)
{
min=0;
moves[0]=bin[0][1]+bin[0][2]+bin[1][0]+bin[1][2]+bin[2][0]+bin[2][1];
moves[1]=bin[0][1]+bin[0][2]+bin[1][0]+bin[1][1]+bin[2][0]+bin[2][2];
moves[2]=bin[0][0]+bin[0][2]+bin[1][2]+bin[1][1]+bin[2][0]+bin[2][1];
moves[3]=bin[0][0]+bin[0][2]+bin[1][0]+bin[1][1]+bin[2][2]+bin[2][1];
moves[4]=bin[0][0]+bin[0][1]+bin[1][2]+bin[1][1]+bin[2][0]+bin[2][2];
moves[5]=bin[0][0]+bin[0][1]+bin[1][2]+bin[1][0]+bin[2][2]+bin[2][1];
min=moves[0];
index=0;
for(i=1;i<6;i++)
{
if(moves<min)
{
min=moves;
index=i;
}
}
if(index==0)
printf("BCG");
else if(index==1)
printf("BGC");
else if(index==2)
printf("GBC");
else if(index==3)
printf("GCB");
else if(index==4)
printf("CBG");
else
printf("CGB");

printf(" %d\n",min);
}

return 0;
}

i am also gettin WA in this code...can u gys plz help me out?????

Jordi Aranda
New poster
Posts: 13
Joined: Wed Apr 29, 2009 11:37 am
Location: Barcelona

### Re: 102, WA

Some simple cases helped me to fix my errors:
input

Code: Select all

`` 0 1 0 0 0 1 1 0 0 ``
output

Code: Select all

`` GCB 0 ``
input

Code: Select all

`` 1 0 0 0 1 0 0 0 1 ``
output

Code: Select all

`` BGC 0 ``
input

Code: Select all

`` 0 0 1 1 0 0 0 1 0 ``
output

Code: Select all

`` CBG 0 ``
Anyways, not too many problems to get A
Born to be wild

ashraf_iut
New poster
Posts: 3
Joined: Thu Jan 22, 2009 9:16 pm

### 102

I am getting Wrong Answer !!But I am getting correct answer for mostly all possible critical Input...plz help me...

#include<iostream>
using namespace std;

int main(){
//freopen("102.txt","r",stdin);
long g[3],b[3],c[3],sum,min;
char str[5];
while((scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld",&b[0],&g[0],&c[0],&b[1],&g[1],&c[1],&b[2],&g[2],&c[2]))==9){
sum=0;
min=3000000;

sum=b[1]+b[2]+c[0]+c[2]+g[0]+g[1];
if(sum<min){
min=sum;
strcpy(str,"BCG");
}

sum=b[1]+b[2]+g[0]+g[2]+c[0]+c[1];
if(sum<min){
min=sum;
strcpy(str,"BGC");
}

sum=c[1]+c[2]+b[0]+b[2]+g[0]+g[1];
if(sum<min){
min=sum;
strcpy(str,"CBG");
}
sum=c[1]+c[2]+g[0]+g[2]+b[0]+b[1];
if(sum<min){
min=sum;
strcpy(str,"CGB");
}
sum=g[1]+g[2]+b[0]+b[2]+c[0]+c[1];
if(sum<min){
min=sum;
strcpy(str,"GBC");
}
sum=g[1]+g[2]+c[0]+c[2]+b[0]+b[1];
if(sum<min){
min=sum;
strcpy(str,"GCB");
}
printf("%s %lld\n",str,min);
}
return 0;
}

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

### Re: 102

you just change long int to long long int and submit.

i got AC so you supposed to get AC

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

### Re: 102, WA

Code: Select all

``````//THIS CODE HAS BEEN WRITTEN BY CODEWORRIOR(SHIVMITRA MISHRA)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>

using namespace std;

typedef long long int64;

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define A first
#define B second
#define PII pair<int,int>
#define VI vector<int>
#define CLR(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define pb push_back

typedef long long int64;

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","wt",stdout);
int64 b1,c1,g1,b2,c2,g2,b3,c3,g3;
int64 total[8];
//int64 cases=0;
while(scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9)
{

CLR(total,0);

//1
total[5]=c1+g1+b2+c2+b3+g3;
//2
total[6]=c1+g1+b2+g2+b3+c3;
//3
total[2]=b1+c1+g2+c2+b3+g3;
//4
total[1]=b1+c1+b2+g2+c3+g3;
//5
total[4]=b1+g1+c2+g2+b3+c3;
//6
total[3]=b1+g1+b2+c2+c3+g3;
//FOR(i,1,6)
//printf("%d\n",total[i]);

int64 ans=1<<20,pos=1;
FOR(i,1,6)
{
ans=min(total[i],ans);
if(ans==total[i])
pos=i;

}
switch (pos)
{
case 1:
{printf("GCB %d",total[1]);break;}
case 2:
{printf("GBC %d",total[2]);break;}
case 3:
{printf("CGB %d",total[3]);break;}
case 4:
{printf("CBG %d",total[4]);break;}
case 5:
{printf("BGC %d",total[5]);break;}
case 6:
{printf("BCG %d",total[6]);break;}
}
printf("\n");
}
}

``````

getting correct output fr all the cases i could find in forums.. bt getting WA...plzz help..

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 102, WA

hey u should remind this line......
If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.
may be your program does not solve this for same minimum moves ......

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

### Re: 102, WA

who can tell me if all input is zero what string should be output?

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

### 102 WA who can help me!!!

#include<iostream>
#include<cstdio>

using namespace std;

long bo[3][3],maxs,maxt,cot[3],cos[3],maxa;
bool flag[3];
char cr[3]={'B','G','C'};

void se(int b)
{
if(b==0){int i;
for(i=0;i<3;++i)
{
maxs=0;

flag=false;
maxs+=(bo[1]+bo[2]);

cot=i;

se(1);
flag=true;
}}
else if(b==1)
{ int i;
for(i=0;i<3;++i)
if(flag)
{
maxs+=(bo[0]+bo[2]);
flag=false;cot=i;
se(2);flag=true;
maxs-=(bo[0]+bo[i][2]);
}
}
else if(b==2){int i;
for(i=0;i<3;++i)
if(flag[i])
{maxs+=(bo[i][0]+bo[i][1]);
cot=i;
if(maxs<=maxt)
{if(maxs<maxt)
{maxt=maxs;
for(int i=0;i<3;++i){cos[i]=cot[i];}
}
else {
for(int i=0;i<3;++i)
{if(cr[cot[i]]<=cr[cos[i]])
{
if(cr[cot[i]]<=cr[cos[i]])
for(int j=i;j<3;++j)cos[j]=cot[j];
}else break;}
}
}maxs-=(bo[i][0]+bo[i][1]);
}
}
}
int main()
{
int i,j;

while(cin>>bo[0][0]>>bo[1][0]>>bo[2][0]>>bo[0][1]
>>bo[1][1]>>bo[2][1]>>bo[0][2]>>bo[1][2]>>bo[2][2])
{
for(int i=0;i<3;++i)flag[i]=true;
maxt=0xfffffff;se(0);
for(int i=0;i<3;++i)printf("%c",cr[cos[i]]);
printf(" %lld\n",maxt);
}
}
I've test many data myself ,but I can't find out the error.
despite my complicated code

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

### Re: 102 WA who can help me!!!

Code: Select all

``````#include<iostream>
#include<cstdio>

using namespace std;

long bo[3][3],maxs,maxt,cot[3],cos[3],maxa;
bool flag[3];
char cr[3]={'B','G','C'};

void se(int b)
{
if(b==0){int i;
for(i=0;i<3;++i)
{
maxs=0;

flag[i]=false;
maxs+=(bo[i][1]+bo[i][2]);

cot[b]=i;

se(1);
flag[i]=true;
}}
else if(b==1)
{  int i;
for(i=0;i<3;++i)
if(flag[i])
{
maxs+=(bo[i][0]+bo[i][2]);
flag[i]=false;cot[b]=i;
se(2);flag[i]=true;
maxs-=(bo[i][0]+bo[i][2]);
}
}
else if(b==2){int i;
for(i=0;i<3;++i)
if(flag[i])
{maxs+=(bo[i][0]+bo[i][1]);
cot[b]=i;
if(maxs<=maxt)
{if(maxs<maxt)
{maxt=maxs;
for(int i=0;i<3;++i){cos[i]=cot[i];}
}
else {
for(int i=0;i<3;++i)
{if(cr[cot[i]]<=cr[cos[i]])
{
if(cr[cot[i]]<=cr[cos[i]])
for(int j=i;j<3;++j)cos[j]=cot[j];
}else break;}
}
}maxs-=(bo[i][0]+bo[i][1]);
}
}
}
int main()
{
int i,j;

while(cin>>bo[0][0]>>bo[1][0]>>bo[2][0]>>bo[0][1]
>>bo[1][1]>>bo[2][1]>>bo[0][2]>>bo[1][2]>>bo[2][2])
{
for(int i=0;i<3;++i)flag[i]=true;
maxt=0xfffffff;se(0);
for(int i=0;i<3;++i)printf("%c",cr[cos[i]]);
printf(" %lld\n",maxt);
}
}
``````

clifford1313
New poster
Posts: 1
Joined: Tue Nov 02, 2010 5:20 pm

### Re: 102

Hi there,

I can't see what's wrong with my code since I continue getting TL status :

Code: Select all

``````import java.io.IOException;

public class Main {

public final static int BCG = 0;
public final static int BGC = 1;
public final static int CBG = 2;
public final static int CGB = 3;
public final static int GBC = 4;
public final static int GCB = 5;
long[] moves = new long[6];

byte lin[] = new byte[maxLg];
int lg = 0, car = -1;

try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n')) {
break;
}
lin[lg++] += car;
}
} catch (IOException e) {
return (null);
}

if ((car < 0) && (lg == 0)) {
return (null);  // eof
}
return (new String(lin, 0, lg));

}

public void run() {
String s = "", result = "";
boolean first = true;
while ((s = readln(255)) != null) {
String splitted[] = s.trim().split(" +");
if (splitted.length != 9) {
continue;
}
long b1B = Long.parseLong(splitted[0]);
long b1G = Long.parseLong(splitted[1]);
long b1C = Long.parseLong(splitted[2]);
long b2B = Long.parseLong(splitted[3]);
long b2G = Long.parseLong(splitted[4]);
long b2C = Long.parseLong(splitted[5]);
long b3B = Long.parseLong(splitted[6]);
long b3G = Long.parseLong(splitted[7]);
long b3C = Long.parseLong(splitted[8]);
moves[BCG] = b1G + b1C + b2B + b2G + b3B + b3C;
moves[BGC] = b1G + b1C + b2C + b2B + b3G + b3B;
moves[CBG] = b1B + b1G + b2C + b2G + b3B + b3C;
moves[CGB] = b1B + b1G + b2B + b2C + b3C + b3G;
moves[GBC] = b1B + b1C + b2C + b2G + b3B + b3G;
moves[GCB] = b1B + b1C + b2B + b2G + b3C + b3G;
long mresult = moves[BCG];
int morder = BCG;
for (int i = 1; i < 6; i++) {
if (moves[i] < mresult) {
mresult = moves[i];
morder = i;
}
}
if(!first) result += "\n";
if (morder == BCG) {
result += "BCG";
} else if (morder == BGC) {
result += "BGC";
} else if (morder == CBG) {
result += "CBG";
} else if (morder == CGB) {
result += "GCB";
} else if (morder == GBC) {
result += "GBC";
} else if (morder == GCB) {
result += "GCB";
}
result += " " + mresult;
first = false;
}
System.out.println(result);
}

public static void main(String[] args) {
Main m = new Main();
m.run();
}
}``````

russel07
New poster
Posts: 1
Joined: Sat Dec 04, 2010 9:38 pm

### Re: 102

Hi, i cant find anything wrong with this code........ can anyone telllllll?

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;

int main()
{
long long a[15][15],b[20],c[100],x;
int i,j,k,p;
map<int,string> mp;
while(cin>>x)
{
b[0]=x;
for(i=1;i<9;i++)
cin>>b;
for(i=0;i<9;i++)
{
p=i%3;
if(i<3)
a[p][0]=b[i+3]+b[i+6];
else if(i>=3&&i<6)
a[p][1]=b[i-3]+b[i+3];
else if(i>=6&&i<9)
a[p][2]=b[i-3]+b[i-6];
}
c[3]=a[1][0]+a[2][1]+a[0][2];
mp[c[3]]="GCB";
c[2]=a[1][0]+a[0][1]+a[2][2];
mp[c[2]]="GBC";
c[5]=a[2][0]+a[1][1]+a[0][2];
mp[c[5]]="CGB";
c[4]=a[2][0]+a[0][1]+a[1][2];
mp[c[4]]="CBG";
c[1]=a[0][0]+a[1][1]+a[2][2];
mp[c[1]]="BGC";
c[0]=a[0][0]+a[2][1]+a[1][2];
mp[c[0]]="BCG";
sort(c,c+5);
cout<<mp[c[0]]<<" "<<c[0]<<endl;
mp.clear();
}
return 0;
}