102 - Ecological Bin Packing
Moderator: Board moderators
Re: Wrong Answer for 102
Can someone explain to me why "CBG" is alphabetically superior to "BGC"?
Edit: Never mind, I was doing it wrong.
Edit: Never mind, I was doing it wrong.
Re: 102, WA. Help me.
Hi,What's wrong with my code? I have got lots of WAs ,frustrated.
It seems the algo is right.
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;
}
102, WA
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?
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;
}
Re: 102, WA
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.
Re: 102, WA
#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?????
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?????
-
- New poster
- Posts: 13
- Joined: Wed Apr 29, 2009 11:37 am
- Location: Barcelona
Re: 102, WA
Some simple cases helped me to fix my errors:
input
output
input
output
input
output
Anyways, not too many problems to get A
input
Code: Select all
0 1 0 0 0 1 1 0 0
Code: Select all
GCB 0
Code: Select all
1 0 0 0 1 0 0 0 1
Code: Select all
BGC 0
Code: Select all
0 0 1 1 0 0 0 1 0
Code: Select all
CBG 0
Born to be wild
-
- New poster
- Posts: 3
- Joined: Thu Jan 22, 2009 9:16 pm
102
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;
}
#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;
}
-
- New poster
- Posts: 14
- Joined: Wed Oct 21, 2009 11:04 am
Re: 102, WA
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..
Re: 102, WA
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 ......
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 ......
Re: 102, WA
who can tell me if all input is zero what string should be output?
102 WA who can help me!!!
Code: Select all
#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
Re: 102 WA who can help me!!!
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);
}
}
-
- New poster
- Posts: 1
- Joined: Tue Nov 02, 2010 5:20 pm
Re: 102
Hi there,
I can't see what's wrong with my code since I continue getting TL status :
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();
}
}
Re: 102
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;
}
#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;
}