102 - Ecological Bin Packing

Moderator: Board moderators

beeplove
New poster
Posts: 17
Joined: Tue Sep 30, 2003 9:28 pm
Location: Boston, MA, USA
Contact:
So the line have not 9 integers should be ignored.. right?

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
it means there are only lines with 9 integers on them

beeplove
New poster
Posts: 17
Joined: Tue Sep 30, 2003 9:28 pm
Location: Boston, MA, USA
Contact:

Sample input and output of # 102

I am getting expected output from code. But still getting WA.
Can someone please post some sample input with output.

Thanks

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
Simply search the board. At the top of the page you have some links (FAQ, search, users, etc.) so click search and look for problem 102 - there are many messages on this problem on the board.
Good luck!

slonko
New poster
Posts: 2
Joined: Tue Oct 14, 2003 4:02 pm

102 WA

hi!
i have only WA? why? can you help me find my mistake?
THANKS
[c]
#include <stdio.h>

void perm(short int i)
{
char tab[4];
switch (i)
{
case 0: tab[0]='B';tab[1]='C';tab[2]='G'; break;
case 1: tab[0]='B';tab[1]='G';tab[2]='C'; break;
case 2: tab[0]='C';tab[1]='B';tab[2]='G'; break;
case 3: tab[0]='C';tab[1]='G';tab[2]='B'; break;
case 4: tab[0]='G';tab[1]='B';tab[2]='C'; break;
case 5: tab[0]='G';tab[1]='C';tab[2]='B'; break;
}
tab[3]=0;
printf("%s",tab);
}

struct kosz{
unsigned long int b;
unsigned long int g;
unsigned long int c;
};

unsigned long int zlicz(struct kosz koszyk[],short int b, short int g, short int c)
{
unsigned long int x=0;
switch(b)
{
case 0: x+=koszyk[1].b+koszyk[2].b; break;
case 1: x+=koszyk[0].b+koszyk[2].b; break;
case 2: x+=koszyk[0].b+koszyk[1].b; break;
}
switch(g)
{
case 0: x+=koszyk[1].g+koszyk[2].g; break;
case 1: x+=koszyk[0].g+koszyk[2].g; break;
case 2: x+=koszyk[0].g+koszyk[1].g; break;
}
switch(c)
{
case 0: x+=koszyk[1].c+koszyk[2].c; break;
case 1: x+=koszyk[0].c+koszyk[2].c; break;
case 2: x+=koszyk[0].c+koszyk[1].c; break;
}
return x;
}

main()
{
struct kosz tab[3];
while(scanf("%d %d %d %d %d %d %d %d %d", &tab[0].b,
&tab[0].g, &tab[0].c, &tab[1].b, &tab[1].g,
&tab[1].c, &tab[2].b, &tab[2].g, &tab[2].c )==9)
{
unsigned long int ruch[6],mina;
short int i,minb;

ruch[5]=zlicz(tab,0,1,2);
ruch[4]=zlicz(tab,0,2,1);
ruch[3]=zlicz(tab,1,0,2);
ruch[2]=zlicz(tab,1,2,0);
ruch[1]=zlicz(tab,2,0,1);
ruch[0]=zlicz(tab,2,1,0);

mina=ruch[5];
for (i=5;i>=0;i--)
{
if (mina>=ruch)
{
mina=ruch;
minb=i;
}
}
perm(minb);
printf(" %d\n", mina);
}
}
[/c]

secret-mission
New poster
Posts: 4
Joined: Tue Jul 29, 2003 10:56 am

p102 (EBP) - Pascal - WA - Tested [Unsolved]

I have read almost all of the topic in this forum, and i got a lot of information from this forum. I have tested my code in some test case which is provided by the previous topic but i still got Wrong Answer. I really don't know how to solve this and i have thought hard for this problem. I really appreciate if someone would like to give me idea, or a suggestion. Thank you very much.

[pascal]
program p102(input,output);
{\$IFDEF ONLINE_JUDGE}
type tint = integer;
{\$ELSE}
type
tint = longint;
{\$ENDIF}
var
b1,b2,b3,total,i,j,k,l,min : tint;
bin : array [1..4,1..4] of tint;
name : string[3];
temp : string;
temp2 : tint;
err : word;
inp : string;
success : boolean;
begin
while not eof(input) do
begin
name := 'BCG';
for i := 1 to 3 do for j := 1 to 3 do bin[j] := 0;
i := pos(' ',inp);
j := 0;
k := 1;
l := 1;
total := 0;
success := true;
if i = 1 then while i = 1 do
begin
delete(inp,1,1);
i := pos(' ',inp);
end;
while i <> 0 do
begin
if i = 1 then while i = 1 do
begin
delete(inp,1,1);
i := pos(' ',inp);
end;
if length(inp) <> 0 then
begin
temp := copy(inp,1,i-1);
val(temp,temp2,err);
if ((total+temp2) < 0) then
begin
success := false;
break;
end
else inc(total,temp2);
if l = 1 then bin[k][1] := temp2
else if l = 2 then bin[k][3] := temp2
else bin[k][2] := temp2;
delete(inp,1,i);
inc(l);
if l > 3 then
begin
l := 1;
if (k < 4) and (l < 2) then inc(k)
else
begin
success := false;
break;
end;
end;
inc(j);
i := pos(' ',inp);
end
else break;
end;
if success then for i := 1 to 3 do for k := 1 to 3 do if (bin[k] = 0) then
begin
if (i = 3) and (k <> 2) then success := false
else if (i = 2) or (i = 1) then success := false;
end;
if success then
begin
if (length(inp) <> 0) and (bin[3][2] = 0) then
begin
val(inp,temp2,err);
if ((total+temp2) < 0) then success := false
else inc(total,temp2);
if success then bin[k][2] := temp2;
end;
end;
if success then
begin
min := -1;
for i := 1 to 3 do for j := 1 to 3 do if i <> j then for k := 1 to 3 do if (k <> i) and (k <> j) then
begin
l := total-bin[1]-bin[2][j]-bin[3][k];
if (l < min) or (min = -1) then
begin
min := l;
b1 := i;
b2 := j;
b3 := k;
end;
end;
writeln(name[b1]:1,name[b2]:1,name[b3]:1,' ',min:1);
end;
end;
end.
[/pascal]

Code: Select all

``````INPUT (Without "")

"1 2 3 4 5 6 7 8 9"
"5 10 5 20 10 5 10 20 10"
"1 2 3 4 5 6 7 8 9 "
" 1 2 3 4 5 6 7 8 9"
"     1 2 3 4 5 6 7 8 9      "
"    1     2     3     4     5      6    7     8      9 "
"1000 200 1500 350 5000 1000 1000 2000 13000"
"60 20 1000 1000 60 20 10000 20 500"
"20 1000 50 2000 50 500 1500 20 3000"
"20 1000 50 2000 50 5000 1500 20 300"
"0"
"5 4 3 2 1"
"1"
"1 2 3 4 5"
"0"
"5 1 2 3 4"
"1"
"4 3 2 1 5"
"4 3 2 1 5"
"2"
"1 2 3 4 5"
"0"
"       2147483648 2147483648 2147483648 2147483648 2147483648 2147483648 2147483648 2147483648 2147483648"
"11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999"
``````

Code: Select all

``````OUTPUT

BCG 30
CBG 50
BCG 30
BCG 30
BCG 30
BCG 30
BCG 6050
CGB 1620
GBC 2140
GCB 2440
BCG 333333330
``````

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

102-Ecological Bin Packing - compile error

could anyone tell me why I keep on receiving a compile error. The code compiles under the most recent mingw g++.

[cpp]
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<utility>
#include<cstdio>

using namespace std;

typedef vector<int> VI; typedef vector<vector<int> > VVI;
typedef vector<string> VS; typedef vector<vector<string> > VVS;
typedef pair<int, int> PII;

string labels = "BGC";
int order[3] = {0, 1, 2};

int main() {
string s;

while(getline(cin, s)) {
istringstream is(s);
vector<long long> bins(3), bottles(10);
long long m = 100000000000000;
int n;
string s_m;

for(int i = 0; i < 9; i++) {
is>>n;
bottles = n; bins[i%3] += n;
}

do {

long long curr=(bins[0]+bins[1]+bins[2])
-(bottles[order[0]]+bottles[3+order[1]]+bottles[6+order[2]]);
string t; t+=labels[order[0]]; t+=labels[order[1]]; t+=labels[order[2]];

if(curr < m) {
m = curr;
s_m = t;
}
else if(curr == m && s_m > t)
s_m = t;

}while(next_permutation(order, order+3));

cout<<s_m<<" "<<m<<endl;
}
return 0;
}
[/cpp]

Nikolay Archak
New poster
Posts: 6
Joined: Tue Dec 02, 2003 6:43 am
Contact:
Hi!
Im not sure but may be you should change

next_permutation(order, order+3)

to

next_permutation((VI::iterator)order, (VI::iterator)(order+3))

BTW, you can submit your solutions by email, in this case you will receive the reply with exact description of compilation error.

uppkastaren
New poster
Posts: 4
Joined: Mon Dec 08, 2003 5:37 pm
Location: Sweden

WA for p102

Hi
I would like som help on this. The problem is supposed to be very simple and I think I have a correct solution but I get WA from the judge.
[java]
import java.io.*;
import java.util.*;

class RecycleBin {
public int b,g,c;
RecycleBin(int brown, int green, int clear) {
this.b=brown;
this.g=green;
this.c=clear;
}
}

class Main {
RecycleBin bin1,bin2,bin3;

byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

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

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

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

void Begin() {
String input;
String output;
StringTokenizer data;
int[] moves = new int[6];
int min;

while((input = Main.ReadLn(255)) != null) {
if(input.length()<17)
break;
data = new StringTokenizer(input);
bin1 = new RecycleBin(
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()));
bin2 = new RecycleBin(
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()));
bin3 = new RecycleBin(
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()));

moves[0] = bin2.b + bin3.b + bin1.c + bin3.c + bin1.g + bin2.g; // BCG
moves[1] = bin2.b + bin3.b + bin1.g + bin3.g + bin1.c + bin2.c; // BGC
moves[2] = bin2.c + bin3.c + bin1.b + bin3.b + bin1.g + bin2.g; // CBG
moves[3] = bin2.c + bin3.c + bin1.g + bin3.g + bin1.b + bin2.b; // CGB
moves[4] = bin2.g + bin3.g + bin1.b + bin3.b + bin1.c + bin2.c; // GBC
moves[5] = bin2.g + bin3.g + bin1.c + bin3.c + bin1.b + bin2.b; // GCB
min = moves[0];
output = "BCG ";
if(moves[1]<min) { min = moves[1]; output = "BGC "; }
if(moves[2]<min) { min = moves[2]; output = "CBG "; }
if(moves[3]<min) { min = moves[3]; output = "CGB "; }
if(moves[4]<min) { min = moves[4]; output = "GBC "; }
if(moves[5]<min) { min = moves[5]; output = "GCB "; }
System.out.println(output + min);
}
}
}
[/java]
According to some of the messages I have read here there could be runtime errors that generate WA. Could someone please hint in the right direction here?

Thanx /Ulf

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:
I wrapped your code in a try/catch block and had the catch do a

while( true );

The purpose, well, if you're currently getting WA, then if an exception is thrown, you'll get TLE instead. But on your program, no dice. It still exits after like 1.3 seconds with WA. Looking through your code, I don't see any glaring errors or something, but I can pretty safely say that it's not a runtime error.

uppkastaren
New poster
Posts: 4
Joined: Mon Dec 08, 2003 5:37 pm
Location: Sweden
Hi Morning
Did you solve it? I am working with the same problem and in Java and I'm also getting WA all the time eaven thou I think its no error in my code.
Se my solution at the Java forum: http://online-judge.uva.es/board/viewtopic.php?t=4577

/Ulf

uppkastaren
New poster
Posts: 4
Joined: Mon Dec 08, 2003 5:37 pm
Location: Sweden

Im getting frustrated here. I have rewritten the code and submitted it a couple of times now but still getting WA. Are there suposed to be any ticky input to solve or what? I'm pretty sure of that I'm doing the calculation in the right way. Pleas give me som more help or just tell me that Java is not compatible with p102...

Spike, thank you very much for your feedback. I will definetly use try/catch and while(true) in the future. Smart!

/U

uppkastaren
New poster
Posts: 4
Joined: Mon Dec 08, 2003 5:37 pm
Location: Sweden

Got AC now!

Aaarrrrggg! The compiler or VM used for Java by the judge is quite buggy! I replaced [java]
bin1 = new RecycleBin(
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()),
Integer.parseInt(data.nextToken()));
[/java]
with [java]
int t1,t2,t3;
t1 = Integer.parseInt(data.nextToken());
t2 = Integer.parseInt(data.nextToken());
t3 = Integer.parseInt(data.nextToken());
bin1 = new RecycleBin(t1,t2,t3);
[/java]
and now I got AC.

Could someone with a little qualification than me please help the judge-team to install a better java environment with 1.4 support.

/U

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:
I've had similar errors like this using UVA's java compiler. Sometimes a program will crash or perform differently when running a command on one line instead of breaking it into seperate lines. Logically your code should be, and (using a good compiler) is the same, but their compiler must mix up code or something, because I can assure you that it's probably just a strange compiler issue. Let's just hope that the UVA guys will surprise us by adding 1.5 support as soon as it comes out or something.