## 102 - Ecological Bin Packing

Moderator: Board moderators

deepdish
New poster
Posts: 3
Joined: Mon Jan 31, 2005 4:14 pm

Sakib
New poster
Posts: 24
Joined: Fri Jan 28, 2005 5:27 pm

### Sorry

First of all sorry for postinf in wrong volume
It was my first.
But I got accepted some days ago.
I changed my algorithm ... Easy problem.
/* Sorry For Nothing */

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

### WA102 with annotated

i can solve the sample1 and sample2
correct output but still get a WA

Code: Select all

``````
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
//http://online-judge.uva.es/p/v1/102.html
//Ecological Bin Packing

//to store BCG or BGC or...
//store the minimum count
int min=999;
//compare with the count if minimum
//minimum= count

void output(const int a[][3])
{//output condition
for(int i=0;i<9;i++)
{
printf("%d,",a[0][i]);
if(i%3==2) printf("\n");
}
}

void copy_a(int a[][3])
{
int count=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(a[i][j]!=0)
{
if(j==0)
else if(j==1)
else if(j==2)
count++;
}
}
void reproduce_data(const int data[][3],int a[][3])
{//because call by name,i will broken my original data
//so need a copy
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
a[i][j]=data[i][j];
}
}
void pack(const int data[][3],int order[][3],int i)
{
if(i==0)
{//if many inputs it will be used
min=299999;
//output(data);
}
int count=0;
int a[3][3];
reproduce_data(data,a);
//because call by name,i will broken my original data
//so need a copy
for(int j=0;j<3;j++)
{
if(order[i][0]!=j)
{//move bin with enery order
a[order[i][0]][0]+=a[j][0];
count+=a[j][0];
a[j][0]=0;
}
if(order[i][1]!=j)
{
a[order[i][1]][1]+=a[j][1];
count+=a[j][1];
a[j][1]=0;
}
if(order[i][2]!=j)
{
a[order[i][2]][2]+=a[j][2];
count+=a[j][2];
a[j][2]=0;
}
}
if(count<min)
{
copy_a(a);
min=count;
}

//output(a);
//cout<<"count="<<count<<endl;
}

void main()
{
int sample1[3][3]={{1 ,2, 3},{ 4, 5, 6},{ 7, 8, 9}};
int sample2[3][3]={{5 ,10, 5},{ 20, 10, 5},{ 10, 20, 10}};
//samples in 102

int a[3][3],i;
int order[6][3]={
{0,2,1},
{0,1,2},
{2,0,1},
{2,1,0},
{1,0,2},
{1,2,0}};
//the all order will be try and save the mininum
srand(time(NULL));
for(i=0;i<9;i++)
{//if use rand
int k=rand();
a[0][i]=(k%15)+1;
}

for(i=0;i<6;i++)
{//to solve sample2
pack(sample2,order,i);
//printf("\n");
}

//the output
for(i=0;i<3;i++)
/*
for(i=0;i<3;i++)
cout<<endl;
*/

}

``````

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
help

Code: Select all

``````#include <iostream>
using namespace std;
int min=999;

void copy_a(int a[][3])
{
int count=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(a[i][j]!=0)
{
if(j==0)
else if(j==1)
else if(j==2)
count++;
}

}
void reproduce_data(const int data[][3],int a[][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
a[i][j]=data[i][j];
}
}
void pack(const int data[][3],int order[][3],int i)
{
if(i==0)
{
min=299999;

}
int count=0;
int a[3][3];
reproduce_data(data,a);
for(int j=0;j<3;j++)
{
if(order[i][0]!=j)
{
a[order[i][0]][0]+=a[j][0];
count+=a[j][0];
a[j][0]=0;
}
if(order[i][1]!=j)
{
a[order[i][1]][1]+=a[j][1];
count+=a[j][1];
a[j][1]=0;
}
if(order[i][2]!=j)
{
a[order[i][2]][2]+=a[j][2];
count+=a[j][2];
a[j][2]=0;
}
}
if(count<min)
{
copy_a(a);
min=count;
}

}

main()
{

int data[3][3],i;
int order[6][3]={
{0,2,1},
{0,1,2},
{2,0,1},
{2,1,0},
{1,0,2},
{1,2,0}};

for(i=0;i<9;i++)
{
cin>>data[0][i];
}

for(i=0;i<6;i++)
{
pack(data,order,i);
}
for(i=0;i<3;i++)
return 0;
}

``````

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am
The problem says:
The input consists of a series of lines with each line containing 9 integers.
Your program can not handle multiple inputs.

Code: Select all

``````  while (true)
{
for(i=0;i<9;i++)
{
cin>>data[0][i];
if (cin.eof())		return 0;
}
.....
}``````
And,
The total number of bottles will never exceed 2^31.
2^31 = 2147483647
299999 is too small, I think.

Lastly, different cases from mine:

Code: Select all

``````0 0 0 0 0 0 1 1 0
0 1 0 0 2 0 0 3 0``````

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
Help me:
Your program output is greater (4197759 bytes) than the maximum
allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.

i chang some code to handle
0 0 0 0 0 0 1 1 0
0 1 0 0 2 0 0 3 0
hope it works

Code: Select all

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

void copy_a(long a[][3])
{
int count=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(a[i][j]!=-1)
{
if(j==0)
else if(j==1)
else if(j==2)
count++;
}

}
void reproduce_data(const long data[][3],long a[][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
a[i][j]=data[i][j];
}
}
void pack(const long data[][3],int order[][3],int i,long &min)
{

if(i==0)
{
min=2147483647;

}
long count=0;
long a[3][3];
reproduce_data(data,a);
for(int j=0;j<3;j++)
{
if(order[i][0]!=j)
{
//a[order[i][0]][0]+=a[j][0];
count+=a[j][0];
a[j][0]=-1;
}
if(order[i][1]!=j)
{
//a[order[i][1]][1]+=a[j][1];
count+=a[j][1];
a[j][1]=-1;
}
if(order[i][2]!=j)
{
//a[order[i][2]][2]+=a[j][2];
count+=a[j][2];
a[j][2]=-1;
}
}
if(count<min)
{
copy_a(a);
min=count;
}

}

main()
{

long min;
long data[3][3],i;
int order[6][3]={
{0,2,1},
{0,1,2},
{2,0,1},
{2,1,0},
{1,0,2},
{1,2,0}};
do{
for(i=0;i<9;i++)
{
cin>>data[0][i];
}

for(i=0;i<6;i++)
{
pack(data,order,i,min);
}
for(i=0;i<3;i++)
}while(true);
return 0;
}
``````

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Code: Select all

`` do{``
You should never take more than you give in the circle of life.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
i can`t see why

my input and output
and i think it is right
• 1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10
0 0 0 0 0 0 1 1 0
0 1 0 0 2 0 0 3 0
21166 30985 5608 30049 2222 4271 15124 22813 6803
9515 18309 3087 1988 11364 10591 10055 10030 19081
9457 20777 26401 8310 5487 15300 95 19491 25655
29241 9690 2108 718 19418 15355 28464 913 19434
2378 28693 26083 32148 16519 8979 32678 6372 19376
2880 19585 10229 21130 8388 8637 5162 3416 22391
BCG 30
CBG 50
BCG 1
BCG 3
GBC 71204
BGC 54060
GBC 76231
BGC 57248
GBC 93009
GBC 38712
• Your program has not solved the problem. It ran during 0.348 seconds.

Code: Select all

``````
@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: 58050zz  102 C++ */
#include <iostream>
using namespace std;

void copy_a(int i)
{
}
void reproduce_data(const unsigned  long data[][3],unsigned  long a[][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
a[i][j]=data[i][j];
}
}
void pack(const unsigned  long data[][3],int order[][3],int i,unsigned  long
&min)
{

if(i==0)
{
min=2147483647;

}
unsigned  long count=0;
unsigned  long a[3][3];
reproduce_data(data,a);
for(int j=0;j<3;j++)
{
if(order[i][0]!=j)
{
//a[order[i][0]][0]+=a[j][0];
count+=a[j][0];
//a[j][0]=-1;
}
if(order[i][1]!=j)
{
//a[order[i][1]][1]+=a[j][1];
count+=a[j][1];
//a[j][1]=-1;
}
if(order[i][2]!=j)
{
//a[order[i][2]][2]+=a[j][2];
count+=a[j][2];
//a[j][2]=-1;
}
}
if(count<min)
{
copy_a(i);
min=count;
}
}

main()
{

unsigned  long min;
unsigned  long data[3][3],i;
int order[6][3]={
{0,2,1},
{0,1,2},
{2,0,1},
{2,1,0},
{1,0,2},
{1,2,0}};
do{
for(i=0;i<9;i++)
{
if(cin.eof())
return 0;
cin>>data[0][i];
}

for(i=0;i<6;i++)
{
pack(data,order,i,min);
}
for(i=0;i<3;i++)
}while(true);
return 0;
}
@END_OF_SOURCE_CODE
``````

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

But try this, another different cases:

Code: Select all

``````10 8 9 8 6 0 9 7 5
3 13 7 8 7 1 5 7 1
0 11 8 5 1 2 12 12 7
11 12 10 7 10 8 12 5 3
8 10 6 1 0 3 8 1 10``````
My output:

Code: Select all

``````CBG 38
CBG 30
CBG 33
CGB 46
GBC 26``````
I should have tested these cases first rather than those rare cases that I presented before.
These cases violate the priority:
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.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
thanks

i can handle it now

Code: Select all

``````10 8 9 8 6 0 9 7 5
3 13 7 8 7 1 5 7 1
0 11 8 5 1 2 12 12 7
11 12 10 7 10 8 12 5 3
8 10 6 1 0 3 8 1 10
``````

what`s the input and output format

is it (i call it format 1)

Code: Select all

``````10 8 9 8 6 0 9 7 5
3 13 7 8 7 1 5 7 1
0 11 8 5 1 2 12 12 7
11 12 10 7 10 8 12 5 3
8 10 6 1 0 3 8 1 10
CBG 38
CBG 30
CBG 33
CGB 46
GBC 26
``````

OR
(i call it format 2)
(it is the format of my code)

Code: Select all

``````10 8 9 8 6 0 9 7 5
CBG 38
3 13 7 8 7 1 5 7 1
CBG 30
0 11 8 5 1 2 12 12 7
CBG 33
11 12 10 7 10 8 12 5 3
CGB 46
8 10 6 1 0 3 8 1 10
GBC 26
``````
but i can`t change to format 1

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
In fact, both are the same. Note that, the judge sysem reads from & write into two separate streams - stdin & stdout respectively. So, whatever you print will go directly into stdout without having any chance of overlapping with the inputs. So, you need not worry about that.
You should never take more than you give in the circle of life.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
thanks everybody

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

my code here .....I dont know why it wrong.....

Code: Select all

``````#include <iostream>

using namespace std;

void main()
{

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

unsigned int a[9]; //store input num
unsigned int b[6];
while(1)
{
if(cin.eof())
break;
int i=0;
while(i<9)
{
cin>>a[i];
i++;
}
//six case
b[0]=a[0]+a[5]+a[7];
b[1]=a[0]+a[4]+a[8];
b[2]=a[2]+a[3]+a[7];
b[3]=a[2]+a[4]+a[6];
b[4]=a[1]+a[3]+a[8];
b[5]=a[1]+a[5]+a[6];
//choose the biggest b[i],while the i is the smallest
i=1;
unsigned int t=b[0];
unsigned int s=0;
while(i<6)
{
if(b[i]>t)
{
t=b[i];
s=i;
}
i++;
}
cout<<str[s]<<' ';
s=0;
i=0;
while(i<9)
{
s+=a[i];
i++;
}
cout<<s-t<<endl;
}
}``````

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
try to use "unsigned long" or " long"
i think ur code is ok

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
thanks ...
but why ?