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

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

Post by 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
New poster
Posts: 6
Joined: Fri Aug 08, 2003 2:06 pm
Location: Egypt

AC

Post by Joe »

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

jromz03
New poster
Posts: 1
Joined: Fri Sep 19, 2003 11:33 am

P102 - WA, Please help.

Post by 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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

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

[/code]

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

problem 102 wa[pascal]

Post by 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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by 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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

i initialised it whith k[1] but it gives WA again.i don't know what is wrong.
hhhhhheeeelllllpppppppppp. :cry: :cry:
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by 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 :lol: )

Hope this helps.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by 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.
:P :P :P
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

leefecu
New poster
Posts: 1
Joined: Thu Oct 02, 2003 2:48 pm
Location: New Zealand

help me 102... i got WA

Post by 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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten »

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

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning »

jromz03,i got the same trouble,have u solved it?
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

P102 WYI WA?[JAVA]

Post by 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?
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

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

Input of 102

Post by 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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten »

read the problem description:
The input consists of a series of lines with each line containing 9 integers.

Post Reply

Return to “Volume 1 (100-199)”