102 - Ecological Bin Packing

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by deepdish »


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

Sorry

Post by Sakib »

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. :lol:
/* Sorry For Nothing */

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

WA102 with annotated

Post by 58050zz »

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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Post by 58050zz »

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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni »

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

Post by 58050zz »

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
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

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

Post by 58050zz »

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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni »

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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Post by 58050zz »

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
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

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

Post by 58050zz »

thanks everybody

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

102 Wrong Answer

Post by sunnycare »

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

Post by 58050zz »

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

Post by sunnycare »

thanks ...
but why ?

Post Reply

Return to “Volume 1 (100-199)”