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

technogeek
New poster
Posts: 12
Joined: Sun Jun 01, 2003 12:21 pm
Location: Pune, India

Remove //sign before @ sign

Post by technogeek »

Perhaps // before @end_of_source_code is giving trouble.

Remove // from @begin_of_source_code also.

Take care to put both on independant lines.

wittgens
New poster
Posts: 5
Joined: Wed Jul 16, 2003 6:58 am

[help] 102 why WA?

Post by wittgens »

[cpp]
/* @JUDGE_ID: 33655HX 102 C++ */
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#ifndef _BINPACKING_H_
#define _BINPACKING_H_
class BinPacking
{
private:
vector<int> color;
vector<int> input_data;
int min_number;
public:
BinPacking();
~BinPacking();
void Init();
void Input(int);
void Output();
void Evaluate_Minimum_Moving();
};

BinPacking::BinPacking()
{
Init();//initialize
}

BinPacking::~BinPacking()
{
color.clear();
input_data.clear();
}

void BinPacking::Init()
{
color.clear();
input_data.clear();
color.push_back(0);
color.push_back(1);
color.push_back(2);
min_number=INT_MIN;

}

void BinPacking::Input(int num)
{
input_data.push_back(num);
}

void BinPacking::Output()
{
vector<int>::iterator vi;
for(vi=color.begin(); vi!=color.end(); vi++) {
switch(*vi) {
case 0:
cout << "B";
break;
case 1:
cout << "G";
break;
case 2:
cout << "C";
break;

default:
break;
}
}
cout << " ";
cout << min_number;
}

void BinPacking::Evaluate_Minimum_Moving()
{
int tmp1, tmp2, tmp3;
int min=INT_MAX;
vector<int> tmp_v;
tmp_v.assign(color.begin(), color.end());
do {
tmp1=tmp2=tmp3=0;
//bin 1
tmp1=input_data[3+tmp_v[0]]+input_data[6+tmp_v[0]];

//bin 2
tmp2 = input_data[tmp_v[1]]+input_data[tmp_v[1]+6];

//bin 3
tmp3 = input_data[tmp_v[2]] + input_data[3+tmp_v[2]];

if(min>tmp1+tmp2+tmp3) {
min=tmp1+tmp2+tmp3;
color.assign(tmp_v.begin(), tmp_v.end());
}
} while(next_permutation(tmp_v.begin(), tmp_v.end()));
min_number=min;
}

#endif

int main()
{
int tmp, cnt;
BinPacking bpobj;
while(true) {
cnt=0;
for(int i=0; i<9; i++) {
cin>>tmp;
if(cin.eof()) exit(0);
bpobj.Input(tmp);
}
bpobj.Evaluate_Minimum_Moving();
bpobj.Output();
bpobj.Init();
cout << endl;
}
return 0;
}
[/cpp]
Hi, My name is Jeong-soo, Kim.
I'm Korean.
nice to meet you^^*

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Re:

Post by Zhao Le »

102 why WA?
I didn't see all the code.

Here is input:
1 2 3 4 5 6 7 8 9
It should be:
BCG 30
But your code appears:
BGC 30
Give you a advice:

Test all the test case the problem before you sumbit.

I have some test case if you need you may ask me.
AC makes me feels good,
But WA makes me thinks hard.

wittgens
New poster
Posts: 5
Joined: Wed Jul 16, 2003 6:58 am

but both BGC and BCG are same

Post by wittgens »

BGC 30
bin 1 : 11
bin 2 : 10
bin 3 : 9

BCG 30
bin 1 : 11
bin 2 : 12
bin 3 : 7

------------------

therefore, are both 'BGC 30' and 'BCG 30' all right?
Hi, My name is Jeong-soo, Kim.
I'm Korean.
nice to meet you^^*

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

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.
hope this help.
Kalo mau kaya, buat apa sekolah?

wittgens
New poster
Posts: 5
Joined: Wed Jul 16, 2003 6:58 am

oh~ thank you very much

Post by wittgens »

^^*
Hi, My name is Jeong-soo, Kim.
I'm Korean.
nice to meet you^^*

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

This is a very simple problem

you dont need to make a learge code like you give.

you will always get three glasses and so yo have only 6 combination

you need to check that combination in lexographicaly. i.e.,

BCG
BGC
CBG
CGB
GBC
GCB

Joe
New poster
Posts: 6
Joined: Fri Aug 08, 2003 2:06 pm
Location: Egypt

why WA in the ecological bin problem (102)

Post by Joe »

my code worked for the sample input that was in the problem, but when I submitted it, i received a WA. Somebody Please help!
here is my code:
[cpp]#include <iostream.h>

struct Bin{
int brown;
int green;
int clear;
};

Bin bin[3];

inline int Calculate_Cost(char a[]);
inline bool less(char a[], char r[]);
void Perm(char a[], int k, int n,int& cost,char r[]);

void main(){
int num;
while(cin>>num){
bin[0].brown=num;
cin>>num;
bin[0].green=num;
cin>>num;
bin[0].clear=num;
cin>>num;
bin[1].brown=num;
cin>>num;
bin[1].green=num;
cin>>num;
bin[1].clear=num;
cin>>num;
bin[2].brown=num;
cin>>num;
bin[2].green=num;
cin>>num;
bin[2].clear=num;
char ch[3];
char result[3];
ch[0]='B';ch[1]='C';ch[2]='G';
result[0]='B';result[1]='C';result[2]='G';
int min_cost=32767;
Perm(ch,0,3,min_cost,result);
for (int i=0; i<3; i++) cout << result;
cout <<' '<<min_cost<< endl;
}
}

void Perm(char a[], int k, int n,int& cost,char r[])
{
if (k==n) { // Output permutation.
int x,i;
for ( i=0;i<3;i++) cout<<a<<' ';
cout<<endl;
x=Calculate_Cost(a);
if(x<cost || (x==cost && less(a,r))){
cost=x;
for ( i=0;i<3;i++) r=a;
}
}
else // a[k:n] has more than one permutation.
// Generate these recursively.
for (int i=k; i<n; i++) {
char t=a[k]; a[k]=a; a=t;
Perm(a, k+1, n,cost,r);
// All permutations of a[k+1:n]
t=a[k]; a[k]=a; a=t;
}
}

inline int Calculate_Cost(char a[]){
int y=0;
switch(a[0]){
case 'B': y=y+bin[0].green+bin[0].clear;
break;
case 'G': y=y+bin[0].brown+bin[0].clear;
break;
case 'C': y=y+bin[0].brown+bin[0].green;
}
switch(a[1]){
case 'B': y=y+bin[1].green+bin[1].clear;
break;
case 'G': y=y+bin[1].brown+bin[1].clear;
break;
case 'C': y=y+bin[1].brown+bin[1].green;
}
switch(a[2]){
case 'B': y=y+bin[2].green+bin[2].clear;
break;
case 'G': y=y+bin[2].brown+bin[2].clear;
break;
case 'C': y=y+bin[2].brown+bin[2].green;
}
return y;
}

inline bool less(char a[], char r[]){
for (int i=0;i<3;i++){
if ((int)a>(int)r)
return false;
}
return true;
}[/cpp]
thnx,
Joe

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

For the purposes of this problem, each bin has infinite capacity and the only constraint is moving the bottles so that each bin contains bottles of a single color. The total number of bottles will never exceed 2^31.
The data type int cannot accomodate the input limit. I suggest you to change int to long int.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

Most probably your mistake is here:
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

Really??
I thought int type can only accomodate 32767 for all the compiler???
Now that's something new!!!

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

Yep, int is 32-bits signed integer since 64-bit compilers were here years ago ...

I noticed that the univ I graduated from still uses old compilers like 16-bits BC ... Even their Intel-Assembly language programming is still stuck with 16-bits programming when the processor has evolved a great deal as of today *sigh* ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

turuthok wrote:Yep, int is 32-bits signed integer since 64-bit compilers were here years ago ...

I noticed that the univ I graduated from still uses old compilers like 16-bits BC ... Even their Intel-Assembly language programming is still stuck with 16-bits programming when the processor has evolved a great deal as of today *sigh* ...

-turuthok-
I don't know why universities don't include new apparatus and subject materials in the course :(

I am with the same voice with you and thanks for you comment :)
ImageWe are all in a circular way, no advances, only moving and moving!

Joe
New poster
Posts: 6
Joined: Fri Aug 08, 2003 2:06 pm
Location: Egypt

it still did not work

Post by Joe »

hi,
I tried to change all int's to long but still I got WA
here is my code.
[cpp]#include <iostream.h>
#include <math.h>

struct Bin{
long brown;
long green;
long clear;
};

Bin bin[3];

inline long Calculate_Cost(char a[]);
inline bool less(char a[], char r[]);
void Perm(char a[], int k, int n,long& cost,char r[]);

void main(){
long num;
while(cin>>num){
bin[0].brown=num;
cin>>num;
bin[0].green=num;
cin>>num;
bin[0].clear=num;
cin>>num;
bin[1].brown=num;
cin>>num;
bin[1].green=num;
cin>>num;
bin[1].clear=num;
cin>>num;
bin[2].brown=num;
cin>>num;
bin[2].green=num;
cin>>num;
bin[2].clear=num;
char ch[3];
char result[3];
ch[0]='B';ch[1]='C';ch[2]='G';
result[0]='B';result[1]='C';result[2]='G';
long min_cost=32767;
Perm(ch,0,3,min_cost,result);
for (int i=0; i<3; i++) cout << result;
cout <<' '<<min_cost<< endl;
}
}

void Perm(char a[], int k, int n,long& cost,char r[])
{
if (k==n) { // Output permutation.
int x,i;
x=Calculate_Cost(a);
if(x<cost || (x==cost && less(a,r))){
cost=x;
for ( i=0;i<3;i++) r=a;
}
}
else // a[k:n] has more than one permutation.
// Generate these recursively.
for (int i=k; i<n; i++) {
char t=a[k]; a[k]=a; a=t;
Perm(a, k+1, n,cost,r);
// All permutations of a[k+1:n]
t=a[k]; a[k]=a; a=t;
}
}

inline long Calculate_Cost(char a[]){
int y=0;
switch(a[0]){
case 'B': y=y+bin[0].green+bin[0].clear;
break;
case 'G': y=y+bin[0].brown+bin[0].clear;
break;
case 'C': y=y+bin[0].brown+bin[0].green;
}
switch(a[1]){
case 'B': y=y+bin[1].green+bin[1].clear;
break;
case 'G': y=y+bin[1].brown+bin[1].clear;
break;
case 'C': y=y+bin[1].brown+bin[1].green;
}
switch(a[2]){
case 'B': y=y+bin[2].green+bin[2].clear;
break;
case 'G': y=y+bin[2].brown+bin[2].clear;
break;
case 'C': y=y+bin[2].brown+bin[2].green;
}
return y;
}

inline bool less(char a[], char r[]){
for (int i=0;i<3;i++){
if ((int)a>(int)r)
return false;
}
return true;
}[/cpp]
Joe :(

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

Did you read my previous post??? Pay attention man:

Code: Select all

    long min_cost=32767;
Although you changed int to long (and you didn't have to do it!!) you did NOT change the min_cost value -> initialize it to 2^31-1 or 2^32-1 or something of that magnitude... 32767 is obviously too small!

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Post Reply

Return to “Volume 1 (100-199)”