UVa : 102 (Ecological Bin Packing)


Title : Ecological Bin Packing

Link : http://uva.onlinejudge.org/external/1/102.html

Tricky Lines :

  1. each bin has infinite capacity
  2. The total number of bottles will never exceed 2^31.
  3. the number of bottles are given in sequence : brown, green, and clear
  4. three upper case characters ‘G’, ‘B’, ‘C’ (representing the colors green, brown, and clear)
  5. alphabetically first string representing a minimal configuration should be printed

Analysis :

  1. Data type : integer
  2. Try all the possibilities to get the answer. That is, first make the bin’s into BCG. Count the movements you need sorting out the bottles.
  3. Similarly go through other possibilities in sequence
    BCG
    BGC
    CBG
    CGB
    GBC
    GCB
    [55 – 60]
  4. if u don’t maintain the sequence then you need to keep track, for which combination you got the minimum result.
  5. Surely you can’t loop through all the bottles as the limit is 2^31
  6. if u decided to make the first bin to keep the color ‘B’ then all other colors increases the movement value.

Critical Input:
9 8 7 6 5 4 3 2 1
238609294 238609294 238609294 238609294 238609294 238609294 238609294 238609294 238609294
85263245 25965748 69854785 15874569 36985745 12365478 36985526 32147859 96587458
123 654 789 963 258 741 159 963 357
123 987 12 852 963 987 963 159 753

Critical Output:
BCG 30
BCG 1431655764
BGC 193193965
CBG 2292
GCB 2862

Runtime : 0.048s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;

int bottles [9 + 3];

int count_movement (int a, int b, int c)
{
    int m = 0;
    for ( int i = 0; i < 9; i++ ) {
        if ( i != a && i != b && i != c )
            m += bottles [i];
    }

    return m;
}

int main ()
{
    while ( scanf ("%d", &bottles [0]) != EOF ) {

        for ( int i = 1; i < 9; i++ )
            scanf ("%d", &bottles [i]);

        char output_str [3 + 3];
        int movements [6];
        int min_movement = INT_MAX;
        char combinations [6] [3 + 2] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};

        // Brown index : 0 3 6
        // Green index : 1 4 7
        // Clear index : 2 5 8

        movements [0] = count_movement (0, 5, 7); // BCG
        movements [1] = count_movement (0, 4, 8); // BGC
        movements [2] = count_movement (2, 3, 7); // CBG
        movements [3] = count_movement (2, 4, 6); // CGB
        movements [4] = count_movement (1, 3, 8); // GBC
        movements [5] = count_movement (1, 5, 6); // GCB

        for ( int i = 0; i < 6; i++ ) {
            if ( movements [i] < min_movement ) {
                min_movement = movements [i];
                strcpy (output_str, combinations [i]);
            }
        }

        printf ("%s %d\n", output_str, min_movement);

    }

	return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UVa : 102 (Ecological Bin Packing)

  1. you can solve this problem by more easily.

    #include
    int main()
    {
    long int min,b1,g1,c1,b2,g2,c2,b3,g3,c3,bcg,bgc,cbg,cgb,gbc,gcb;
    while(scanf(“%ld%ld%ld%ld%ld%ld%ld%ld%ld”;,
    &b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9)
    {
    bcg=0,bgc=0,cbg=0,cgb=0,gbc=0,gcb=0;
    bcg=b2+b3+c1+c3+g1+g2;
    bgc=b2+b3+g1+g3+c1+c2;
    cbg=c2+c3+b1+b3+g1+g2;
    cgb=c2+c3+g1+g3+b1+b2;
    gbc=g2+g3+b1+b3+c1+c2;
    gcb=g2+g3+c1+c3+b1+b2;
    min=bcg;
    if(bgc<min)min=bgc;
    if(cbg<min)min=cbg;
    if(cgb<min)min=cgb;
    if(gbc<min)min=gbc;
    if(gcb<min)min=gcb;
    if(bcg==min)printf("BCG %ld\n",min);
    else if(bgc==min)printf("BGC %ld\n",min);
    else if(cbg==min)printf("CBG %ld\n",min);
    else if(cgb==min)printf("CGB %ld\n",min);
    else if(gbc==min)printf("GBC %ld\n",min);
    else printf("GCB %ld\n",min);
    }
    return 0;
    }

    for solution of this problem and other more problem visit http://uvasolve.co.cc

  2. #include
    #include
    #include
    #include
    #include
    using namespace std;
    struct Case
    {
    string bins ;
    long long motions;
    Case(string s , long long mo)
    {
    bins = s;
    motions = mo;
    }
    };
    Case calcMotions(long long arr [3][3] )
    {
    vector Cases;

    long long B1 = arr[0][1] + arr[0][2];
    long long G1 = arr[1][0] + arr[1][2];
    long long C1 = arr[2][0] + arr[2][1];
    long long case1 = B1 + G1+C1;
    Cases.push_back(Case(“BGC”,case1));

    long long B2 = arr[0][1] + arr[0][2];
    long long C2 = arr[2][0] + arr[2][2];
    long long G2 = arr[1][0] + arr[1][1];
    long long case2 = B2+C2+G2;
    Cases.push_back(Case(“BCG”,case2));

    long long C3 = arr[2][1] + arr[2][2];
    long long B3 = arr[0][0] + arr[0][2];
    long long G3 = arr[1][0] + arr[1][1];
    long long case3 = C3 + B3 + G3;
    Cases.push_back(Case(“CBG”,case3));

    long long G4 = arr[1][1] + arr[1][2];
    long long B4 = arr[0][0] + arr[0][2];
    long long C4 = arr[2][0] + arr[2][1];
    long long case4 = G4 + B4 + C4;
    Cases.push_back(Case(“GBC”,case4));

    long long G5 = arr[1][1] + arr[1][2];
    long long C5 = arr[2][0] + arr[2][2];
    long long B5 = arr[0][0] + arr[0][1];
    long long case5 = G5 + C5 + B5;
    Cases.push_back(Case(“GCB”,case5));

    long long C6 = arr[2][1] + arr[2][2];
    long long G6 = arr[1][0] + arr[1][2];
    long long B6 = arr[0][0] + arr[0][1];
    long long case6 = C6 + G6+ B6;
    Cases.push_back(Case(“CGB”,case6));

    long long min = Cases[0].motions;
    Case tmp = Cases[0];
    for(long long i = 1 ;i<Cases.size();i++)
    {
    if(Cases[i].motions Cases[i].bins)
    tmp = Cases[i];
    }

    }

    return tmp;
    }

    int main()
    {
    long long bottels [3][3];
    long long num = 0;
    Case tmp(“”,0);
    while (true)
    {
    //get 9 bottels
    for(long long j = 0 ;j<3;j++)
    {
    for(long long i = 0 ;i>bottels[i][j] ;
    num += bottels[i][j];
    if(num>(2^31))
    goto l1;
    }
    }
    tmp = calcMotions(bottels);
    cout<<tmp.bins<<" "<<tmp.motions<<endl;
    //prlong longf("%s %f\n",tmp.bins , tmp.motions);
    l1:
    num = 0;
    }
    return 0;
    }

    uva said 'time limit',why??

  3. #include
    int main()
    {
    int ara[9],i,r=0,sor[6],j,k,m;
    char c[25]=”BCGBGCCBGCGBGBCGCB”;

    while(scanf(“%d%d%d%d%d%d%d%d%d”,&ara[0],&ara[1],&ara[2],&ara[3],&ara[4],&ara[5],&ara[6],&ara[7],&ara[8])==9){

    sor[0]=ara[1]+ara[2]+ara[3]+ara[4]+ara[6]+ara[8];
    sor[1]=ara[1]+ara[2]+ara[3]+ara[5]+ara[6]+ara[7];
    sor[2]=ara[0]+ara[1]+ara[4]+ara[5]+ara[6]+ara[8];
    sor[3]=ara[0]+ara[1]+ara[3]+ara[5]+ara[7]+ara[8];
    sor[4]=ara[0]+ara[2]+ara[4]+ara[5]+ara[6]+ara[7];
    sor[5]=ara[0]+ara[2]+ara[3]+ara[4]+ara[7]+ara[8];

    for(i=0;isor[i])r=i;

    }
    k=r;
    j= 3 * r;

    for(r=j;r<j+3;r++)
    {
    printf("%c",c[r]);
    }
    printf(" %d\n",sor[k]);
    r=0;
    k=0;
    j=0;
    }

    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s