Page 25 of 33
Reply
Posted: Sun Jun 18, 2006 4:05 am
by 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.
Posted: Sun Jun 18, 2006 2:18 pm
by sathyashrayan
yes, I have got the Idea. Several thanks for delighting in this.
A little program about 102
Posted: Sun Jul 30, 2006 10:45 am
by 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??
Posted: Mon Jul 31, 2006 7:31 am
by 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)
102, WA. Help me.
Posted: Wed Aug 09, 2006 5:04 pm
by 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 : )
Posted: Sat Aug 12, 2006 6:07 am
by 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;
This problem can be solved without using arrays
Posted: Sun Aug 20, 2006 1:09 pm
by 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()
102 wa ? please
Posted: Fri Sep 01, 2006 7:59 am
by 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;
}
Posted: Fri Sep 01, 2006 4:45 pm
by 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
102 Wrong Answer
Posted: Fri Sep 01, 2006 6:43 pm
by 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;
}
Posted: Fri Sep 01, 2006 6:53 pm
by 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:
Posted: Fri Sep 01, 2006 7:41 pm
by 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...
Posted: Sat Sep 02, 2006 3:23 am
by 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.
Posted: Sat Sep 02, 2006 7:26 am
by chunyi81
Why are you reading from a file? You should be reading input using cin or scanf for C++ code.
Posted: Sat Sep 02, 2006 1:17 pm
by neo_darko
Hey - thanks...
Changed everything to long long and the value of min as you said...Got accepted...
Thanks..