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

m_jerry1101
New poster
Posts: 2
Joined: Tue May 18, 2004 9:51 am
Location: Shanghai, China

why WAs?(problem 102)

I can't find anything wrong.
[cpp]#include <iostream.h>
#include <string.h>

long bins[3][3];

void main()
{long x,y,z,t;
int i,j,k;
char b[4],r[4];
do
{t=0;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{cin>>bins[j];
t+=bins[j];
}
strcpy(r,"GGG");strcpy(b,"BBB");
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(i!=j)
{x=0;y=0;z=0;
for(k=0;k<3;k++)
{if(k!=i)x+=bins[k][0];
if(k!=j)y+=bins[k][1];
if(k!=3-i-j)z+=bins[k][2];
}
if(x+y+z<=t)
{b='B';b[j]='G';b[3-i-j]='C';b[4]='\0';
if(x+y+z<t)
{strcpy(r,b);
t=x+y+z;
}
else
if(strcmp(b,r)<0)
{strcpy(r,b);
t=x+y+z;
}
}
}
cout<<r<<" "<<t<<endl;
}while(!cin.eof());
}[/cpp]

NothingElse
New poster
Posts: 2
Joined: Thu Jun 10, 2004 6:02 pm
Contact:

Hi all!

I am a new member and I have just tried to solve the problem 102. When I compiled it on my computer and run, it was Ok. But when I submitted, I received the notice that : Compile Error. About the Input, I wrote exactly as in example of problem 100 which was given to us.

Is there any body can help me?
Thanks a lot
Nothing to Lose

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Edit your member profile and have the judge send messages to your e-mail address.

It'll give you the exact compile error message.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
i ran your program on TC and found that for any input the control gets
struck in this loop :
[c]
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(i!=j)
{x=0;y=0;z=0;
for(k=0;k<3;k++)
{if(k!=i)x+=bins[k][0];

[/c]
if u can think of it .. u can do it in software.

m_jerry1101
New poster
Posts: 2
Joined: Tue May 18, 2004 9:51 am
Location: Shanghai, China

3Q,but......

thanks,but...........what's wrong with this loop.
i'm having final exam these days

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Contact:

Why wrong answer for 102

I am psyched!!!!I am getting a wrong answer for this!!!I am not able to find any mistake!!!Can comeone spot any mistake or some sample input!!!!!!!

[cpp]
#include<iostream>
#include<limits.h>

using namespace std;

main()
{
long int a[9],i,j,k[6],clr,opt;
while(cin>>a[0] > 0)
{
for(i=1;i<9;i++)
{
cin>>a;
}
{
k[5]=a[3]+a[6]+a[1]+a[7]+a[2]+a[5];
k[1]=a[3]+a[4]+a[0]+a[7]+a[2]+a[8];
k[2]=a[1]+a[4]+a[0]+a[5]+a[6]+a[8];
k[0]=a[1]+a[4]+a[2]+a[3]+a[6]+a[8];
k[3]=a[1]+a[5]+a[0]+a[3]+a[7]+a[8];
k[4]=a[0]+a[4]+a[2]+a[5]+a[6]+a[7];
}
opt=k[0];
clr = 0;
for(j=0;j<6;j++)
{[cpp]
if(k[j]<opt)
{
opt=k[j];
clr=j;
}
}
/* for(i=0;i<6;i++)
{
if((k==opt)&&(i<clr))
{
clr=i;
}
}*/

switch(clr)
{
case 1:{cout<<"BGC "<<opt<<'\n';break;}
case 5:{cout<<"GCB "<<opt<<'\n';break;}
case 2:{cout<<"CBG "<<opt<<'\n';break;}
case 0:{cout<<"BCG "<<opt<<'\n';break;}
case 3:{cout<<"CGB "<<opt<<'\n';break;}
case 4:{cout<<"GBC "<<opt<<'\n';break;}
}
}
return (0);
}

Can someone help me out pls!!!!!!!!!!!!!!!!!!1 [/cpp][/cpp]

Md. Azam Khan
New poster
Posts: 8
Joined: Tue Jun 15, 2004 7:16 pm
Contact:
Hi,
I think there is nothing to explain bcoz u understood the problem clearly. So no more discussion. I changed ur silly mistake in making the minimum.

{ //why did u use this bracket?
k[5]=a[3]+a[6]+a[1]+a[7]+a[2]+a[5]; //It is for k[1] not for k[5] according to ur output.
k[1]=a[3]+a[4]+a[0]+a[7]+a[2]+a[8];// It is for k[5] not for k[1]
k[2]=a[1]+a[4]+a[0]+a[5]+a[6]+a[8];
k[0]=a[1]+a[4]+a[2]+a[3]+a[6]+a[8];
k[3]=a[1]+a[5]+a[0]+a[3]+a[7]+a[8];
k[4]=a[0]+a[4]+a[2]+a[5]+a[6]+a[7];
}//why did u use this bracket?

u can also change ur code in output without changing above code. But i think it should try urself.

Wishing good luck.

I born to code

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Contact:

Thank u!

Yeah!!It got accepted!!Thanx a lot!

gingioerge
New poster
Posts: 4
Joined: Thu Jul 01, 2004 2:12 pm

102 faster, faster than the speed of light.

Ok I'm new, so forgive me if I say something stupid...
I've just solved problem 102, it is quite easy, ok,
but I have a question:
since the problem isn't hard and the solution is simple
to write I can't understand how someone could
get 0.00.000 time and 64 memory usage
while my program get 0.00.303 time and 404 memory usage
It isn't really important, but I can't imagine what improvements
they used. What's the trick?

Md. Azam Khan
New poster
Posts: 8
Joined: Tue Jun 15, 2004 7:16 pm
Contact:
Hi,
The matter is not actually like that. The program is never faster than the light. In this problem there is only six combination. it can be done without using any loop. So how much time is there need to solve the problem? It is enough time of 0.00.000123=>?, isn't it? Anyway now u r a newcomer (according to u), when u will be an expert then u will better understand the matter. We r waiting for the day!

Wishing good luck.

I born to code

gingioerge
New poster
Posts: 4
Joined: Thu Jul 01, 2004 2:12 pm

a

Infact I know that this problem can be solved in CONSTANT time,
only 6 configuration must be checked, I do this in my code!
And it is for this reason that I can't think a simpler solution....

[cpp] #include <iostream>

int main()
{
const char seq_name[6][4] =
{ "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" };
unsigned int b1, b2, b3, c1, c2, c3, g1, g2, g3;
unsigned int seq[6], j, max = 0;

for( ; (std::cin >> b1) > 0 ; ) {
std::cin >> g1 >> c1
>> b2 >> g2 >> c2
>> b3 >> g3 >> c3;

seq[0] = b1 + c2 + g3;
seq[1] = b1 + g2 + c3;
seq[2] = c1 + b2 + g3;
seq[3] = c1 + g2 + b3;
seq[4] = g1 + b2 + c3;
seq[5] = g1 + c2 + b3;

for( j = 1, max = 0 ; j < 6 ; ++j )
if( seq[ j ] > seq[ max ] ) max = j;

std::cout << seq_name[ max ] << " "
<< ( seq[ 0 ] + seq[ 3 ] + seq[ 4 ] - seq[ max ] )
<< std::endl;
}

return 0;
}[/cpp]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
You may consider improving your I/O routines to get a better run time.

However, I think that you should just forget about the 0.00.000s time... Check this out:
http://online-judge.uva.es/board/viewtopic.php?t=5850
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

janrenfairy
New poster
Posts: 2
Joined: Sat Jul 03, 2004 9:26 pm
Location: China

102 Why I got WA?Help!

I've tested sevaral cases on my code including the sample,and it can work out ,why I still got WA? Can any good guy help me,please?I really want to know why?Thanks!

Code: Select all

``````#include<iostream.h>

#include<stdio.h>

void GBC(int gbc)

{

switch(gbc)

{

case 0:cout<<'B';break;

case 1:cout<<'C';break;

case 2:cout<<'G';break;

}

return;

}

int main(void)

{

long int B1[3],B2[3],B3[3],i,j,k,m,ii,jj,kk,movs,minmovs;

while(scanf("%d%d%d%d%d%d%d%d%d",&B1[0],&B1[2],&B1[1],&B2[0],&B2[2],&B2[1],&B3[0],&B3[2],&B3[1])==9)

{

minmovs=100000000;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

if(j==i)continue;

for(k=0;k<3;k++)

{

movs=0;

if((k==i)||(k==j))continue;

for(m=0;m<3;m++)

{

if(m!=i)movs=movs+B1[m];

if(m!=j)movs=movs+B2[m];

if(m!=k)movs=movs+B3[m];

}

if((movs<minmovs)||((movs==minmovs)&&((i<ii)||((i==ii)&&(j<jj)))))

{

minmovs=movs;

ii=i;

jj=j;

kk=k;

}

}

}

}

GBC(ii);GBC(jj);GBC(kk);

cout<<" "<<minmovs<<endl;

}

return(0);

}
``````

gingioerge
New poster
Posts: 4
Joined: Thu Jul 01, 2004 2:12 pm
oh, really I don't understand your code...
but I think that the error, if there's one, isn't in code...
spend little more time on the problem and, I'm sure,
you'll find a simpler solution... this problem can be solved in
constant time, take a pen and a paper and try by hand,
I think you'll learn more than trying to debugging this code

Falldog
New poster
Posts: 4
Joined: Tue Jul 13, 2004 3:49 am

102 WA!!!

[cpp]
#include<iostream>
#include<string>
using namespace std;

int BlockCount(char * color,int *Block){
int time=0;
for(int x=0 ; x<9 ; x+=3){
if( color[x/3] == 'B' ){
time += Block[x+1] ;
time += Block[x+2] ;
}
if( color[x/3] == 'G' ){
time += Block[x] ;
time += Block[x+2] ;
}
if( color[x/3] == 'C' ){
time += Block[x] ;
time += Block[x+1] ;
}
}
return time;
}
void main(){
int Block[9],x,y,z,minTime=99999,tempTime;
char BGC[4]="BCG";
char color[4],minColor[4];

while( ( cin>>Block[0] ) != NULL ){
for(x=1 ; x<9 ; x++)
cin>>Block[x];

for(x=0 ; x<3 ; x++)
for(y=0 ; y<3 ; y++)
for(z=0 ; z<3 ; z++){
if(x!=y && x!=z && y!=z){
color[0]=BGC[x];
color[1]=BGC[y];
color[2]=BGC[z];
tempTime = BlockCount(color,Block);
if( minTime > tempTime ){
minTime=tempTime;
strcpy(minColor,color);
}
}
}
minColor[3]='\0';

cout<< minColor << ' ' << minTime <<'\n';
minTime=99999;
}
}
[/cpp]