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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

Hi !! Peter here some I/O maybe you can test

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

Hope it Helps
Keep posting !! :D

Peter
New poster
Posts: 3
Joined: Fri Oct 15, 2004 12:28 pm
Location: Poland, Wloclawek

Post by Peter »

... already tested some time ago , thx anyway :)

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 »

your program gives an extra output before terminate.

change you code like this:
[cpp]
while(1)
{
for(i=0;i<9;i++)
cin>>b;
if(cin.eof()) break;
}[/cpp]

there may be other problems. :roll:

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by wirjawan »

your program does not break tie correctly.

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

try this input:
2 3 1 5 3 1 3 5 3

the expected output is:
CBG 15

your output:
GBC 15

Both CBG & GBC needs 15 moves , but since CBG is "first" compared to GBC (C is earlier than G) , you should output "CBG".

looking at your code, it seems that your order of evaluation is :
BCG , BGC , GCB , GBC , CGB, CBG.

it should be,
BCG, BGC, CBG, CGB, GBC, GCB.

hope it helps :)

Peter
New poster
Posts: 3
Joined: Fri Oct 15, 2004 12:28 pm
Location: Poland, Wloclawek

Post by Peter »

Thank you for your help and time u've spent to find the bug. Unfortunately I don't have much time now to ultimately deal with this problem, but I'll do it soon :-). And I'll post about the result ...

Wirjawan - debug master 8)


BTW: I'd like to thank A1 for his good intentions:-)

bloodnight
New poster
Posts: 6
Joined: Thu Dec 30, 2004 5:14 pm

102why compile error

Post by bloodnight »

im a newcomer here, and just dont know how to get the detailed feedback info about detailed... i received no mail from the system how come?

here's my code...anyone could help me? thanks very much...

#include <iostream>
#include <string>

using namespace std;

struct bin
{
long brown,green,clear;
}bin[3];

struct movements
{
long n;
string s;
}movements[6];

int main()
{
long min;
while(!feof(stdin))
{
for( int i=0 ; i<3 ; i++ )
cin>>bin.brown>>bin.green>>bin.clear;
i=0;

movements.n=bin[1].brown+bin[2].brown+bin[0].green+bin[2].green+bin[0].clear+bin[1].clear;
movements.s="BGC";
i++;


movements.n=bin[1].brown+bin[2].brown+bin[0].clear+bin[2].clear+bin[0].green+bin[1].green;
movements.s="BCG";
i++;


movements.n=bin[1].green+bin[2].green+bin[0].brown+bin[2].brown+bin[0].clear+bin[1].clear;
movements.s="GBC";
i++;


movements.n=bin[1].green+bin[2].green+bin[0].clear+bin[2].clear+bin[0].brown+bin[1].brown;
movements[i].s="GCB";
i++;

movements[i].n=bin[1].clear+bin[2].clear+bin[0].brown+bin[2].brown+bin[0].green+bin[1].green;
movements[i].s="CBG";
i++;

movements[i].n=bin[1].clear+bin[2].clear+bin[0].green+bin[2].green+bin[0].brown+bin[1].brown;
movements[i].s="CGB";


min=movements[0].n;
for( i=1 ; i<6 ; i++ )
if(movements[i].n<min)
min=movements[i].n;
for( i=0 ; i<6 ; i++ )
if(movements[i].n==min)
{
cout<<movements[i].s<<" "<<min<<endl;
break;
}
}
return 0;
}

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

If you are using a mail agent to submit problems it can cut off the lines that are painfully long(for it) so only a portion of your code goes in to the judge.

You should have a copy of the code *submitted* to the judge in the judge response in your mailbox(if you didnt delete that already).Go check it and it should tell you more where exactly the error is.

Alternatively, use the link:
http://acm.uva.es/problemset/submit.php

Regards,
Suman.

bloodnight
New poster
Posts: 6
Joined: Thu Dec 30, 2004 5:14 pm

now,i've corrected my codes

Post by bloodnight »

thanks,sumankar...

#include <iostream>
#include <string>

using namespace std;

struct bin
{
long brown,green,clear;
}bin[3];

struct movements
{
long n;
string s;
}movements[6];

int main()
{
long min;
int i;
while(cin>>bin[0].brown>>bin[0].green>>bin[0].clear)
{
for( i=1 ; i<3 ; i++ )
cin>>bin.brown>>bin.green>>bin.clear;

i=0;

movements.n=bin[1].brown+bin[2].brown+bin[0].clear+bin[2].clear+bin[0].green+bin[1].green;
movements.s="BCG";
i++;


movements.n=bin[1].brown+bin[2].brown+bin[0].green+bin[2].green+bin[0].clear+bin[1].clear;
movements.s="BGC";
i++;


movements.n=bin[1].clear+bin[2].clear+bin[0].brown+bin[2].brown+bin[0].green+bin[1].green;
movements.s="CBG";
i++;

movements.n=bin[1].clear+bin[2].clear+bin[0].green+bin[2].green+bin[0].brown+bin[1].brown;
movements[i].s="CGB";


movements[i].n=bin[1].green+bin[2].green+bin[0].brown+bin[2].brown+bin[0].clear+bin[1].clear;
movements[i].s="GBC";
i++;


movements[i].n=bin[1].green+bin[2].green+bin[0].clear+bin[2].clear+bin[0].brown+bin[1].brown;
movements[i].s="GCB";
i++;

min=movements[0].n;
for( i=1 ; i<6 ; i++ )
if(movements[i].n<min)
min=movements[i].n;
for( i=0 ; i<6 ; i++ )
if(movements[i].n==min)
{
cout<<movements[i].s<<" "<<min<<endl;
break;
}
}
return 0;
}
here's my corrected prog, why's it wa? i've almost tried every test datas i could get...
i did adhere to the output specification that the output should be in lexicographical order, is there sth else i may neglect?

bloodnight
New poster
Posts: 6
Joined: Thu Dec 30, 2004 5:14 pm

Post by bloodnight »

well, i see now :evil:

ywceric
New poster
Posts: 5
Joined: Fri Jan 07, 2005 12:58 pm

how many lines should i process???

Post by ywceric »

for example , http://acm.uva.es/p/v1/102.html
in this Q, how many lines should i process??
is there any limit??
if there is no limit, how can i process all the lines if the line number exceeds the limit of array of the compiler?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Try processing the test cases one by one instead of reading the whole input into memory first. The task 102 can be solved with O(1) memory, i.e. the memory your program uses doesn't depend on the size of the input.

As a side note, when using 32-bit compilers you can make pretty huge arrays :D

enochcheng
New poster
Posts: 4
Joined: Sat Jan 08, 2005 9:19 pm

102

Post by enochcheng »

how about this
why i can't be done?

#include "stdio.h"

main()
{
int max,i,j,total=0,bin[9],final[]={0,0,0},checka[]={0,0,1},checkb[]={1,2,2};
char maxbin[3]={8,8,8},binname[]="BCG";
while(scanf("%d%d%d%d%d%d%d%d%d",&bin[0],&bin[2],&bin[1],&bin[3],&bin[5],&bin[4],&bin[6],&bin[8],&bin[7])==9)
{
total=0;
final[0]=0;final[1]=0;final[2]=0;
maxbin[0]=8;maxbin[1]=8;maxbin[2]=8;
for(j=0;j<3;j++)
{
max=0;
for(i=0+j;i<9;i+=3)
if(bin>bin[max])
max=i;
if(max>2&&max<6)
max=1;
else if(max>5&&max<9)
max=2;
else
max=0;
final[j]=max;
maxbin[max]=binname[j];
}
printf("final: %d %d %d maxbin: %d %d %d\n",final[0],final[1],final[2],maxbin[0],maxbin[1],maxbin[2]);
for(j=0;j<3;j++)
if(final[checka[j]]==final[checkb[j]])
for(i=0;i<3;i++)
if(maxbin==8)
{
final[checka[j]]=i;
maxbin=binname[checka[j]];
break;
}


for(i=0;i<3;i++)
printf("%c: %d %d %d\n",binname,bin[0*3+i],bin[1*3+i],bin[2*3+i]);

printf("final: %d %d %d maxbin: %d %d %d\n",final[0],final[1],final[2],maxbin[0],maxbin[1],maxbin[2]);

for(j=0;j<3;j++)
{
maxbin[final[j]]=binname[j];
printf("for %c, max is %d, value is %d\n",binname[j],final[j],bin[final[j]*3+j]);
printf("%c %c\n",maxbin[final[j]],binname[j]);
for(i=0;i<3;i++)
if(i!=final[j]){printf("total: %d add: %d\n",total,bin[i*3+j]);
total+=bin[i*3+j];}
}

maxbin[3]='\0';
printf("%s %d\n",maxbin,total);
}
}

enochcheng
New poster
Posts: 4
Joined: Sat Jan 08, 2005 9:19 pm

Post by enochcheng »

what's wrong with this program?
please help...thx

Rakot2005
New poster
Posts: 5
Joined: Mon Jan 10, 2005 11:33 pm

Post by Rakot2005 »

you can write easy code...
you must count a movements of different cases - 6 cases.
and case with min movement is the answer

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

102 Ecological Bin Packing

Post by Sakib »

Can anyone tell me What will be the format to write this program?
I can't get AC.
Please Help!

(C++)
#include<stdio.h>
void main()
{
long k,b1,c1,g1,b2,c2,g2,b3,c3,g3;
char t1,t2,t3;
while(scanf("%ld %ld %ld %ld %ld %ld %ld %ld %ld",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9)
{
k=0;
//------------------------------------
if(b1>b2 && b1>b3)
{
t1='G';
k=k+b2+b3;
if(g2>g3)
{
t2='B';
k=k+g1+g3;
t3='C';
k=k+c1+c2;
}
else
{
t3='B';
t2='C';
k=k+g1+g2;
k=k+c1+c3;
}
}
//----------------------------------------
else if(b2>b1 && b2>b3)
{
t1='C';
k=k+b1+b3;
if(g1>g3)
{
t2='G';
k=k+g2+g3;
t3='B';
k=k+c1+c2;
}
else
{
t3='G';
t2='B';
k=k+g1+g2;
k=k+c2+c3;
}
}
//-------------------------------------------
else
{
t1='B';
k=k+b1+b2;
if(g1>g2)
{
t3='C';
k=k+g2+g3;
t2='G';
k=k+c1+c3;
}
else
{
t2='C';
t3='G';
k=k+g1+g3;
k=k+c2+c3;
}
}
//-----------------------------------------
printf("%c%c%c ",t1,t2,t3);
printf("%ld\n",k);
}
}


Thanks!
/* Sorry For Nothing */

Post Reply

Return to “Volume 1 (100-199)”