102 - Ecological Bin Packing

Moderator: Board moderators

kasturi
New poster
Posts: 3
Joined: Sat Jan 24, 2004 5:05 am

thanks..

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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
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."

sms
New poster
Posts: 1
Joined: Mon Sep 06, 2004 9:33 pm

Help for 102

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]

New poster
Posts: 10
Joined: Mon Jul 19, 2004 6:35 pm

102 - Ecological Bin Packing

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
New poster
Posts: 3
Joined: Sun Sep 26, 2004 2:09 pm

102: Compile Error

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
New poster
Posts: 3
Joined: Sun Sep 26, 2004 2:09 pm
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
OJ compiles the code with old gcc 2.95, which has no <limits> header.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

I'm a little disappointed...

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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Re: I'm a little disappointed...

eg_frx wrote: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
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States

Re: I'm a little disappointed...

eg_frx wrote: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
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

#102 Ecological Bin Packing(WA), help me...

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..
I see the red...
I saw the rain..

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
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
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:
now, I got AC.

The Problem is function bin_cmp()...hm...@_@but i'm still confused
I see the red...
I saw the rain..

Peter
New poster
Posts: 3
Joined: Fri Oct 15, 2004 12:28 pm
Location: Poland, Wloclawek

102 - you are the last resort...

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;

};
}