102 - Ecological Bin Packing

[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]

[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]

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

[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?

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

[wittgens]

^^*

[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]

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]

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]

Most probably your mistake is here:

Code: Select all

[Joseph Kurniawan]

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

[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-

[Moni]

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

[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]

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