## 102 - Ecological Bin Packing

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

The problem which I consider important is that value assigned to m is too long. Every non-float number that you put into your code is considered as an integer if it's not stated otherwise. Long long numbers should have LL suffix at the end.

Remember that the judge is using g++ 2.95. The program that compiles, and even works fine under g++ 3.3 (I suppose that's what you understand by recent mingw) can have a compile error or compile, but work in some other way.

40019JR
New poster
Posts: 9
Joined: Fri Dec 12, 2003 11:41 pm

### Why WA? 102

Hi, I just got WA from the following program. However, I can not figure out what is wrong with it. Can anyone help me out? Thanks.
[cpp]
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
int c1, c2, c3, b1, b2, b3, g1, g2, g3;
int minimum;
int minimum_number;
int r1, r2, r3, r4, r5, r6;
while (cin >> b1 >> g1 >> c1 >> b2 >> g2 >> c2 >> b3 >> g3 >> c3)
{
// r1 == b, g, c
// r2 == b, c, g
// r3 == g, b, c
// r4 == g, c, b
// r5 == c, b, g
// r6 == c, g, b
r1 = b2 + b3 + g1 + g3 + c1 + c2;
minimum = 1;
minimum_number = r1;
r2 = b2 + b3 + c1 + c3 + g1 + g2;
if(r2 < minimum_number)
{

minimum = 2;
minimum_number = r2;
}
r3 = g2 + g3 + b1 + b3 + c1 + c2;
if(r3 < minimum_number)
{
minimum = 3;
minimum_number = r3;
}
r4 = g2 + g3 + c1 + c3 + b1 + b2;
if(r4 < minimum_number)
{
minimum = 4;
minimum_number = r4;
}
r5 = c2 + c3 + b1 + b3 + g1 + g2;
if(r5 < minimum_number)
{
minimum = 5;
minimum_number = r5;
}
else if((r5 == minimum_number) && ((minimum_number == 3) ||
(minimum_number == 4)))
{
minimum = 5;
minimum_number = r5;
}
r6 = c2 + c3 + g1 + g3 + b1 + b2;
if(r2 < minimum_number)
{
minimum = 6;
minimum_number = r6;
}
else if((r6 == minimum_number) && ((minimum_number == 3) ||
(minimum_number == 4)))
{
minimum = 6;
minimum_number = r6;
}

switch(minimum)
{
case 1:
cout << "BGC " << minimum_number << endl;
break;
case 2:
cout << "BCG " << minimum_number << endl;
break;
case 3:
cout << "GBC " << minimum_number << endl;
break;
case 4:
cout << "GCB " << minimum_number << endl;
break;
case 5:
cout << "CBG " << minimum_number << endl;
break;
case 6:
cout << "CGB " << minimum_number << endl;
break;
default:
return 1;
}//end of switch statement
}//end of while statement
return 0;
}[/cpp]

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

the two letters after your user ID are only for your purposes. They are not be put in public.

ofcourse I assume that they are correct.
abi

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm

### 102 WA

"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."

if two movement are same your code doesn't print the alphabeticall first string.

Input:
1 2 3 4 5 6 7 8 9
BGC 30

but OUTPUT should be:
BCG 30

so correct your code and try again. best of luck

you can easily collect your six sumation in a sigle array and then searching it and its location you can easily make your code simple and readable .. anyways u can continue your style.

40019JR
New poster
Posts: 9
Joined: Fri Dec 12, 2003 11:41 pm

### I encountered another problem

Thanks for the correction.
By the way, if you can tell me how to write the code using array more in detail I'd appreciate it.
Now, I get following compiler error from the following code.
02167125_24.c: In function `int main ()':
02167125_24.c:47: parse error at end of input
[cpp]
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
int c1, c2, c3, b1, b2, b3, g1, g2, g3;
int minimum;
int minimum_number;
int r1, r2, r3, r4, r5, r6;
while (cin >> b1 >> g1 >> c1 >> b2 >> g2 >> c2 >> b3 >> g3 >> c3)
{
// r1 == b, g, c
// r2 == b, c, g
// r3 == g, b, c
// r4 == g, c, b
// r5 == c, b, g
// r6 == c, g, b
r1 = b2 + b3 + g1 + g3 + c1 + c2;
minimum = 1;
minimum_number = r1;
r2 = b2 + b3 + c1 + c3 + g1 + g2;
if(r2 <= minimum_number)
{

minimum = 2;
minimum_number = r2;
}
r3 = g2 + g3 + b1 + b3 + c1 + c2;
if(r3 < minimum_number)
{
minimum = 3;
minimum_number = r3;
}
r4 = g2 + g3 + c1 + c3 + b1 + b2;
if(r4 < minimum_number)
{
minimum = 4;
minimum_number = r4;
}
r5 = c2 + c3 + b1 + b3 + g1 + g2;
if(r5 < minimum_number)
{
minimum = 5;
minimum_number = r5;
}
else if((r5 == minimum_number) && ((minimum_number == 3) ||
(minimum_number == 4)))
{
minimum = 5;
minimum_number = r5;
}
r6 = c2 + c3 + g1 + g3 + b1 + b2;
if(r2 < minimum_number)
{
minimum = 6;
minimum_number = r6;
}
else if((r6 == minimum_number) && ((minimum_number == 3) ||
(minimum_number == 4)))
{
minimum = 6;
minimum_number = r6;
}

switch(minimum)
{
case 1:
cout << "BGC " << minimum_number << endl;
break;
case 2:
cout << "BCG " << minimum_number << endl;
break;
case 3:
cout << "GBC " << minimum_number << endl;
break;
case 4:
cout << "GCB " << minimum_number << endl;
break;
case 5:
cout << "CBG " << minimum_number << endl;
break;
case 6:
cout << "CGB " << minimum_number << endl;
break;
default:
return 1;
}//end of switch statement
}//end of while statement
return 0;
}[/cpp]

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
you can implement with an array by declaring an array to hold all the bottle amounts, then another array to hold the movements, and finally if you would like you could have an array to hold the strings to print. Then just use the array instead of your r1,r2,r3.... c1,c2,..... you get the picture
[cpp]
// an array to hold the bottle amounts
unsigned long bottle[9];

// an array to hold the movements
unsigned long move[6];

// and an array to hold the strings (in alphabetical order ofcourse)
static const char str[6]={"BCG","BGC","CBG","CGB","GBC","GCB"};

// your while loop could look like
while(cin>>bottle[0]>>bottle[1]>>bottle[2]>>bottle[3]>>bottle[4]>>bottle[5]>>bottle[6]>>bottle[7]>>bottle[8]){
/*
*
* code
*
*/
}
[/cpp]
It is also nice to have the indices of the movements correspond to the strings to print. Then you just find the index of the minimum movement and print that string.

klv
New poster
Posts: 1
Joined: Mon Jan 26, 2004 6:14 am

### #102 - Output limit Exceeded. May anyone help please~~

Here is my code:

#include <iostream>
using namespace std;

int main()
{
int bin[9];
char color[6][4] = {"BCG","BGC","CBG","CGB","GBC","GCB"};
int max[6];
int index;
int sum = 0;
int sum_tmp;
int min_tmp;
while (1)
{
sum = 0;
for (index = 0;index<9;index++) cin >> bin [index];
for (index = 0;index<9;index++) sum += bin[index];
min_tmp = sum;

sum_tmp = sum;
sum_tmp -= bin[0]+bin[5]+bin[7];
max[0] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

sum_tmp = sum;
sum_tmp -= bin[0]+bin[4]+bin[8];
max[1] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

sum_tmp = sum;
sum_tmp -= bin[2]+bin[3]+bin[7];
max[2] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

sum_tmp = sum;
sum_tmp -= bin[2]+bin[4]+bin[6];
max[3] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

sum_tmp = sum;
sum_tmp -= bin[1]+bin[3]+bin[8];
max[4] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

sum_tmp = sum;
sum_tmp -= bin[1]+bin[5]+bin[6];
max[5] = sum_tmp;
if (min_tmp > sum_tmp) min_tmp = sum_tmp;

for (index = 0;index<6;index++)
if (max[index] == min_tmp)
{
cout << color[index][0] << color[index][1] << color[index][2]
<< " " << max[index] << endl;
break;
}
}
return 0;
}

Can somebody tell me how to solve it please?
Thanks a lot !!

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
You've got the right idea with the six different moves, but why not add the moves up with the different bins instead of subtracting from the sum each time. You save some time by eliminating several of your assignment operations sum_tmp=sum. like:

[cpp]
max[0]=bin[1]+bin[2]+bin[3]+bin[4]+bin[6]+bin[8];// BCG
//max[1]=BGC
//max[2]=CBG
//max[3]=CGB
// and so on
/*
then just do a quick loop through those and check to see which index has the smallest value, and do a quick*/
cout<<color[index]<<endl;
[/cpp]
This is all the code you will need. six assignments with five additions in each assignment, a quick loop, and an output statement.

Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

### How to insert asm into C/C++ code

It's no trade secret. All you have to do is to enclose it like this:

[cpp]_asm nop;[/cpp]
for single statement.

Or make a block for multiple statements

[cpp]_asm
{

}[/cpp]

As C and C++ code can be almost directly converted to asm so the compilers don't have much trouble including any other asm code. All they have to do is to also convert the rest of your C/C++ program into assembly and then assemble it rather than compiling it. Easy isn't it

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

### Plz, help me with some simple code of problem 102, I GOT WA!

ok. I know that it's an ugly code but I'm a beginner in this field....
I don't understand WHAT IS WRONG with my code, it's very simple but I always get WA!!
if someone could help me I will appreciatte

Sorry for my english....I'm from Argentina
here is my code:

[c]#include <stdio.h>

int main()
{
long int temp[6],brown[4],green[4],clear[4];
char inic0[3]="BCG";

while( scanf("%ld %ld %ld %ld %ld %ld %ld %ld %ld", &brown[0], &green[0], &clear[0], &brown[1], &green[1], &clear[1], &brown[2], &green[2], &clear[2])== 9)

temp[0]=brown[1]+brown[2]+ clear[0]+ clear[2]+ green[0]+ green[1];

temp[1]=brown[1]+brown[2]+ clear[0]+ clear[1]+ green[0]+ green[2];

if (temp[0]>temp[1])
{
temp[0]=temp[1];
strcpy(inic0, "BGC");
}
temp[2]=brown[0]+brown[2]+ clear[1]+ clear[2]+ green[0]+ green[1];

if (temp[0]>temp[2])
{
temp[0]=temp[2];
strcpy(inic0, "CBG");
}
temp[3]=brown[0]+brown[1]+ clear[1]+ clear[2]+ green[0]+ green[2];

if (temp[0]>temp[3])
{
temp[0]=temp[3];
strcpy(inic0, "CGB");
}
temp[4]=brown[0]+brown[2]+ clear[0]+ clear[1]+ green[1]+ green[2];

if (temp[0]>temp[4])
{
temp[0]=temp[4];
strcpy(inic0, "GBC");
}
temp[5]=brown[0]+brown[1]+ clear[0]+ clear[2]+ green[1]+ green[2];
if (temp[0]>temp[5])
{
temp[0]=temp[5];
strcpy(inic0, "GCB");
}

printf("%s %ld\n",inic0, temp[0]);
return 0;
}[/c]

The sample input/Output works perfectly...

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

### #102 WA but all the test cases seems to be good

ok. I know that it's an ugly code but I'm a beginner in this field....
I don't understand WHAT IS WRONG with my code, it's very simple but I always get WA!!
if someone could help me I will appreciatte

Sorry for my english....I'm from Argentina
here is my code:

C:
#include <stdio.h>

int main()
{
long int temp[6],brown[4],green[4],clear[4];
char inic0[3]="BCG";

while( scanf("%ld %ld %ld %ld %ld %ld %ld %ld %ld", &brown[0], &green[0], &clear[0], &brown[1], &green[1], &clear[1], &brown[2], &green[2], &clear[2])== 9)

temp[0]=brown[1]+brown[2]+ clear[0]+ clear[2]+ green[0]+ green[1];

temp[1]=brown[1]+brown[2]+ clear[0]+ clear[1]+ green[0]+ green[2];

if (temp[0]>temp[1])
{
temp[0]=temp[1];
strcpy(inic0, "BGC");
}
temp[2]=brown[0]+brown[2]+ clear[1]+ clear[2]+ green[0]+ green[1];

if (temp[0]>temp[2])
{
temp[0]=temp[2];
strcpy(inic0, "CBG");
}
temp[3]=brown[0]+brown[1]+ clear[1]+ clear[2]+ green[0]+ green[2];

if (temp[0]>temp[3])
{
temp[0]=temp[3];
strcpy(inic0, "CGB");
}
temp[4]=brown[0]+brown[2]+ clear[0]+ clear[1]+ green[1]+ green[2];

if (temp[0]>temp[4])
{
temp[0]=temp[4];
strcpy(inic0, "GBC");
}
temp[5]=brown[0]+brown[1]+ clear[0]+ clear[2]+ green[1]+ green[2];
if (temp[0]>temp[5])
{
temp[0]=temp[5];
strcpy(inic0, "GCB");
}

printf("%s %ld\n",inic0, temp[0]);
return 0;
}

The samples input/Output works perfectly...

zymen
New poster
Posts: 2
Joined: Sun Feb 15, 2004 5:54 pm

### 102 problem... Why doesn't it work ?

Why doesn't it work ?

[cpp]#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define b 0
#define g 1
#define c 2

int containers[3][3]={{0}};

char result[4]={0};
int minimum_cost(99999999);

void min_cost()
{
int tmp_cost(0);
int nr(0);
//bcg
tmp_cost = containers[1]+containers[2]+ //b
containers[0][c]+containers[2][c]+ //c
containers[0][g]+containers[1][g]; //g

minimum_cost = tmp_cost;
strcpy(result, "bcg");

//bgc
tmp_cost = containers[1]+containers[2]+ //b
containers[0][g]+containers[2][g]+ //g
containers[0][c]+containers[1][c]; //c

if (minimum_cost > tmp_cost )
{
minimum_cost = tmp_cost;
strcpy(result, "bgc");
}

//cbg
tmp_cost = containers[1][c]+containers[2][c]+ //c
containers[0]+containers[2]+ //b
containers[0][g]+containers[1][g]; //g

if (minimum_cost > tmp_cost )
{
minimum_cost = tmp_cost;
strcpy(result, "cbg");
}

//cgb
tmp_cost = containers[1][c]+containers[2][c]+ //c
containers[0][g]+containers[2][g]+ //g
containers[0]+containers[1]; //b

if (minimum_cost > tmp_cost )
{
minimum_cost = tmp_cost;
strcpy(result, "cgb");
}

//gbc
tmp_cost = containers[1][g]+containers[2][g]+ //g
containers[0]+containers[2]+ //b
containers[0][c]+containers[1][c]; //c

if (minimum_cost > tmp_cost )
{
minimum_cost = tmp_cost;
strcpy(result, "gbc");
}

//gcb
tmp_cost = containers[1][g]+containers[2][g]+ //g
containers[0][c]+containers[2][c]+ //c
containers[0][b]+containers[1][b]; //b

if (minimum_cost > tmp_cost )
{
minimum_cost = tmp_cost;
strcpy(result, "gcb");
}

}

int main(int argc, char *argv[])
{
while(cin>>containers[0][0]>>containers[0][1]>>containers[0][2]>>\
containers[1][0]>>containers[1][1]>>containers[1][2]>>\
containers[2][0]>>containers[2][1]>>containers[2][2])
{
min_cost();
cout << result << " " << minimum_cost << endl;
}
return 0;
}[/cpp]
:=
love is nice ;->

zymen
New poster
Posts: 2
Joined: Sun Feb 15, 2004 5:54 pm
heh

just one small mistake
bcg -> BCG
etc.. :>

everything is ok now.
:=
love is nice ;->

Sayutee
New poster
Posts: 9
Joined: Wed Jun 04, 2003 7:50 am

### Only two traps can be here

I think you have made a very much simple thing much complex. trying to simplify the code will do better.

Scanf returns the number of elements it scans - but sometimes i had it not working as i expected. though i am not sure, but your input-taking style may cause the problem. When scanf tries to read past the end-of-file, it returns EOF. try this.

hope u will get an AC. best of luck.

Sayutee
New poster
Posts: 9
Joined: Wed Jun 04, 2003 7:50 am