102 - Ecological Bin Packing

[Krzysztof Duleba]

The interesting thing is that a code with

void main(){

compiles in ansi mode at all. The only possibility here is [cpp]int main()[/cpp].

[Joe]

the problem was in the less function, i used strcmp instead and got AC.
thnx,
Joe

[jromz03]

Hi, I keep getting WA (Wrong Answer) when I submit my code. I tried using the various data here in the boards (from page 1 to 14), and all my outputs are correct. Even the famous '1 2 3 4 5 6 7 8 9' gives 'BCG 30'.

Can anyone here help me? Thanks.

[c]
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>


int main(int argc, char *argv[])
{
int i, j, k;
int ii, jj, kk;
char bintype[] = "BGC";

unsigned long bin1[3],
bin2[3],
bin3[3];

double minmoves;
char binorder[5];
double currsum;
char currbinorder[5];
char dataline[150];

while (!feof(stdin))
{
minmoves = -1;
memset(binorder, 0, sizeof(binorder));
strcpy(binorder, "ZZZ");

memset(dataline, 0, sizeof(dataline));
fgets(dataline, sizeof(dataline)-1, stdin);

sscanf(dataline, "%U %U %U %U %U %U %U %U %U",
&bin1[0], &bin1[1], &bin1[2],
&bin2[0], &bin2[1], &bin2[2],
&bin3[0], &bin3[1], &bin3[2]);

for (i = 1; i < 4; ++i)
{
for (j = 1; j < 4; ++j)
{
if (i != j)
{
for (k = 1; k < 4; ++k)
{
if (i != k && j != k)
{
currsum = 0;
memset(currbinorder, 0, sizeof(currbinorder));
for (ii = 1; ii < 4; ++ii)
{
if (ii != i)
{
currsum += bin1[ii-1];
}
}

for (jj = 1; jj < 4; ++jj)
{
if (jj != j)
{
currsum += bin2[jj-1];
}
}

for (kk = 1; kk < 4; ++kk)
{
if (kk != k)
{
currsum += bin3[kk-1];
}
}

currbinorder[0] = bintype[i-1];
currbinorder[1] = bintype[j-1];
currbinorder[2] = bintype[k-1];

if (currsum < minmoves || minmoves == -1)
{
minmoves = currsum;
strcpy(binorder, currbinorder);
}
else
if (currsum == minmoves && strcmp(currbinorder, binorder) < 0)
strcpy(binorder, currbinorder);
}
}
}
}
}

printf("%s %1.0lf\n", binorder, minmoves);
}
return (0);
}

[/c]


Here's a sample data I passed to the program

Code: Select all

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8     	9
		5	10	5	20		10	5		10	20		10
		2147483648 2147483648 2147483648	2147483648	2147483648	2147483648	2147483648	2147483648	2147483648

The output is:

Code: Select all

BCG 30
BCG 30
CBG 50
BCG 12884901882

[xbeanx]

That last input causes my accepted program to crash. I think it is invalid.

[/code]

[Eduard]

help whith this it gives WA every time can someone help me?
program acm102;
var k,a:array[1..10] of longint;
min,i,j,sum,l:longint;
s:string;
begin
while not eof do
begin
for i:=1 to 9 do
read(a);
sum:=0;
min:=2000000000;
for i:=1 to 9 do
sum:=sum+a;
k[1]:=sum-a[1]-a[6]-a[8];
k[2]:=sum-a[1]-a[5]-a[9];
k[3]:=sum-a[3]-a[4]-a[8];
k[4]:=sum-a[3]-a[5]-a[7];
k[5]:=sum-a[2]-a[4]-a[9];
k[6]:=sum-a[2]-a[6]-a[7];
for i:=1 to 6 do
if k<min then begin min:=k;j:=i;end;
if j=1 then s:='BCG';
if j=2 then s:='BGC';
if j=3 then s:='CBG';
if j=4 then s:='CGB';
if j=5 then s:='GBC';
if j=6 then s:='GCB';
writeln(s,' ',min);
end;
end.

[Maarten]

your algorithm is correct.. i couldn't spot a mistake but it might be that the minimum number of bottles to move might be bigger than 2000000000. I suggest you initialize it with k[1]

[Eduard]

i initialised it whith k[1] but it gives WA again.i don't know what is wrong.
hhhhhheeeelllllpppppppppp.

[junjieliang]

Well, your problem is with input:

Code: Select all

for i := 1 to 9 read(a[i]);
readln; { You need this line }

I'm not too sure why you need this, but apparently if you don't your eof function will not be correct (you'll run the last case twice).

This problem is seen in many other problems where read is used instead of readln. (One of the reasons why I switched to C )

Hope this helps.

[Eduard]

thank you to match i got accepted whith your help and not only this problem i have same problem whith other problems to.
thank you.

[leefecu]

Code: Select all

#include "stdio.h"
#include "math.h"
#include "string.h"

#define Brown 1
#define Clear 2
#define Green 3
long b[3],g[3],c[3];
unsigned long min=pow(2,31);
long move[6]={0,};
char *comb[6]={"BGC","BCG","GBC","GCB","CBG","CGB"};


int main(void){
	int i,cnt=0,sc;
	scanf("%ld %ld %ld %ld %ld %ld %ld %ld %ld",&b[0],&g[0],&c[0],&b[1],&g[1],
			&c[1],&b[2],&g[2],&c[2]);
	move[0]=b[1]+b[2]+g[0]+g[2]+c[0]+c[1];
	move[1]=b[1]+b[2]+g[0]+g[1]+c[0]+c[2];
	move[2]=g[1]+g[2]+b[0]+b[2]+c[0]+c[1];
	move[3]=g[1]+g[2]+c[0]+c[2]+b[0]+b[1];
	move[4]=c[1]+c[2]+b[0]+b[2]+g[0]+g[1];
	move[5]=c[1]+c[2]+g[0]+g[2]+b[0]+b[1];
	for(i=0;i<6;i++){
		if(move[i]<min || (move[i]==min && strcmp(comb[cnt],comb[i])>0)){
			min=move[i];
			cnt=i;
		}
	}
	printf("%s %ld",comb[cnt],min);
	return 0;
}

I don't know what's wrong with my code...
please help me[/b][/cpp]

[Maarten]

there might be more than one test case in the input.. your program is only processing the first

[Morning]

jromz03,i got the same trouble,have u solved it?

[Morning]

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
    static String ReadLn (int maxLg)  
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        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);  
        return (new String (lin, 0, lg));
    }

    public static void main (String args[])  
	{
		int i,j;
		int p,q,r;
		int min=0;
		int minb=0;
		int max=0;
		int sum=0;
		int minOrder=123;
		String order="";
		String border="";
		String input;
		StringTokenizer idata;
		int matrix[][]=new int[3][3];
		while ((input = Main.ReadLn (255)) != null)
        {
          idata = new StringTokenizer (input);
          for(i=0;i<3;i++)
			  for(j=0;j<3;j++)
			  {
				matrix[i][j]=Integer.parseInt (idata.nextToken());
				sum+=matrix[i][j];
				min=sum;
			  }
		  
		  
		  for(p=0;p<3;p++)      
			  for(q=0;q<3;q++)  
			  {
				if(p==q) continue;
				for(r=0;r<3;r++)
				  {
					if(r==p||r==q) continue;
					minb=0;
					for(i=0;i<3;i++)
						for(j=0;j<3;j++)
						{
							 if (i==0&&j==p) continue;
							 if (i==1&&j==q) continue;
							 if (i==2&&j==r) continue;
							 minb+=matrix[i][j];
						}
							
					if (minb<min)
					{
						min=minb;
						minOrder=(p+1)*100+(q+1)*10+r+1;
						switch(minOrder)
						{
							case 123: 
								order="BGC ";
							break;
							case 132:
								order="BCG ";
							break;
							case 213:
								order="GBC ";
							break;
							case 231: 
								order="GCB ";
							break;
							case 312:
								order="CBG ";
							break;
							case 321:
								order="CGB ";
							break;
						}
					}
						
					if (minb==min)
					{
						switch((p+1)*100+(q+1)*10+r+1)
						{
							case 123: 
								border="BGC ";
							break;
							case 132:
								border="BCG ";
							break;
							case 213:
								border="GBC ";
							break;
							case 231: 
								border="GCB ";
							break;
							case 312:
								border="CBG ";
							break;
							case 321:
								border="CGB ";
							break;
						}
						if (border.charAt(0)<order.charAt(0)) 
						{
							order=border;
						}
						else if(border.charAt(0)==order.charAt(0)) 
						{
							if (border.charAt(1)<order.charAt(1)) 
							{
								order=border;
							}
							else if(border.charAt(1)==order.charAt(1)) 
							{	
								if (border.charAt(2)<order.charAt(2)) 
								{
									order=border;
								}
							}
						}
					}
				  }
			  }
			  System.out.println(order+min);
		}
	}
}

After i input"1 2 3 4 5 6 7 8 9"i got the correct answer,
and after i input"5 10 5 20 10 5 10 20 10"i got the correct answer,too
So,why i got WA?

[beeplove]

If I put 8 integers instead of 9
What should program do?
1. ignore that line
or,
2. would take the first integer from the next line.


In problem description it said,
"Integers on a line will be separated by one or more spaces"

[Maarten]

read the problem description:

The input consists of a series of lines with each line containing 9 integers.