102 - Ecological Bin Packing

[Fali]

Hi!!

Let me explain the sample input...

Sample Input

1 2 3 4 5 6 7 8 9

then the bins are in this form:
Brown Green Clear
Bin #1: 1 2 3
Bin #2: 4 5 6
Bin #3: 7 8 9

We want to put all the brown bottles in one bin, all the green bottles in other and all the clear bottles in other. i.e we want to separe the bins by color.

if we try the following order:

BCG

then we have to move 4 brown bottles of bin#2 and 7 brown bottles of bin#3 to bin#1, because bin#1 is of brown bottles, of de same form we have to move 3 clear bottles from bin#1 and 9 clear bottles from bin#3 to bin#2 and 2 green bottles from bin#1 and 5 green bottles from bin#2 to bin#3, then the total of moved bottles is:

4 + 7 + 3 + 9 + 2 + 5 = 30.

I hope this help

P.D. There are only 6 possible combinations:

BCG
BGC
CBG
CGB
GBC
GCB

you can only figure out those 6 (yes, only 6) possible combinations, and then choose the smallest.

[sathyashrayan]

yes, I have got the Idea. Several thanks for delighting in this.

[toyman]

Code: Select all

while(cin>>arr[0]>>arr[1]>>arr[2]>>arr[3]>>arr[4]>>arr[5]>>arr[6]>>arr[7]>>arr[8]){ 

can this work?

I can get AC!!!
Code:

while (true) {
if (cin.eof()) break;

This is the cause of WA.
This should be changed,
Code:
while (scanf("%d %d %d %d %d %d %d %d %d",
&data[0],&data[1],&data[2],
&data[3],&data[4],&data[5],
&data[6],&data[7],&data[8])==9) {...

the above means what???
that's will got WA??

[smilitude]

this is supposed to work!
i took my input like this ...

Code: Select all

while(scanf("%d%d%d%d%d%d%d%d%d", 
&b[0][0],&b[0][2],&b[0][1],&b[1][0],&b[1][2],&b[1][1],&b[2][0],&b[2][2],&b[2][1])==9)

[mosaick2]

I don't know what's problem in my code.
Who can advice me?
(Actually, I have passed many testcase that I found below threads.)
I'll appreciate your help.
------------------------------------------------------------------------------
I got A.C
Actually, My mistake is if-statement's position.

Code: Select all

 *wrong code*

	do
	{ 
		if (cin.eof()) break;  <=====
		bp.SetInput();
		bp.GetSolution();
	} while (!cin.eof());

Code: Select all

*correct code*

	do
	{ 
		bp.SetInput();
		if (cin.eof()) break; <=====
		bp.GetSolution();
	} while (!cin.eof());

In wrong code, my program prints one more line that comes from last answer.

Thankx, shaform : )

[shaform]

Your program prints an unnecessary line when End-Of-File is reached.
( cin.eof() returns true if the eofbit stream's error flag has been set by a previous i/o operation. )
Why not just write something like this:

Code: Select all

z = 0;
while(cin >> x[z]) {
	if(++z<9) continue;

[hedgehog1204]

just linear programming and single data types. Here is the example in Python (easy to convert to other languages):

Code: Select all

# Program that solves the Ecological Bin Packing problem
# http://acm.uva.es/p/v1/102.html
	
file = open('input.txt')
for line in file:
	vars = line.strip().split(' ')				# get numbers from input file
	B1, G1, C1, B2, G2, C2, B3, G3, C3 = vars	# assign number of bottles in bins
	# count number of moves for every bin and color:
	B12, B13, B23 = int(B1)+int(B2), int(B1)+int(B3), int(B2)+int(B3)		
	C12, C13, C23 = int(C1)+int(C2), int(C1)+int(C3), int(C2)+int(C3)
	G12, G13, G23 = int(G1)+int(G2), int(G1)+int(G3), int(G2)+int(G3)
	min = B23+G12+C13
	minBins = "BGC"

	# find minimum number of moves
	moves = B23+G13+C12
	if moves < min or minBins > "BGC" and min == moves:
		minBins, min = "BGC", moves
	moves = B23+G12+C13
	if moves < min or minBins > "BCG" and min == moves:
		minBins, min = "BCG", moves
	moves = B13+G23+C12
	if moves < min or minBins > "GBC" and min == moves:
		minBins, min = "GBC", moves
	moves = B12+G23+C13	
	if moves < min or minBins > "GCB" and min == moves:
		minBins, min = "GCB", moves
	moves = B13+G12+C23
	if moves < min or minBins > "CBG" and min == moves:
		minBins, min = "CBG", moves
	moves = B12+G13+C23
	if moves < min or minBins > "CGB" and min == moves:
		minBins, min = "CGB", moves
	print minBins, min
file.close()

[tle_nu]

#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("bin.txt");

int main()
{
int sum,pack;
int min = 0;

int bin[10];

while(fin >> bin[1] >> bin[2] >> bin[3] >> bin[4] >> bin[5] >> bin[6] >> bin[7] >> bin[8] >> bin[9])
{


min = bin[2]+bin[3]+bin[4]+bin[5]+bin[7]+bin[9];
pack = 2;

if((sum = bin[2]+bin[3]+bin[4]+bin[6]+bin[7]+bin[8]) < min)
{
min = sum;
pack = 1;
}

if((sum = bin[2]+bin[3]+bin[4]+bin[5]+bin[7]+bin[9]) < min)
{
min = sum;
pack = 2;
}

if((sum = bin[1]+bin[3]+bin[5]+bin[6]+bin[7]+bin[8]) < min)
{
min = sum;
pack = 3;
}

if((sum = bin[1]+bin[3]+bin[4]+bin[5]+bin[8]+bin[9]) < min)
{
min = sum;
pack = 4;
}

if((sum = bin[1]+bin[2]+bin[5]+bin[6]+bin[7]+bin[9]) < min)
{
min = sum;
pack = 5;
}

if((sum = bin[1]+bin[2]+bin[4]+bin[6]+bin[8]+bin[9]) < min)
{
min = sum;
pack = 6;
}

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

return 0;
}

[Vexorian]

there aren't much test cases that might fail here except when more than one combination is the minimum in which case the output should be the alphabetically first minimum solution.

try these test cases:

in

Code: Select all

2 2 2 2 2 2 2 2 2
10 90 16 78 1 2 3 100 1000
0 0 0 0 0 0 0 0 0
1 3 3 5 3 3 9 3 3

out

Code: Select all

BCG 12
GBC 132
BCG 0
CGB 18

[neo_darko]

Hi - I've tried the available Test Cases - the outputs seem to be correct. But still I got wrong answer...

Code: Select all

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

long a[6];
long bin1[4];
long bin2[4];
long bin3[4];

char *ch[6] = { "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" };

int main()
{	
	long min, index;
	
	while( scanf("%ld%ld%ld%ld%ld%ld%ld%ld%ld", &bin1[1], &bin1[2], &bin1[3], &bin2[1], &bin2[2], &bin2[3], &bin3[1], &bin3[2], &bin3[3]) != EOF )
	{
		min = 999999;
		
		a[0] =  bin2[1] + bin3[1] + bin1[3] + bin3[3] + bin1[2] + bin2[2];
		if ( min > a[0] ) 
		{
			min = a[0];
			index = 0;
		}
				
		a[1] =  bin2[1] + bin3[1] + bin1[2] + bin3[2] + bin1[3] + bin2[3];
		if ( min > a[1] ) 
		{
			min = a[1];
			index = 1;
		}
		
		a[2] =  bin2[3] + bin3[3] + bin1[1] + bin3[1] + bin1[2] + bin2[2];
		if ( min > a[2] ) 
		{
			min = a[2];
			index = 2;
		}
		
		a[3] =  bin2[3] + bin3[3] + bin1[2] + bin3[2] + bin1[1] + bin2[1];
		if ( min > a[3] ) 
		{
			min = a[3];
			index = 3;
		}
		
		a[4] =  bin2[2] + bin3[2] + bin1[1] + bin3[1] + bin1[3] + bin2[3];
		if ( min > a[4] ) 
		{
			min = a[4];
			index = 4;
		}

		a[5] =  bin2[2] + bin3[2] + bin1[3] + bin3[3] + bin1[1] + bin2[1];
		if ( min > a[5] ) 
		{
			min = a[5];
			index = 5;
		}
		
		printf("%s %ld\n", ch[index], a[index]);
	}
	
	return 0;
}

[Vexorian]

there was a topic on this problem just 2 threads bellow but anyways try these:

in:

Code: Select all

2 2 2 2 2 2 2 2 2
10 90 16 78 1 2 3 100 1000
0 0 0 0 0 0 0 0 0
1 3 3 5 3 3 9 3 3

out:

Code: Select all

BCG 12
GBC 132
BCG 0
CGB 18

[neo_darko]

Sorry for opening a new thread - but I thought that's how things go around here - I mean everyone should start his/her own thread...

Anyways - I've tried the test cases - they worked...

[tan_Yui]

The total number of bottles will never exceed 2^31.

So, the parameter 'min = 999999;' will be too small to solve.
It should be set on more than 2147483648.

Best regards.

[chunyi81]

Why are you reading from a file? You should be reading input using cin or scanf for C++ code.

[neo_darko]

Hey - thanks...

Changed everything to long long and the value of min as you said...Got accepted...

Thanks..