102 - Ecological Bin Packing

[kasturi]

thanks a lot man .. that worked.. but the problem does not state that condition right?? anyway thanx for that suggestion..

[Almost Human]

Actually it does. Maybe you missed it because it is stated at the last paragraph:

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

I'm glad it helped

[sms]

I keep getting WA. I tested my output even against the samples provided by Almost Human (http://online-judge.uva.es/board/viewto ... hlight=102). My output matched with his. Pls. help.
[cpp]
#include <stdio.h>
#include <string.h>

#define MAX 3

int n;
int arr[MAX];
double data[MAX][MAX];
double max;
double tot;
int soln;

char chars[MAX] = {'B', 'G', 'C'};
char outs[6][MAX+1];

void print(int arr[])
{
int i;
for(i=0;i<n;i++) printf("%d ",arr);
printf("\n");
}

void find_min()
{
int i;
double temp = 0.0;

for(i=0;i<MAX;i++)
temp+=data[arr];

if(max<temp) soln=0;
else if(max==temp) soln++;

if(max<=temp) {
max=temp;
for(i=0;i<MAX;i++)
outs[soln]=chars[arr];
}
}

void swap(int arr[], int x, int y)
{
int temp=arr[x];
arr[x]=arr[y];
arr[y]=temp;
}


void perm(int p, int depth)
{
int i;
if(p==(n-1)) {find_min(); return;}

perm(p+1, 1);
if(depth)
{
for(i=p+1;i<n;i++)
{
swap(arr,p,i);
perm(p,0);
swap(arr,p,i);
}
}

}


void mysort(char str[6][4], int num)
{
int i,j;
char temp[256];
for(i=num-1;i>0;i--)
{
for(j=0;j<i;j++)
if(strcmp(str[j],str[j+1])>1)
{
strcpy(temp, str[j]);
strcpy(str[j], str[j+1]);
strcpy(str[j+1],temp);
}
}
}

int main(int argc, char *argv[])
{
int i,j;
n=3;
while(1)
{
max=tot=0.0;
soln=0;
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(scanf("%lf",&data[j])!=1) return 0;
tot+=data[j];
}
arr=i;
}
for(i=0;i<6;i++) outs[MAX]='\0';
perm(0,1);
mysort(outs,soln);
printf("%s %.0lf\n",outs[0],tot-max);
}
return 0;
}
[/cpp][/c]

[vadiu]

I can't understand why my code gives me WA. This problem is easy, and I've read all the posts. I would be greatful if someone could help me.
[c]
#include "stdio.h"
#include "string.h"


int main()
{
int i;
char order[5];
unsigned long int matrix[9], sum=0;

while(!feof(stdin))
{
for(i=0; i<9&&!feof(stdin); i++)
scanf("%lu", &matrix);

strcpy(order, "BCG");



sum=matrix[1]+matrix[2]+matrix[3]+matrix[4]+matrix[6]+matrix[8];


if(matrix[1]+matrix[2]+matrix[3]+matrix[5]+matrix[6]+matrix[7]<sum)
{
sum=matrix[1]+matrix[2]+matrix[3]+matrix[5]+matrix[6]+matrix[7];
strcpy(order, "BGC");
}

if(matrix[0]+matrix[1]+matrix[4]+matrix[5]+matrix[6]+matrix[8]<sum)
{
sum=matrix[0]+matrix[1]+matrix[4]+matrix[5]+matrix[6]+matrix[8];
strcpy(order, "CBG");
}

if(matrix[0]+matrix[1]+matrix[3]+matrix[5]+matrix[7]+matrix[8]<sum)
{
sum=matrix[0]+matrix[1]+matrix[3]+matrix[5]+matrix[7]+matrix[8];
strcpy(order, "CGB");
}

if(matrix[0]+matrix[2]+matrix[4]+matrix[5]+matrix[6]+matrix[7]<sum)
{
sum=matrix[0]+matrix[2]+matrix[4]+matrix[5]+matrix[6]+matrix[7];
strcpy(order, "GBC");
}

if(matrix[0]+matrix[2]+matrix[3]+matrix[4]+matrix[7]+matrix[8]<sum)
{
sum=matrix[0]+matrix[2]+matrix[3]+matrix[4]+matrix[7]+matrix[8];
strcpy(order, "GCB");
}

printf("%s %lu\n", order, sum);


}


return 0;
}
Thanks...
[/c]

[MW]

I'm trying to submit my solution to problem 102, but for whatever reason I keep getting compile errors. I'm coding in C++ and I'm using the nice shell extension program.

I'm coding in Visual Studio .NET, but I'm also testing all code with g++ installed via Cygwin. Here's my command line for compiling with g++:

g++ -ansi -pedantic-errors -Wall main.cpp

I get no errors or warnings from neither g++ nor VS. My g++-version is:
g++ (GCC) 3.3.3 (cygwin special)

I read that Online Judge was supposed to email compiler output to your e-mail address, but I've received none. I suppose I could post my code here, but does anyone know how I can troubleshoot this?

I've previously submitted two other problems (100 & 101) and sucessfully passed.

[MW]

With some trial and error (quite hard when I don't know the compiler's output) I managed to track the 'bug' down to this single line:

#include <limits>

Why doesn't 'limits' exist?

[Krzysztof Duleba]

OJ compiles the code with old gcc 2.95, which has no <limits> header.

[A1]

Code: Select all

while(!feof(stdin)) 
   { 
      for(i=0; i<9&&!feof(stdin); i++) 
         scanf("%lu", &matrix[i]);

This part of your does not work well,

You can change it like this:
[c]while(scanf("%d%d%d%d%d%d%d%d%d",&matrix[0],&matrix[1],&matrix[2],&matrix[3],&matrix[4],&matrix[5],&matrix[6],&matrix[7],&matrix[8])==9)
{
//for(i=0; i<9&&!feof(stdin); i++)
// scanf("%lu", &matrix);
[/c]
you will get AC!

[eg_frx]

There are quite some questions that may have many equally good answers.

102 is an example.
For instance:
1 2 3 4 5 6 7 8 9
All 6 possible assigning schemes - GBC, GCB, CBG, CGB, BCG, BGC - will non-exceptionally generate the same moves - 30!

So these solutions should be equally treated as correct. That is if two or more solutions gives the same level of satisfaction to the problem, then any of them should be accepted.

However, I just proved that this is not the way the online judge works. I got WA at first, then I just did a little adjustment to the priority of the 6 permutations, and it's accepted. I would feel better, if it were my own fault.

[eg_frx]

There are quite some questions that may have many equally good answers.

102 is an example.
For instance:
1 2 3 4 5 6 7 8 9
All 6 possible assigning schemes - GBC, GCB, CBG, CGB, BCG, BGC - will non-exceptionally generate the same moves - 30!

So these solutions should be equally treated as correct. That is if two or more solutions gives the same level of satisfaction to the problem, then any of them should be accepted.

However, I just proved that this is not the way the online judge works. I got WA at first, then I just did a little adjustment to the priority of the 6 permutations, and it's accepted. I would feel better, if it were my own fault.

Sorry that I took 102 as an example. After I read the problem again, I found that there are instructions concerning this point. However, I found no such sentence in probem 104...

[eleusive]

There are quite some questions that may have many equally good answers.

102 is an example.
For instance:
1 2 3 4 5 6 7 8 9
All 6 possible assigning schemes - GBC, GCB, CBG, CGB, BCG, BGC - will non-exceptionally generate the same moves - 30!

So these solutions should be equally treated as correct. That is if two or more solutions gives the same level of satisfaction to the problem, then any of them should be accepted.

However, I just proved that this is not the way the online judge works. I got WA at first, then I just did a little adjustment to the priority of the 6 permutations, and it's accepted. I would feel better, if it were my own fault.

The problem statement tells you that if there are multiple optimal configurations, then the configuration that produces the lexographically (alphabetically first) answer is the correct one.

[lazenca]

when I test with some test inputs, I operated well..
but i submitted the code i got WA...hm..

here is my code...
[cpp]
/* @JUDGE_ID: 50047XX 102 C++ "Recycling Problem" */

#include <stdio.h>
#include <iostream>

using namespace std;

#define ONLINE_JUDGE

char bin_cmp(unsigned char bin, char a, char b, char c);

int main()
{
// total number of bottles will never exceed 2^31 (0 ~ INT_MAX)

unsigned long bottle[3][3]; // (b,g,c):bin1, (b,g,c):bin2, (b,g,c):bin2

char i, j, k; // index for bin

unsigned char final_bin = 0;

unsigned long move_cnt = 0;
unsigned long final_cnt;

while (cin >> bottle[0][0])
{
for (i = 1; i < 9; i++) // read one line(9 integer)
cin >> *(&bottle[0][0] + i);

final_cnt = 2147483647; // 2^31 - 1

for (i = 0; i < 3; i++) // first bin
{
for (j = (i+1)%3; i != j; j = (j+1)%3) // second bin
{

move_cnt = 0;

/* third bin: 3 - (i + j)
Brown: 0
Green: 1
Clear: 2
*/
k = 3 - (i + j);

move_cnt += bottle[1] + bottle[2];
move_cnt += bottle[0][j] + bottle[2][j];
move_cnt += bottle[0][k] + bottle[1][k];

if (move_cnt <= final_cnt)
{
if (!(move_cnt == final_cnt && bin_cmp(final_bin, i, j, k) < 0))
{
final_cnt = move_cnt;

final_bin = 0;
final_bin = (final_bin | i) << 2;
final_bin = (final_bin | j) << 2;
final_bin = (final_bin | k);
}
}
}
}


// print each bin's color
for (i = 2; i >= 0; i--)
{
switch ((final_bin >> (i * 2)) & 0x3) // 0x3: 11
{
case 0: cout << 'B'; break;
case 1: cout << 'G'; break;
case 2: cout << 'C'; break;
}
}

// minimum number of bottle movements
cout << ' ' << final_cnt << endl;

} // end of while

return 0;
}



char bin_cmp(unsigned char bin, char a, char b, char c)
{
// similar to strcmp

unsigned char i;
char *p;

for (i = 4, p = &a; (bin >> i) == *p; i -= 2, p += 4)
{
if (i == 0)
return 0;
bin = bin & (0xF >> (4 - i));
}

if ((bin >> i)*5 % 3 < *p*5 % 3)
return -1;
else
return 1;
}
[/cpp]

what's wrong? I couldn't find any problem..

[wolf]

Hi !
I can't seenothing wrong in your answers (they're the same like my AC program produce), but the reason of your WA can be in sending code especialy if you send it via e-mail (sometimes this can make problems). You also have to check if you are using the proper data type in your code.

Keep trying

[lazenca]

thanks for your advice
now, I got AC.

The Problem is function bin_cmp()...hm...@_@but i'm still confused

[Peter]

Hello, It's my first post. I new here. I was stopped by 102 problem. I've improving my program quite a long time ... spending much time. Now I know I am unable to find the mistake. All the inputs I could find work correctly ... I tried many things you recommended (using scanf and so on). I simply desire to finally find what is wrong with my code , why still WA ...
Thanks for all this people who'll help me.

This my code:

#include <iostream.h>

long b[9],z[4],x,i,j,k;

void main(){

while(!cin.eof()){
for(i=0;i<9;i++)
cin>>b;

cout<<endl;
z[0]=0;

for(i=0;i<3;i++)
for(k=0;k<3;k++)
for(j=0;j<3;j++){
if(i==j || i==k || k==j)
continue;

x=b+b[j+3]+b[k+6];

if(x>z[0]){
z[0]=x;
z[1]=i;
z[2]=j;
z[3]=k;
}
}

for(i=1;i<4;i++){
switch (z){
case 0:
cout<<"B";
break;
case 1:
cout<<"G";
break;
case 2:
cout<<"C";
};
}

x=0;
for(i=0;i<9;i++)
x=x+b;
cout<<" "<<x-z[0]<<endl;

};
}