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

df7321
New poster
Posts: 1
Joined: Mon Apr 23, 2007 8:59 am

102 wa

Post by df7321 »

has any one can tell me what wrong with my code

#include <stdio.h>



main()
{
int b,b1,b2,g,g1,g2,c,c1,c2,small,n;
int sum=0;
int reg=0;


while(scanf("%d%d%d%d%d%d%d%d%d",&b,&g,&c,&b1,&g1,&c1,&b2,&g2,&c2)==9)
{
sum=b+b1+b2+g+g1+g2+c+c1+c2;
reg=sum-b-c1-g2;
small=reg;
n=1;
reg=sum-b-g1-c2;
if(reg<small)
{
small=reg;
n=2;
}
reg=sum-c-b1-g2;
if(reg<small)
{
small=reg;
n=3;
}
reg=sum-c-g1-b2;
if(reg<small)
{
small=reg;
n=4;
}
reg=sum-g-b1-c2;
if(reg<small)
{
small=reg;
n=5;
}
reg=sum-g-c1-b2;
if(reg<small)
{
small=reg;
n=6;
}
if(n==1)
{
printf("BCG %d\n",small);
}
else if(n==2)
{
printf("BGC %d\n",small);
}
else if(n==3)
{
printf("CBG %d\n",small);
}
else if(n==4)
{
printf("CGB %d\n",small);
}
else if(n==5)
{
printf("GBC %d\n",small);
}
else
{
printf("GCB %d\n",small);
}

}
}

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

- use existing threads
- use code tags

vivgrn
New poster
Posts: 6
Joined: Sat Aug 25, 2007 4:48 pm

WA 102

Post by vivgrn »

hi all
well iam new to uva.
i have read the forum rules and waited for a day to post this in some old thread reagrding the above but my implementation of the problem is different.

here is the code

#include<iostream>

using namespace std;

int main()
{

unsigned long array[9];
int index[3];//store the indices
int block1,posblock1;//stores information about the block. these are the repitition of the arrays declared below
int block2,posblock2;//also working with arrays is a much simpler task than working with variables
int block3,posblock3;
int counter,counter2;
int intercount=0;//longermediate counter
unsigned long sum=0;
int i,j;//i and j are just the counters
unsigned long deduct=0;
unsigned long swapper;
int block[3],posblock[3],change;


while(cin>>array[0]>>array[1]>>array[2]>>array[3]>>array[4]>>array[5]>>array[6]>>array[7]>>array[8])
{

sum=0;
change=0;
for(i=0;i<9;i++)
sum=sum+array;



for(counter=0;counter<9;counter++)
{
if(array[counter]>array[intercount])
intercount=counter;
}

block1=intercount/3;
posblock1=intercount%3;

if(block1==0)
{
if(posblock1!=0)
counter2=3;//physical position
else
counter2=4;
}
else
counter2=0;


for(counter=0;counter<9;counter++)
{
if(array[counter]>array[counter2]&&counter/3!=block1&&counter%3!=posblock1)
counter2=counter;
}

block2=counter2/3;
posblock2=counter2%3;



block3=3-(block1+block2);
posblock3=3-(posblock1+posblock2);


deduct=array[3*block1+posblock1]+array[3*block2+posblock2]+array[3*block3+posblock3];


//determining the indice in the correct order

index[0]=3*block1+posblock1;
index[1]=3*block2+posblock2;
index[2]=3*block3+posblock3;

for(i=2;i>=0;i--)
{
for(j=1;j<=i;j++)
{
if(index[j]<index[j-1])
{
swapper=index[j-1];
index[j-1]=index[j];
index[j]=swapper;
}
}
}


block[0]=0;
block[1]=1;
block[2]=2;
posblock[0]=index[0]%3;
posblock[1]=index[1]%3;
posblock[2]=index[2]%3;

//case1 //BCG
//case2
if(posblock[0]==0&&posblock[1]==1&&posblock[2]==2)//BGC
{
if(array[4]+array[8]<=array[5]+array[7])
{
posblock[1]=2;
posblock[2]=1;
}
}
//case3
else if(posblock[0]==2&&posblock[1]==0&&posblock[2]==1)//CBG
{
if(array[2]+array[3]<=array[0]+array[5])
{
posblock[0]=0;
posblock[1]=2;
}
}
//case4
else if(posblock[0]==2&&posblock[1]==1&&posblock[2]==0)//CGB
{
if(array[6]+array[4]<=array[3]+array[7])
{
posblock[2]=1;
posblock[0]=0;
change=1;
}
if(change==1)
{
if(array[2]+array[3]<=array[5]+array[0])
{
posblock[0]=0;
posblock[1]=2;
}
}
}
//new ones started here

else if(posblock[0]==1&&posblock[1]==2&&posblock[2]==0)//GCB
{
if(array[1]+array[6]<=array[7]+array[0])
{
posblock[0]=0;
posblock[2]=1;
change=1;
}
if(change==0)
{
if(array[1]+array[5]<=array[2]+array[4])
{
posblock[0]=2;
posblock[1]=1;
}
}
}

else if(posblock[0]==1&&posblock[1]==0&&posblock[2]==2)//GBC
{
if(array[1]+array[8]<=array[7]+array[2])

{
{
posblock[0]=2;
posblock[2]=1;
change=1;
}
if(change==1)
{
if(array[2]+array[3]<=array[0]+array[5])
{
posblock[0]=0;
posblock[1]=2;
}
}
else
{
if(array[1]+array[3]<=array[0]+array[4])
{
posblock[0]=0;
posblock[1]=1;
}
}
}
}
//printing
if(posblock[0]==0)
cout<<"B";
if(posblock[0]==1)
cout<<"G";
if(posblock[0]==2)
cout<<"C";
if(posblock[1]==0)
cout<<"B";
if(posblock[1]==1)
cout<<"G";
if(posblock[1]==2)
cout<<"C";
if(posblock[2]==0)
cout<<"B";
if(posblock[2]==1)
cout<<"G";
if(posblock[2]==2)
cout<<"C";
cout<<" "<<(sum-deduct)<<endl;

}
return 0;
}





well the answer to every input here in the thread comes to be fine but i get a wrong answer. is it because of my wrong way of submission ie. the output not being in a standard format???

please help....


thanking you in anticipation

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Search the board first. Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

vivgrn
New poster
Posts: 6
Joined: Sat Aug 25, 2007 4:48 pm

WA 102

Post by vivgrn »

hi all
well iam new to acm.

here is the code.
(the implementation of my code is ltl different than others).

#include<iostream>

using namespace std;

int main()
{

unsigned long array[9];
int index[3];//store the indices
int block1,posblock1;//stores information about the block. these are the repitition of the arrays declared below
int block2,posblock2;//also working with arrays is a much simpler task than working with variables
int block3,posblock3;
int counter,counter2;
int intercount=0;//longermediate counter
unsigned long sum=0;
int i,j;//i and j are just the counters
unsigned long deduct=0;
unsigned long swapper;
int block[3],posblock[3],change;


while(cin>>array[0]>>array[1]>>array[2]>>array[3]>>array[4]>>array[5]>>array[6]>>array[7]>>array[8])
{

sum=0;
change=0;
for(i=0;i<9;i++)
sum=sum+array;



for(counter=0;counter<9;counter++)
{
if(array[counter]>array[intercount])
intercount=counter;
}

block1=intercount/3;
posblock1=intercount%3;

if(block1==0)
{
if(posblock1!=0)
counter2=3;//physical position
else
counter2=4;
}
else
counter2=0;


for(counter=0;counter<9;counter++)
{
if(array[counter]>array[counter2]&&counter/3!=block1&&counter%3!=posblock1)
counter2=counter;
}

block2=counter2/3;
posblock2=counter2%3;



block3=3-(block1+block2);
posblock3=3-(posblock1+posblock2);


deduct=array[3*block1+posblock1]+array[3*block2+posblock2]+array[3*block3+posblock3];


//determining the indice in the correct order

index[0]=3*block1+posblock1;
index[1]=3*block2+posblock2;
index[2]=3*block3+posblock3;

for(i=2;i>=0;i--)
{
for(j=1;j<=i;j++)
{
if(index[j]<index[j-1])
{
swapper=index[j-1];
index[j-1]=index[j];
index[j]=swapper;
}
}
}


block[0]=0;
block[1]=1;
block[2]=2;
posblock[0]=index[0]%3;
posblock[1]=index[1]%3;
posblock[2]=index[2]%3;

//case1 //BCG
//case2
if(posblock[0]==0&&posblock[1]==1&&posblock[2]==2)//BGC
{
if(array[4]+array[8]<=array[5]+array[7])
{
posblock[1]=2;
posblock[2]=1;
}
}
//case3
else if(posblock[0]==2&&posblock[1]==0&&posblock[2]==1)//CBG
{
if(array[2]+array[3]<=array[0]+array[5])
{
posblock[0]=0;
posblock[1]=2;
}
}
//case4
else if(posblock[0]==2&&posblock[1]==1&&posblock[2]==0)//CGB
{
if(array[6]+array[4]<=array[3]+array[7])
{
posblock[2]=1;
posblock[0]=0;
change=1;
}
if(change==1)
{
if(array[2]+array[3]<=array[5]+array[0])
{
posblock[0]=0;
posblock[1]=2;
}
}
}
//new ones started here

else if(posblock[0]==1&&posblock[1]==2&&posblock[2]==0)//GCB
{
if(array[1]+array[6]<=array[7]+array[0])
{
posblock[0]=0;
posblock[2]=1;
change=1;
}
if(change==0)
{
if(array[1]+array[5]<=array[2]+array[4])
{
posblock[0]=2;
posblock[1]=1;
}
}
}

else if(posblock[0]==1&&posblock[1]==0&&posblock[2]==2)//GBC
{
if(array[1]+array[8]<=array[7]+array[2])

{
{
posblock[0]=2;
posblock[2]=1;
change=1;
}
if(change==1)
{
if(array[2]+array[3]<=array[0]+array[5])
{
posblock[0]=0;
posblock[1]=2;
}
}
else
{
if(array[1]+array[3]<=array[0]+array[4])
{
posblock[0]=0;
posblock[1]=1;
}
}
}
}
//printing
if(posblock[0]==0)
cout<<"B";
if(posblock[0]==1)
cout<<"G";
if(posblock[0]==2)
cout<<"C";
if(posblock[1]==0)
cout<<"B";
if(posblock[1]==1)
cout<<"G";
if(posblock[1]==2)
cout<<"C";
if(posblock[2]==0)
cout<<"B";
if(posblock[2]==1)
cout<<"G";
if(posblock[2]==2)
cout<<"C";
cout<<" "<<(sum-deduct)<<endl;

}
return 0;
}





well the answer to every input here in the threads comes to be fine but i get a wrong answer. is it because of my wrong way of submission ie. the output not being in a standard format???

please help....


thanking you in anticipation

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Check the following thread.

http://online-judge.uva.es/board/viewto ... 9b39ba02c9

P.S Thats why the moderators are locking duplicate threads.
Ami ekhono shopno dekhi...
HomePage

Yujou
New poster
Posts: 2
Joined: Tue Oct 09, 2007 5:39 am

Post by Yujou »

Dears,
I tried the input available in the forum (I found in other similar threads)
And I also try to random generate some inputs and compare the result to the sample python code. But still I can't find is there anything wrong.
Can anyone help me check my code below ?
Thanks. (PS. I submitted my code to the new system.)

Code: Select all


#include <stdio.h>
#include <string.h>

#define INPUT stdin
#define OUTPUT stdout

#define BROWN 'B'
#define GREEN 'G'
#define CLEAR 'C'

typedef unsigned long UINT;

int main()
{

#define NUM_PATTERN 6

	// in alphabetic order 
	// ("BCG" means that result is to pack all brown bottles into bin1, 
        //clear bottles into bin2, Green bottles into bin3)
	char * rgszBinsPacking[NUM_PATTERN] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};
	
	// testing fix
	UINT uIdxSum[NUM_PATTERN][6] = {{3, 6, 2, 8, 1, 4, }, // "BCG"
									{3, 6, 1, 7, 2, 5, }, // "BGC"
									{5, 8, 0, 6, 1, 4, }, // "CBG"
									{5, 8, 1, 7, 0, 3, }, // "CGB"
									{4, 7, 0, 6, 2, 5, }, // "GBC"
									{4, 7, 2, 8, 0, 3, }, // "GCB"
									};

	UINT uInitBottles[9] = {0};

	while (!feof(INPUT))
	{
		fscanf(INPUT, "%ld %ld %ld %ld %ld %ld %ld %ld %ld\n",	uInitBottles,
																uInitBottles+1,
																uInitBottles+2,
																uInitBottles+3,
																uInitBottles+4,
																uInitBottles+5,
																uInitBottles+6,
																uInitBottles+7,
																uInitBottles+8);

		// calculate for each pattern
		int i, j;
		int sum;
		int min = 0, minPattern = 0;

		// calc sum for first pattern
		sum = 0;
		for (j = 0; j < 6; ++ j)
		{
			min += uInitBottles[uIdxSum[0][j]];
		}

		for (i = 1; i < NUM_PATTERN; ++ i)
		{
			// calc sum
			sum = 0;
			for (j = 0; j < 6; ++ j)
			{
				sum += uInitBottles[uIdxSum[i][j]];
				if (sum > min)
					break;
			}

			// check min
			if (sum < min)
			{
				min = sum;
				minPattern = i;
			}
		}

		fprintf(OUTPUT, "%s %ld", rgszBinsPacking[minPattern], min);
		if (!feof(INPUT)) 
			fprintf(OUTPUT, "\n");
	};

	return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Don't use feof(). You can use.

Code: Select all

while(fscanf(INPUT,"%d %d,...",...)==6)
{
}
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Yujou
New poster
Posts: 2
Joined: Tue Oct 09, 2007 5:39 am

Post by Yujou »

Hi Jan,
Deeply appreciating of your great help.
I removed the feof code and got accepted (I thought the fault is the integer/long trouble and retried so many times :q).
I thought feof should be working because that I used it for 100, 101. Any way, using that should be assuming the input is in expected format.
Thank you very much for giving advice to me.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

You are welcome. And don't forget to remove your old code, thanks.
Ami ekhono shopno dekhi...
HomePage

Rushow
New poster
Posts: 14
Joined: Sat Oct 14, 2006 4:09 pm
Location: Dhaka,Bangladesh

102--Ecological Bin Packing--Getting Compilation error

Post by Rushow »

Any one help me to solve this problem. My code is given below:
/* p102 */
/* Ecological Bin Packing */

#include<stdio.h>
#include<string.h>

long exchange(long r[3][3],int a,int b,int c);

void main()
{
long r[3][3],total,temp;
char s[5];

while(scanf("%ld%ld%ld%ld%ld%ld%ld%ld%ld",&r[0][0],&r[0][1],&r[0][2],&r[1][0],&r[1][1],&r[1][2],&r[2][0],&r[2][1],&r[2][2])!=EOF)
{
total=exchange(r,0,2,1);
strcpy(s,"BCG");

temp=exchange(r,1,0,2);
if(temp<total)
{
total=temp;
strcpy(s,"GBC");
}

temp=exchange(r,2,0,1);
if(temp<total)
{
total=temp;
strcpy(s,"CBG");
}

temp=exchange(r,0,1,2);
if(temp<total)
{
total=temp;
strcpy(s,"BGC");
}

temp=exchange(r,1,2,0);
if(temp<total)
{
total=temp;
strcpy(s,"GCB");
}
temp=exchange(r,2,1,0);
if(temp<total)
{
total=temp;
strcpy(s,"CGB");
}

printf("%s %ld\n",s,total);

}
}


long exchange(long r[3][3],int a,int b,int c)
{
return r[1][a]+r[2][a]+r[0]+r[2]+r[0][c]+r[1][c];
}




mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Use 'int main()', and return 0 from main.

joaotorres
New poster
Posts: 1
Joined: Sat Feb 02, 2008 8:48 pm

Compile Error

Post by joaotorres »

Hey,

I'm getting a compile error on this one, I'm still trying to get my first one to work. It's working fine here (gcc/cygwin). And though the output for the sample input posted here works fine, oddly the fist sample from the problem ("1 2 3 4 5 6 7 8 9") returns the wrong answer.

I'd be happy if anyone could point me what's wrong. Thanks in advance!

Code: Select all

/*
 * File:   102.c
 * Author: joao
 *
 * Created on 2 de Fevereiro de 2008, 01:47
 */

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
        
    char *line;
    int x1, x2, x3, y1, y2, y3, z1, z2, z3, m, t, r;
    
    line = (char*) malloc(2000);
    
    while (scanf("%d %d %d %d %d %d %d %d %d\n", &x1, &x2, &x3, &y1, &y2, &y3,
            &z1, &z2, &z3) == 9){

        // BGC
        m = y1 + z1 + x2 + z2 + x3 + y3;
        r = 1;
        
        // BCG
        t = y1 + z1 + x3 + z3 + x2 + y2;
        if (t < m){
            m = t;
            r = 2;            
        }
        
        // GBC
        t = y2 + z2 + x1 + z1 + x3 + y3;
        if (t < m){
            m = t;
            r = 3;            
        }
        
        // GCB
        t = y2 + z2 + x3 + z3 + x1 + y1;
        if (t < m){
            m = t;
            r = 4;            
        }
        
        // CBG
        t = y3 + z3 + x1 + z1 + x2 + y2;
        if (t < m){
            m = t;
            r = 5;            
        }
        
        // CGB
        t = y3 + z3 + x2 + z2 + x1 + y1;
        if (t < m){
            m = t;
            r = 6;            
        }
        
        switch(r){
            case 1:{
                printf("BGC");
                break;
            }

            case 2:{
                printf("BCG");
                break;
            }

            case 3:{
                printf("GBC");
                break;
            }

            case 4:{
                printf("GCB");
                break;
            }

            case 5:{
                printf("CBG");
                break;
            }

            case 6:{
                printf("CGB");
                break;
            }
        }
        
        printf(" %d\n", m);
        
    }    
    
    return (1);
}


abdulshafy
New poster
Posts: 1
Joined: Sun Feb 17, 2008 12:25 am

Post by abdulshafy »

You need to consider the case for which t == m, in which you should output the alphabetically smaller string, in order to do that you may do your calculations in the following order: BCG, BGC, CBG, CGB, GBC, GCB.

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Post by amr saqr »

Help Please :(

Here is my code

Code: Select all

Removed After AC :D
Last edited by amr saqr on Sat May 31, 2008 8:34 am, edited 1 time in total.
C++ Is The Best.

Post Reply

Return to “Volume 1 (100-199)”