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

Anunnaki
New poster
Posts: 7
Joined: Thu Dec 25, 2008 11:14 pm

Re: Wrong Answer for 102

Post by Anunnaki » Sun Jan 04, 2009 2:32 am

Can someone explain to me why "CBG" is alphabetically superior to "BGC"?

Edit: Never mind, I was doing it wrong.

JINX
New poster
Posts: 3
Joined: Sat Jul 19, 2008 3:36 pm

Re: 102, WA. Help me.

Post by JINX » Sat Apr 25, 2009 11:51 am

Hi,What's wrong with my code? I have got lots of WAs ,frustrated.
It seems the algo is right.

Code: Select all

#include <iostream>
#include <map>
using namespace std;

long long Color[3][3];
long long SumColor[3];
map<int ,char> M;

bool ColorUsed[3];
int	 BinColor[3];
//output
int  MinBinColor[3];
long long MinMove;


void GetInput()
{
		
		for (int i = 0 ;i<3 ;i++)
		{
			SumColor[i] = 0;
			ColorUsed[i] = false;
			BinColor[i] = 0;
		}

		MinMove = (long long)1<<31 ;
		
		for (int i = 0 ;i<3 ;i++)
		{
			cin>>Color[i][0]>>Color[i][2]>>Color[i][1];
			SumColor[i] = Color[i][0]+Color[i][2]+Color[i][1];
		}
	
}




void Process(int bin)
{
	if( bin == 3 )
	{
		long long TmpMove =0;
		for (int j = 0; j<3 ;j++)
		{
			TmpMove += SumColor[j]-Color[j][BinColor[j]];
		}

		if (TmpMove < MinMove)
		{
			MinMove = TmpMove;
			for (int j = 0 ; j<3 ; j++)
			{
				MinBinColor[j] = BinColor[j];
			}

		}
		return;
	}

	for (int i = 0 ; i<3 ; i++)
	{
		if(ColorUsed[i] == false)
		{
			ColorUsed[i] = true;
			BinColor[bin] = i;
			Process(bin+1);
			ColorUsed[i] = false;
		}
		
	
	}

}

void SetOutput()
{
	for (int i = 0 ; i<3 ; i++)
	{
		cout<<M[MinBinColor[i]];
	}
	cout<<' ';
	cout<<MinMove;
	cout<<endl;


}



int main()
{
	
	M[0] = 'B';
	M[1] = 'C';
	M[2] = 'G';
	
	while(!cin.eof()) 
	{
		GetInput();
		Process(0);
		SetOutput();
	}
	




	return 0;
}

ror
New poster
Posts: 2
Joined: Mon May 18, 2009 1:34 am

102, WA

Post by ror » Mon May 18, 2009 1:48 am

Hi,

I keep getting a wrong answer for 102. I've even diffed my output with some of the other posts on this topic on the forum, to only find no difference. This is driving me crazy, I can't find the issue anywhere, all my solutions seem correct, which leaves me to believe it's a formatting issue somehow, but where? Have I got my alphabetization orders correct?

Code: Select all

#include <iostream>
#include <string>

using namespace std;
int solution (int a, int b, int c, const int (&solarray)[9]) {
    return solarray[a]+solarray[b]+solarray[c];
};

string solution_id_to_string(int solID) {
    string out;
    switch (solID) {
        case 1:
            out="BCG";
            break;
        case 2:
            out="BGC";
            break;
        case 3:
            out="CBG";
            break;
        case 4:
            out="CGB";
            break;
        case 5:
            out="GBC";
            break;
        case 6:
            out="GCB";
            break;
        default: out="";
    }
    return out;
};

int main () {
    int input[9];
    int line_max = 1000;
    int solves[line_max][2];
    int line_no=0;

    while((cin >> input[0] >> input[1] >> input[2] >> input[3] >> input[4] >> input[5] >> input[6] >> input[7] >> input[8]) and (line_no < line_max)) {

        int total = input[0]+input[1]+input[2]+input[3]+input[4]+input[5]+input[6]+input[7]+input[8];

        int max = solution(0,5,7,input);
        int solution_id=1;
        if (max<solution(0,4,8,input)) {max=solution(0,4,8,input);solution_id=2;};
        if (max<solution(2,3,7,input)) {max=solution(2,3,7,input);solution_id=3;};
        if (max<solution(2,4,6,input)) {max=solution(2,4,6,input);solution_id=4;};
        if (max<solution(1,3,8,input)) {max=solution(1,3,8,input);solution_id=5;};
        if (max<solution(1,5,6,input)) {max=solution(1,5,6,input);solution_id=6;};

        //cout << solution_id << "\t" << total -max <<endl;
        solves[line_no][0]=solution_id;
        solves[line_no][1]=total-max;
        line_no++;
    }

    for(int i=0;i<line_no;i++) {
        cout << solution_id_to_string(solves[i][0]) << " " << solves[i][1] << endl;
    }

	return 0;
}

ror
New poster
Posts: 2
Joined: Mon May 18, 2009 1:34 am

Re: 102, WA

Post by ror » Tue May 19, 2009 1:13 am

OK well I've fixed it, I just had to re-write it so that output is concurrent with input. I don't know if this is a requirement, or whether I was simply getting my line maximum way too small (I did try some very large numbers though!) but just processing a line at a time has fixed this problem.

rahat089
New poster
Posts: 2
Joined: Sat May 02, 2009 5:03 pm

Re: 102, WA

Post by rahat089 » Thu Jun 25, 2009 6:35 am

#include<stdio.h>
int bin[3][3]={0};
int moves[6]={0};
int main()
{
int min,i,index;
while(scanf("%d%d%d%d%d%d%d%d%d",&bin[0][0],&bin[0][1],&bin[0][2],&bin[1][0],&bin[1][1],&bin[1][2],&bin[2][0],&bin[2][1],&bin[2][2])==9)
{
min=0;
moves[0]=bin[0][1]+bin[0][2]+bin[1][0]+bin[1][2]+bin[2][0]+bin[2][1];
moves[1]=bin[0][1]+bin[0][2]+bin[1][0]+bin[1][1]+bin[2][0]+bin[2][2];
moves[2]=bin[0][0]+bin[0][2]+bin[1][2]+bin[1][1]+bin[2][0]+bin[2][1];
moves[3]=bin[0][0]+bin[0][2]+bin[1][0]+bin[1][1]+bin[2][2]+bin[2][1];
moves[4]=bin[0][0]+bin[0][1]+bin[1][2]+bin[1][1]+bin[2][0]+bin[2][2];
moves[5]=bin[0][0]+bin[0][1]+bin[1][2]+bin[1][0]+bin[2][2]+bin[2][1];
min=moves[0];
index=0;
for(i=1;i<6;i++)
{
if(moves<min)
{
min=moves;
index=i;
}
}
if(index==0)
printf("BCG");
else if(index==1)
printf("BGC");
else if(index==2)
printf("GBC");
else if(index==3)
printf("GCB");
else if(index==4)
printf("CBG");
else
printf("CGB");

printf(" %d\n",min);
}

return 0;
}


i am also gettin WA in this code...can u gys plz help me out?????

User avatar
Jordi Aranda
New poster
Posts: 13
Joined: Wed Apr 29, 2009 11:37 am
Location: Barcelona

Re: 102, WA

Post by Jordi Aranda » Thu Jul 30, 2009 5:48 pm

Some simple cases helped me to fix my errors:
input

Code: Select all

 0 1 0 0 0 1 1 0 0 
output

Code: Select all

 GCB 0 
input

Code: Select all

 1 0 0 0 1 0 0 0 1 
output

Code: Select all

 BGC 0 
input

Code: Select all

 0 0 1 1 0 0 0 1 0 
output

Code: Select all

 CBG 0 
Anyways, not too many problems to get A
Born to be wild

ashraf_iut
New poster
Posts: 3
Joined: Thu Jan 22, 2009 9:16 pm

102

Post by ashraf_iut » Sun Nov 15, 2009 11:15 am

I am getting Wrong Answer !!But I am getting correct answer for mostly all possible critical Input...plz help me...

#include<iostream>
using namespace std;

int main(){
//freopen("102.txt","r",stdin);
long g[3],b[3],c[3],sum,min;
char str[5];
while((scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld",&b[0],&g[0],&c[0],&b[1],&g[1],&c[1],&b[2],&g[2],&c[2]))==9){
sum=0;
min=3000000;

sum=b[1]+b[2]+c[0]+c[2]+g[0]+g[1];
if(sum<min){
min=sum;
strcpy(str,"BCG");
}

sum=b[1]+b[2]+g[0]+g[2]+c[0]+c[1];
if(sum<min){
min=sum;
strcpy(str,"BGC");
}

sum=c[1]+c[2]+b[0]+b[2]+g[0]+g[1];
if(sum<min){
min=sum;
strcpy(str,"CBG");
}
sum=c[1]+c[2]+g[0]+g[2]+b[0]+b[1];
if(sum<min){
min=sum;
strcpy(str,"CGB");
}
sum=g[1]+g[2]+b[0]+b[2]+c[0]+c[1];
if(sum<min){
min=sum;
strcpy(str,"GBC");
}
sum=g[1]+g[2]+c[0]+c[2]+b[0]+b[1];
if(sum<min){
min=sum;
strcpy(str,"GCB");
}
printf("%s %lld\n",str,min);
}
return 0;
}

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

Re: 102

Post by Eather » Sat Jan 30, 2010 8:28 am

you just change long int to long long int and submit.

i got AC so you supposed to get AC :D

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

Re: 102, WA

Post by codeworrior » Wed Jun 23, 2010 7:12 pm

Code: Select all

//THIS CODE HAS BEEN WRITTEN BY CODEWORRIOR(SHIVMITRA MISHRA)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>

using namespace std;

typedef long long int64;

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define A first
#define B second
#define PII pair<int,int>
#define VI vector<int>
#define CLR(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define pb push_back

typedef long long int64;

int main()
{
   freopen("input.txt","r",stdin);
   freopen("output.txt","wt",stdout);
   int64 b1,c1,g1,b2,c2,g2,b3,c3,g3;
   int64 total[8];
   //int64 cases=0;
   while(scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9) 
   {
                                         
                                         CLR(total,0);
                                        
                                         //1
                                         total[5]=c1+g1+b2+c2+b3+g3;
                                         //2
                                         total[6]=c1+g1+b2+g2+b3+c3;
                                         //3
                                         total[2]=b1+c1+g2+c2+b3+g3;
                                         //4
                                         total[1]=b1+c1+b2+g2+c3+g3;
                                         //5
                                         total[4]=b1+g1+c2+g2+b3+c3;
                                         //6
                                         total[3]=b1+g1+b2+c2+c3+g3;
                                         //FOR(i,1,6)
                                         //printf("%d\n",total[i]);
   
                                         int64 ans=1<<20,pos=1;
                                         FOR(i,1,6)
                                         {
                                                  ans=min(total[i],ans);
                                                  if(ans==total[i])
                                                  pos=i;
 
                                         }
   switch (pos)
   {
          case 1:
               {printf("GCB %d",total[1]);break;}
          case 2:
               {printf("GBC %d",total[2]);break;}
          case 3:
               {printf("CGB %d",total[3]);break;}
          case 4:
               {printf("CBG %d",total[4]);break;}
          case 5:
               {printf("BGC %d",total[5]);break;}
          case 6:
               {printf("BCG %d",total[6]);break;}
   }
   printf("\n");
}
}
               


getting correct output fr all the cases i could find in forums.. bt getting WA...plzz help..

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

Re: 102, WA

Post by md_yusuf » Mon Jun 28, 2010 11:22 pm

hey u should remind this line......
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.
may be your program does not solve this for same minimum moves ......

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

Re: 102, WA

Post by panthenia » Sun Jul 11, 2010 4:08 am

who can tell me if all input is zero what string should be output?

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

102 WA who can help me!!!

Post by panthenia » Sun Jul 11, 2010 4:52 am

#include<iostream>
#include<cstdio>

using namespace std;

long bo[3][3],maxs,maxt,cot[3],cos[3],maxa;
bool flag[3];
char cr[3]={'B','G','C'};

void se(int b)
{
if(b==0){int i;
for(i=0;i<3;++i)
{
maxs=0;

flag=false;
maxs+=(bo[1]+bo[2]);

cot=i;


se(1);
flag=true;
}}
else if(b==1)
{ int i;
for(i=0;i<3;++i)
if(flag)
{
maxs+=(bo[0]+bo[2]);
flag=false;cot=i;
se(2);flag=true;
maxs-=(bo[0]+bo[i][2]);
}
}
else if(b==2){int i;
for(i=0;i<3;++i)
if(flag[i])
{maxs+=(bo[i][0]+bo[i][1]);
cot=i;
if(maxs<=maxt)
{if(maxs<maxt)
{maxt=maxs;
for(int i=0;i<3;++i){cos[i]=cot[i];}
}
else {
for(int i=0;i<3;++i)
{if(cr[cot[i]]<=cr[cos[i]])
{
if(cr[cot[i]]<=cr[cos[i]])
for(int j=i;j<3;++j)cos[j]=cot[j];
}else break;}
}
}maxs-=(bo[i][0]+bo[i][1]);
}
}
}
int main()
{
int i,j;

while(cin>>bo[0][0]>>bo[1][0]>>bo[2][0]>>bo[0][1]
>>bo[1][1]>>bo[2][1]>>bo[0][2]>>bo[1][2]>>bo[2][2])
{
for(int i=0;i<3;++i)flag[i]=true;
maxt=0xfffffff;se(0);
for(int i=0;i<3;++i)printf("%c",cr[cos[i]]);
printf(" %lld\n",maxt);
}
}
I've test many data myself ,but I can't find out the error.
despite my complicated code

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

Re: 102 WA who can help me!!!

Post by panthenia » Sun Jul 11, 2010 4:52 am

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;
      
long bo[3][3],maxs,maxt,cot[3],cos[3],maxa;
bool flag[3];
char cr[3]={'B','G','C'};

void se(int b)
     {      
           if(b==0){int i;
                    for(i=0;i<3;++i)
                    {
                      maxs=0;
                      
                      flag[i]=false;
                      maxs+=(bo[i][1]+bo[i][2]);
                      
                      cot[b]=i;
                      
                      
                      se(1);   
                      flag[i]=true;            
                    }}
           else if(b==1)
                {  int i;
                   for(i=0;i<3;++i)
                    if(flag[i])
                      {
                      maxs+=(bo[i][0]+bo[i][2]);
                      flag[i]=false;cot[b]=i;
                      se(2);flag[i]=true; 
                      maxs-=(bo[i][0]+bo[i][2]);           
                      }
                  }        
             else if(b==2){int i;
                      for(i=0;i<3;++i)
                       if(flag[i])
                         {maxs+=(bo[i][0]+bo[i][1]);
                          cot[b]=i;
                          if(maxs<=maxt)
                          {if(maxs<maxt)
                           {maxt=maxs;
                                for(int i=0;i<3;++i){cos[i]=cot[i];}                             
                           }
                           else {         
                                for(int i=0;i<3;++i)
                                  {if(cr[cot[i]]<=cr[cos[i]])
                                    {
                                      if(cr[cot[i]]<=cr[cos[i]])
                                      for(int j=i;j<3;++j)cos[j]=cot[j];                                                                                  
                                    }else break;}                                                             
                                }                                                     
                          }maxs-=(bo[i][0]+bo[i][1]);
                      }                  
                      }                           
     } 
int main()
    {
       int i,j;
       
       while(cin>>bo[0][0]>>bo[1][0]>>bo[2][0]>>bo[0][1]
         >>bo[1][1]>>bo[2][1]>>bo[0][2]>>bo[1][2]>>bo[2][2])
         {                                                            
           for(int i=0;i<3;++i)flag[i]=true;
           maxt=0xfffffff;se(0);
           for(int i=0;i<3;++i)printf("%c",cr[cos[i]]);
           printf(" %lld\n",maxt);                                                                                                                                       
         }
    }

clifford1313
New poster
Posts: 1
Joined: Tue Nov 02, 2010 5:20 pm

Re: 102

Post by clifford1313 » Tue Nov 02, 2010 5:26 pm

Hi there,

I can't see what's wrong with my code since I continue getting TL status :

Code: Select all

import java.io.IOException;

public class Main {

    public final static int BCG = 0;
    public final static int BGC = 1;
    public final static int CBG = 2;
    public final static int CGB = 3;
    public final static int GBC = 4;
    public final static int GCB = 5;
    long[] moves = new long[6];

    static String readln(int maxLg) {
        byte lin[] = new byte[maxLg];
        int lg = 0, car = -1;

        try {
            while (lg < maxLg) {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) {
                    break;
                }
                lin[lg++] += car;
            }
        } catch (IOException e) {
            return (null);
        }

        if ((car < 0) && (lg == 0)) {
            return (null);  // eof
        }
        return (new String(lin, 0, lg));

    }

    public void run() {
        String s = "", result = "";
        boolean first = true;
        while ((s = readln(255)) != null) {
            String splitted[] = s.trim().split(" +");
            if (splitted.length != 9) {
                continue;
            }
            long b1B = Long.parseLong(splitted[0]);
            long b1G = Long.parseLong(splitted[1]);
            long b1C = Long.parseLong(splitted[2]);
            long b2B = Long.parseLong(splitted[3]);
            long b2G = Long.parseLong(splitted[4]);
            long b2C = Long.parseLong(splitted[5]);
            long b3B = Long.parseLong(splitted[6]);
            long b3G = Long.parseLong(splitted[7]);
            long b3C = Long.parseLong(splitted[8]);
            moves[BCG] = b1G + b1C + b2B + b2G + b3B + b3C;
            moves[BGC] = b1G + b1C + b2C + b2B + b3G + b3B;
            moves[CBG] = b1B + b1G + b2C + b2G + b3B + b3C;
            moves[CGB] = b1B + b1G + b2B + b2C + b3C + b3G;
            moves[GBC] = b1B + b1C + b2C + b2G + b3B + b3G;
            moves[GCB] = b1B + b1C + b2B + b2G + b3C + b3G;
            long mresult = moves[BCG];
            int morder = BCG;
            for (int i = 1; i < 6; i++) {
                if (moves[i] < mresult) {
                    mresult = moves[i];
                    morder = i;
                }
            }
            if(!first) result += "\n";
            if (morder == BCG) {
                result += "BCG";
            } else if (morder == BGC) {
                result += "BGC";
            } else if (morder == CBG) {
                result += "CBG";
            } else if (morder == CGB) {
                result += "GCB";
            } else if (morder == GBC) {
                result += "GBC";
            } else if (morder == GCB) {
                result += "GCB";
            }
            result += " " + mresult;
            first = false;
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        Main m = new Main();
        m.run();
    }
}

russel07
New poster
Posts: 1
Joined: Sat Dec 04, 2010 9:38 pm

Re: 102

Post by russel07 » Sat Dec 11, 2010 5:45 pm

Hi, i cant find anything wrong with this code........ can anyone telllllll?

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;

int main()
{
long long a[15][15],b[20],c[100],x;
int i,j,k,p;
map<int,string> mp;
while(cin>>x)
{
b[0]=x;
for(i=1;i<9;i++)
cin>>b;
for(i=0;i<9;i++)
{
p=i%3;
if(i<3)
a[p][0]=b[i+3]+b[i+6];
else if(i>=3&&i<6)
a[p][1]=b[i-3]+b[i+3];
else if(i>=6&&i<9)
a[p][2]=b[i-3]+b[i-6];
}
c[3]=a[1][0]+a[2][1]+a[0][2];
mp[c[3]]="GCB";
c[2]=a[1][0]+a[0][1]+a[2][2];
mp[c[2]]="GBC";
c[5]=a[2][0]+a[1][1]+a[0][2];
mp[c[5]]="CGB";
c[4]=a[2][0]+a[0][1]+a[1][2];
mp[c[4]]="CBG";
c[1]=a[0][0]+a[1][1]+a[2][2];
mp[c[1]]="BGC";
c[0]=a[0][0]+a[2][1]+a[1][2];
mp[c[0]]="BCG";
sort(c,c+5);
cout<<mp[c[0]]<<" "<<c[0]<<endl;
mp.clear();
}
return 0;
}


:roll:

Post Reply

Return to “Volume 1 (100-199)”