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

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

thanks..

Post by kasturi » Wed Aug 11, 2004 10:36 pm

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

Post by Almost Human » Thu Aug 12, 2004 6:27 am

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
New poster
Posts: 1
Joined: Mon Sep 06, 2004 9:33 pm

Help for 102

Post by sms » Mon Sep 06, 2004 9:43 pm

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
New poster
Posts: 10
Joined: Mon Jul 19, 2004 6:35 pm

102 - Ecological Bin Packing

Post by vadiu » Fri Sep 17, 2004 6:09 pm

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

Post by MW » Sun Sep 26, 2004 2:18 pm

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

Post by MW » Sun Sep 26, 2004 2:41 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?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Sep 26, 2004 3:59 pm

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Mon Sep 27, 2004 2:51 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! :wink: 8)

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

I'm a little disappointed...

Post by eg_frx » Sat Oct 02, 2004 3:32 pm

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

Post by eg_frx » Sat Oct 02, 2004 5:48 pm

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

Post by eleusive » Thu Oct 07, 2004 7:35 pm

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.

User avatar
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...

Post by lazenca » Tue Oct 12, 2004 7:06 am

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

Post by wolf » Wed Oct 13, 2004 4:40 pm

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 :-D

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

Post by lazenca » Thu Oct 14, 2004 10:37 am

thanks for your advice :P
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...

Post by Peter » Fri Oct 15, 2004 1:00 pm

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 ... :cry:
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;

};
}

Post Reply

Return to “Volume 1 (100-199)”