102 - Ecological Bin Packing

[epsilon0]

i see...

you do not have to test ALL n! possibilities... my idea would be to use a stack and explore the possibilities like a tree... BUT you can "go back" as soon as the sum of bottle movement gets greater than MAX (the temp max number of bottle movement).. not sure i'm being very clear :/

example:

if you know a way to sort the bins with 10 bottle movements, and you have 10 bins:

bin 1 has 5 green bottles
bin 2 has 6 brown bottles

all the possibilities that put brown bottles in bin 1 and green bottles in bin 2 can be eliminated AT ONCE because they have at least 5+6=11 bottle movements.. that's what i called "go back" when you explore the tree of possibilities....

there might be a better solution but i don't know it...

if anyone knows it please let me know

[ontoral]

Seems straightforward enough, but I got WA.

[cpp]
#include <iostream>
#include <climits>

using namespace std;

int bin1g, bin1b, bin1c, bin2g, bin2b, bin2c, bin3g, bin3b, bin3c;
int one = 0;

void PackBottles()
{
int bcg, bgc, cbg, cgb, gbc, gcb;
int minSwap = INT_MAX;

bcg = bin2b + bin3b + bin1c + bin3c + bin1g + bin2g;
bgc = bin2b + bin3b + bin1g + bin3g + bin1c + bin2c;
cbg = bin2c + bin3c + bin1b + bin3b + bin1g + bin2g;
cgb = bin2c + bin3c + bin1g + bin3g + bin1b + bin2b;
gbc = bin2g + bin3g + bin1b + bin3b + bin1c + bin2c;
gcb = bin2g + bin3g + bin1c + bin3c + bin1b + bin2b;

minSwap = bcg < minSwap ? bcg : minSwap;
minSwap = bgc < minSwap ? bgc : minSwap;
minSwap = cbg < minSwap ? cbg : minSwap;
minSwap = cgb < minSwap ? cgb : minSwap;
minSwap = gbc < minSwap ? gbc : minSwap;
minSwap = gcb < minSwap ? gcb : minSwap;

if( one++ )
cout << endl;

if( bcg == minSwap )
cout << "BCG ";
else if( bgc == minSwap )
cout << "BGC ";
else if( cbg == minSwap )
cout << "CBG ";
else if( cgb == minSwap )
cout << "CGB ";
else if( gbc == minSwap )
cout << "GBC ";
else
cout << "GCB ";
cout << minSwap;
}

int main()
{
cin >> bin1g >> bin1b >> bin1c;
cin >> bin2g >> bin2b >> bin2c;
cin >> bin3g >> bin3b >> bin3c;
while( cin )
{
PackBottles();
cin >> bin1g >> bin1b >> bin1c;
cin >> bin2g >> bin2b >> bin2c;
cin >> bin3g >> bin3b >> bin3c;
}

return 0;
}
[/cpp]

[off_algos]

u must read the problem description properly
when two bins have equal number of swaps the question says to output the lexicographically first order
change ur code like this

Code: Select all

 gcb = bin2g + bin3g + bin1c + bin3c + bin1b + bin2b;
gbc = bin2g + bin3g + bin1b + bin3b + bin1c + bin2c; 
cgb = bin2c + bin3c + bin1g + bin3g + bin1b + bin2b;
    cbg = bin2c + bin3c + bin1b + bin3b + bin1g + bin2g; 
 bgc = bin2b + bin3b + bin1g + bin3g + bin1c + bin2c;
bcg = bin2b + bin3b + bin1c + bin3c + bin1g + bin2g; 

[off_algos]

I made a bad mistake when i saw ur code
sorry!!
[\b]

[off_algos]

problem 102:
... brown, green and clear bottles (respectively) ...

assuming that u named ur variables right (which i think u have!!)
and assuming that im not wrong this time u take the inputs in the wrong order

Code: Select all

 cin >> bin1b >> bin1g >> bin1c;   
                              cin >> bin2b >> bin2g >> bin2c;   
                              cin >> bin3b >> bin3g >> bin3c;   

should get u an AC

[ontoral]

Thanks, I couldn't see the forest for the trees.

[Ozton]

Hi everyone~~^^

Input data
1 2 3 4 5 6 7 8 9

BCG 30 : Answer.
BGC 30 : Wrong answer.

Why...?

[off_algos]

the question specifies that in case of a tie the alphabetically first permutation has to be output

[ElSoloMar]

HOLA A TODOS !!!!

I am trying to solve problem 102 and I get

Your program output is greater (4236247 bytes) than the maximum
allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.

every time I make a tiny change I get a completely different error (WA) or something
similar. My short program is at the end of this email.

Also I am not certain if the way in which I am reading from stdin is the best
since it seems every body is doing it differently. I am assuming that one of the most
effective ways to test so many problems is by redirecting the input like this :

program.exe < input.dat

and that is the reason why I use

[c]
fscanf(stdin,
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]"
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]"
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]"
/*------------------------------------------------------------*/
/* B G C */
, spc, &cb[0], spc, &cb[1], spc, &cb[2], spc /* BIN 1 */
, spc, &cb[3], spc, &cb[4], spc, &cb[5], spc /* BIN 2 */
, spc, &cb[6], spc, &cb[7], spc, &cb[8], spc /* BIN 3 */
);
[/c]

to read the input for 102 ... it works perfectly and smoothly in my system.

I already read ALL the messages concerning problem 102 and I could not find
the answer to my problem. You are my last resource.


[c]
/* @BEGIN_OF_SOURCE_CODE */

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

int main()
{
/* DECLARATION/INITIALISATION OF VARIABLES ................ CC++ */

char
*spc = NULL
, orders[][4] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"}
;
int
i
, bin[6]
, cb[9]
, moves = 0
, order = 0
;

/* BODY OF THE FUNCTION .................................... CC++ */

while( !feof(stdin) ){

fscanf(stdin,
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]"
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]"
"%[^0-9]%d%[^0-9]%d%[^0-9]%d%[^0-9]",
/*---------------------------------------------------------*/
/* B G C */
spc, &cb[0], spc, &cb[1], spc, &cb[2], spc /* BIN 1 */
, spc, &cb[3], spc, &cb[4], spc, &cb[5], spc /* BIN 2 */
, spc, &cb[6], spc, &cb[7], spc, &cb[8], spc /* BIN 3 */
);

/* BCG */
bin[0] = cb[3]+cb[6]+cb[2]+cb[8]+cb[1]+cb[4];
/* BGC */
bin[1] = cb[3]+cb[6]+cb[1]+cb[7]+cb[2]+cb[5];
/* CBG */
bin[2] = cb[5]+cb[8]+cb[0]+cb[6]+cb[1]+cb[4];
/* CGB */
bin[3] = cb[5]+cb[8]+cb[1]+cb[7]+cb[0]+cb[3];
/* GBC */
bin[4] = cb[4]+cb[7]+cb[0]+cb[6]+cb[2]+cb[5];
/* GCB */
bin[5] = cb[4]+cb[7]+cb[2]+cb[8]+cb[0]+cb[3];

moves = bin[0];
for(i=1; i<6; i++){
if ( bin < moves ){
moves = bin;
order = i;
}
}

printf("%s %d\n", orders[order], moves);
}

return 0;
}
/* @END_OF_SOURCE_CODE */
[/c]


GRACIAS POR SU AYUDA!! Y
HAPPY PROGRAMMING !!!

[off_algos]

you must delete all the unnecesary code and then if you send a clearer code with single line comments then i may be able enough to help you..

if u feel like sending me the .c file that compiled in you compiler heres my mail add:
ak_i6@yahoo.com

[kenshin_kudo]

Um try this....instead of initializing min to some large number, try to use
-1 instead and make special case for the first occurence.
There might be a possibility that the number of movements is greater than your initialized min value.

[minskcity]

I submitted your program without changes and got accepted. Try to format it when sending....

[PJP]

I tested this code and I really belive it works. It even tests this: 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.

Can anyone help me? This is the message that appears: Your program has not solved the problem. It ran during 0.156 seconds.
[c]
#include <stdio.h>
int scan_r;
int main()
{
int v[9], r[6],max,i,x,total,n;
scan_r = 9;
while(scan_r==9){
scan_r=scanf("%d %d %d %d %d %d %d %d %d",&v[0],&v[1],&v[2],&v[3],&v[4],&v[5],
&v[6],&v[7],&v[8]);
r[1]= v[0] + v[4] + v[8];
r[0]= v[0] + v[5] + v[7];
r[4]= v[1] + v[3] + v[8];
r[5]= v[1] + v[5] + v[6];
r[2]= v[2] + v[3] + v[7];
r[3]= v[2] + v[4] + v[6];
total= v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + v[6] + v[7] + v[8];
max=0;
for(i=0;i<6;i++)
{
if(r>max)
{max= r; x= i;}
}
n=total-max;
switch (x)
{
case 0 : printf("BCG %d\n",n);break;
case 1 : printf("BGC %d\n",n);break;
case 2 : printf("CBG %d\n",n);break;
case 3 : printf("CGB %d\n",n);break;
case 4 : printf("GBC %d\n",n);break;
case 5 : printf("GCB %d\n",n);break;
}
}
return 0;
}
[/c][/c]

[Hisoka]

your problem only in your input. you don't need scan_r.
you just declarate your input like this:

Code: Select all

while(scanf("%d %d %d %d %d %d %d %d %d",
         &v[0],&v[1],&v[2],&v[3],&v[4],&v[5],&v[6],&v[7],&v[8])==9)
{
 ...
}

[PJP]

Thank you Hisoka... finally it was accepted.