102 - Ecological Bin Packing

deepdish · Post by **deepdish** » Sun Feb 06, 2005 4:48 pm

hey~ check it out first~
http://online-judge.uva.es/board/viewto ... 9b39ba02c9

Sakib · Post by **Sakib** » Sun Feb 06, 2005 5:12 pm

First of all sorry for postinf in wrong volume
It was my first.
Thanks for reply.
But I got accepted some days ago.
I changed my algorithm ... Easy problem.

58050zz · Post by **58050zz** » Sat Feb 26, 2005 2:53 pm

i can solve the sample1 and sample2
correct output but still get a WA
please help me
i am a newer

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

int answer_array[3];
//to show answer condition,for debug
char answer_order[4];
//to store BCG or BGC or...
int answer_count=0;
//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)
			{
				answer_array[i]=a[i][j];
				if(j==0)
					answer_order[count]='B';
				else if(j==1)
					answer_order[count]='G';
				else if(j==2)
					answer_order[count]='C';
				count++;
			}
	answer_order[count]='\0';//set NULL at end
}
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;
		answer_count=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++)
		cout<<answer_order[i];
	cout<<"  "<<answer_count<<endl;
	/*
	for(i=0;i<3;i++)
		cout<<answer_array[i]<<",";
	cout<<endl;
	*/

}

58050zz · Post by **58050zz** » Sat Feb 26, 2005 4:41 pm

my newest WA
help

Code: Select all

#include <iostream>
using namespace std;
int answer_array[3];
char answer_order[4];
int answer_count=0;
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)
   {
    answer_array[i]=a[i][j];
    if(j==0)
     answer_order[count]='B';
    else if(j==1)
     answer_order[count]='G';
    else if(j==2)
     answer_order[count]='C';
    count++;
   }

 answer_order[count]='\0';
}
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;
  answer_count=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++)
  cout<<answer_order[i];
 cout<<"  "<<answer_count<<endl;
 return 0;
}

teni_teni · Post by **teni_teni** » Sat Feb 26, 2005 9:20 pm

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 · Post by **58050zz** » Sat Feb 26, 2005 11:09 pm

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

please post the right answer for me to check

Code: Select all

#include <iostream>
using namespace std;

char answer_order[4];
int answer_count=0;

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)
   {
    //answer_array[i]=a[i][j];
    if(j==0)
     answer_order[count]='B';
    else if(j==1)
     answer_order[count]='G';
    else if(j==2)
     answer_order[count]='C';
    count++;
   }

 answer_order[count]='\0';
}
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;
  answer_count=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++)
  cout<<answer_order[i];
 cout<<" "<<answer_count<<endl;
  }while(true);
 return 0;
}

Mohammad Mahmudur Rahman · Sun Feb 27, 2005 2:12 am

Code: Select all

do{

58050zz · Post by **58050zz** » Sun Feb 27, 2005 7:11 am

please help me
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;

char answer_order[4];
int answer_count=0;

void copy_a(int i)
{
 if(i==0) strcpy(answer_order,"BCG");
 if(i==1) strcpy(answer_order,"BGC");
 if(i==2) strcpy(answer_order,"GCB");
 if(i==3) strcpy(answer_order,"CGB");
 if(i==4) strcpy(answer_order,"GBC");
 if(i==5) strcpy(answer_order,"CBG");
}
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;
  answer_count=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++)
  cout<<answer_order[i];
 cout<<" "<<answer_count<<endl;
  }while(true);
 return 0;
}
@END_OF_SOURCE_CODE

teni_teni · Post by **teni_teni** » Sun Feb 27, 2005 5:38 pm

Your output is right.

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 · Post by **58050zz** » Mon Feb 28, 2005 11:17 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

please tell me

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
please teach me

Mohammad Mahmudur Rahman · Tue Mar 01, 2005 2:44 am

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.

58050zz · Post by **58050zz** » Tue Mar 01, 2005 9:10 am

thanks everybody

sunnycare · Post by **sunnycare** » Tue Mar 08, 2005 3:37 am

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 · Post by **58050zz** » Sat Mar 12, 2005 5:34 am

try to use "unsigned long" or " long"
i think ur code is ok

sunnycare · Post by **sunnycare** » Mon Mar 14, 2005 4:17 am

thanks ...
but why ?

OJ Board

102 - Ecological Bin Packing

Sorry

WA102 with annotated

102 Wrong Answer