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

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

Post by Bug! » Tue Jul 13, 2004 5:51 am

I think u should change ur limit
minTime=99999 -> minTime=2147483648
Good Luck...
Andre

Falldog
New poster
Posts: 4
Joined: Tue Jul 13, 2004 3:49 am

Post by Falldog » Wed Jul 14, 2004 3:21 am

Bug! wrote:I think u should change ur limit
minTime=99999 -> minTime=2147483648
Good Luck...
Andre
still can't....>"<

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

Post by Bug! » Tue Jul 20, 2004 3:29 am

I've submitted your code and change your mlongime=2147483647 (using long) or mlongime=2147483648 (unsigned long). And I got AC. I prefered if u change int into long... And U'll get ac... Good Luck....

Falldog
New poster
Posts: 4
Joined: Tue Jul 13, 2004 3:49 am

Post by Falldog » Wed Jul 28, 2004 4:30 am

Bug! wrote:I've submitted your code and change your mlongime=2147483647 (using long) or mlongime=2147483648 (unsigned long). And I got AC. I prefered if u change int into long... And U'll get ac... Good Luck....
thank you very much!
i got a AC
thanks~~~
^_^

Falldog
New poster
Posts: 4
Joined: Tue Jul 13, 2004 3:49 am

Post by Falldog » Wed Jul 28, 2004 4:41 am

Bug! wrote:I've submitted your code and change your mlongime=2147483647 (using long) or mlongime=2147483648 (unsigned long). And I got AC. I prefered if u change int into long... And U'll get ac... Good Luck....
thank you very much!
i got a AC
thanks~~~
^_^

Tourskey_911
New poster
Posts: 8
Joined: Sat Jun 12, 2004 4:12 am

Why Runtime error in 102?

Post by Tourskey_911 » Tue Aug 03, 2004 4:39 am

please give me some suggestion.Thank you.

Code: Select all

#include<iostream.h>

typedef struct
{
	int bi[3];
}bin;

int Step(int i,int j,int k);
bin b[4];

void main()
{
	int i,j,k,step,ii,jj,kk;
	float min;
	char glass[4]={'#','B','C','G'};
	for(i=1;i<=3;i++)
	{
		for(j=0;j<3;j++)
			cin>>b[i].bi[j];
	}
	min=100000;
	for(i=1;i<=3;i++)
	{
		for(j=1;j<=3;j++)
		{
			for(k=1;k<=3;k++)
			{
				if((i!=j)&&(i!=k)&&(j!=k))
				{
					step=Step(i,j,k);
					if(step<min)
					{
						min=(float)step;
						ii=i;jj=j;kk=k;
					}
				}
			}
		}
	}
	cout<<glass[ii]<<glass[jj]<<glass[kk]<<" "<<min;

}

int Step(int i,int j,int k)
{
	int step=0;
	int l,m;
	for(l=1;l<=3;l++)
	{
		for(m=0;m<3;m++)
			step=step+b[l].bi[m];
	}
	if(i==1)
		step=step-b[1].bi[i-1];
	if(i==2)
		step=step-b[1].bi[i];
	if(i==3)
		step=step-b[1].bi[i-2];
	if(j==1)
		step=step-b[2].bi[j-1];
	if(j==2)
		step=step-b[2].bi[j];
	if(j==3)
		step=step-b[2].bi[j-2];
	if(k==1)
		step=step-b[3].bi[k-1];
	if(k==2)
		step=step-b[3].bi[k];
	if(k==3)
		step=step-b[3].bi[k-2];
	return step;
}

outlaw
New poster
Posts: 2
Joined: Sat Aug 07, 2004 7:06 pm

102: compile error?

Post by outlaw » Sat Aug 07, 2004 7:10 pm

i get this error when i submit my code...
02746974_24.c: In function `int getnum()':
02746974_24.c:117: implicit declaration of function `int getchar(...)'
this is my code, its c++, starting at line 114.

Code: Select all

int getnum(){
	int number=0,temp[10],hold,flag=1,count=0,i;
	while(flag==1){
		hold=getchar();
		if((hold==' ') || (hold=='\n')){
			count--;
			flag=0;
		}
		else if((hold>='0') && (hold<='9')){
			hold-='0';
			temp[count]=hold;
			count++;
		}
	}
	if(count>=0){
		for(i=0;i<count+1;i++){
			hold=temp[i]*mypow(10,(count-i));
			number+=hold;
		}
		return number;
	}
	else{
		return (-1);
	}
}
any ideas on how to fix this error (which i dont get locally)?

Piotrek Mazur
New poster
Posts: 17
Joined: Thu Jul 15, 2004 10:55 am
Location: Poland, Rzeszow University of Technology

Post by Piotrek Mazur » Sat Aug 07, 2004 8:41 pm

Do you include stdio.h?

outlaw
New poster
Posts: 2
Joined: Sat Aug 07, 2004 7:06 pm

Post by outlaw » Sun Aug 08, 2004 12:26 am

yea, i noticed that i didnt shortly after i posted that :( thx anyway

Aalex
New poster
Posts: 2
Joined: Sun Aug 08, 2004 7:07 pm

Wrong Answer for 102

Post by Aalex » Sun Aug 08, 2004 7:16 pm

hey ppl,
I'd appreciate it if someone could help me out with this code. It works for the sample input.

Code: Select all

#include <iostream>
#include <string>
using namespace std;

long findMin(long value[])
{ 
	long min, index;
	min = value[0];
	index = 0;
	for (int i=0; i<6; i++)
	{
		if (value[i] < min)
		{
			min = value[i];
			index = i;
		}
	}
	return index;
}

int main()
{
	long bin1[3], bin2[3], bin3[3];
	long a, b, c;

	while (cin >> a >> b >> c)
	{
		
		bin1[0] = a;
		bin1[1] = b;
		bin1[2] = c;
		for (int i=0; i<3; i++)
			cin >> bin2[i];
		for (int j=0; j<3; j++)
			cin >> bin3[j];

		
		long bcg = bin2[0] + bin3[0] + bin1[2] + bin3[2] + bin1[1] + bin2[1];
		long bgc = bin2[0] + bin3[0] + bin1[2] + bin3[2] + bin1[1] + bin2[1];

		long cbg = bin2[2] + bin3[2] + bin1[0] + bin3[0] + bin1[1] + bin2[1];
		long cgb = bin2[2] + bin3[2] + bin1[1] + bin3[1] + bin1[0] + bin2[0];

		long gbc = bin2[1] + bin3[1] + bin1[0] + bin3[0] + bin1[2] + bin2[2];
		long gcb = bin2[1] + bin3[1] + bin1[2] + bin3[2] + bin1[0] + bin2[0];

		string list[6] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};
		long value[6] = { bcg, bgc, cbg, cgb, gbc, gcb };
		
       
		long index = findMin(value);

		cout <<list[index] << " " << value[index] << endl;
	}
	return 0;
}


Please help!

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Mon Aug 09, 2004 2:17 pm

I used my AC-ed source code to test data I generated randomly and I some differences. Looks like your answer is not minimal enough.

I hope it helps.

Input :

Code: Select all

12848 19770 21137 28663 9067 27681 19994 1430 19738
21409 10918 28079 27748 18094 18605 25346 31081 14515
11339 25614 8929 29300 17281 1993 14677 11587 11388
5646 26405 24114 7298 1653 15750 8475 19823 25249
567 18800 21597 11823 11350 4050 9159 4723 7
5401 9306 28826 31870 2243 10630 2931 3288 30106
642 22416 14029 18257 15411 4585 14720 15302 12210
19953 5005 11055 15764 9335 20750 15353 15095 1742
3747 17058 317 24146 27302 120 21099 11787 25986
26276 29311 20754 2355 12047 13381 19346 13064 24874
27570 14145 5320 6754 19421 29396 23977 18130 13207
2179 20045 24008 3154 26757 4854 24731 18217 5692
14891 17928 14022 17036 16459 25380 5262 21980 5351
11893 18518 30378 6906 9502 25280 6351 22883 15405
23182 8268 14577 13410 25868 9853 10546 22670 13164
18139 9830 30628 27919 31078 26457 27484 16957 26985
11488 27418 9279 3573 5479 208 3832 1493 28379
22516 7095 28135 1965 16308 5371 26984 7853 5608
21333 18652 23422 12896 15442 5527 1916 3609 291
12009 20102 31351 23172 3044 28464 26204 26471 27451
31910 32605 23799 15158 25853 24418 23745 25141 25145
21726 13898 1985 32546 22833 17050 24234 3544 1985
18665 7935 24234 16006 31637 7099 12701 19853 17149
25281 6360 18592 28681 16206 30311 15080 22349 7870
11235 6497 1749 24680 5100 1523 9131 692 12104
9134 14579 27756 2046 5939 21141 7801 23832 32286
21029 6346 2797 16409 24999 8914 11860 14152 12631
5916 18201 8981 13827 32058 2608 7195 2231 11309
4728 30474 6447 17469 26140 4175 25774 25319 15664
7994 25997 17751 8391 23932 11564 16401 9529 21136
27498 14780 11633 26305 16917 6064 16444 30317 18623
19738 8942 2178 1182 142 27542 11972 17286 22838
1264 19213 24542 14436 9721 30142 31956 15326 21934
7071 17114 25203 31035 12821 23581 28685 17711 15151
14458 4454 27842 13576 6466 15358 22078 21671 25677
21324 4723 31150 4286 26560 21075 12937 31209 4217
19957 23995 13969 32040 21024 9988 2630 19217 23302
5217 28345 32439 30687 5810 19731 12199 26094 21318
31368 14154 26567 28198 10421 6492 21067 13614 29743
29168 7446 26399 30513 30300 13285 12364 5069 23632
19978 9476 12384 12890 25943 26533 10661 19069 19511
28621 12952 2018 32729 6998 2657 21312 21114 16689
11918 2051 29424 2814 20400 6598 14922 23310 17539
26237 5284 19456 23081 27077 733 29132 148 30933
21877 14261 8099 6512 3264 1644 16284 7688 11124
7072 11818 3458 11008 11834 32238 9250 6208 15748
2016 10149 1967 6754 5124 2357 10061 7846 2155
4705 22179 14914 25832 1342 6777 18061 8969 24863
3196 16387 12803 11500 24656 22829 17076 31276 6865
1773 11356 15156 27699 27881 4721 18819 9125 32623
15104 3428 14891 12445 3875 1161 1802 30318 7518
264 23009 23552 18875 14634 19060 23035 27538 31693
32211 20812 5327 20736 29052 8136 14697 2002 17211
15674 30340 555 19945 31407 18144 23755 19679 21089
19634 7290 18738 18994 13173 6564 904 30459 15035
10527 31820 11814 3627 2450 14108 7884 13478 19143
5972 17691 21907 8562 17460 12912 24701 18813 22957
9962 14810 22006 16648 8242 2085 19736 2306 22762
22866 3653 7278 17887 7663 7385 9495 11846 418
3353 17666 30804 14704 6118 419 5030 13696 16962
13551 875 29413 8380 1556 7980 11659 17834 22175
13025 21290 8316 12282 14432 25873 30209 13148 16612
2148 12718 17626 23015 26591 30598 644 32299 8453
7921 3755 17918 14632 29702 27833 25856 7955 11012
2530 23087 20865 19574 6104 6813 8669 14966 13248
28005 5321 20810 18939 11915 28820 3482 8964 27860
8300 17360 21366 10384 11532 29695 5004 23087 507
2863 19973 25815 4168 6275 29016 12364 14143 13288
31788 18448 2455 23287 15631 26624 8577 24192 17382
18497 23239 11280 15030 4561 26157 19895 175 22156
28414 26072 6712 22505 14845 19117 31120 3205 12375
20271 26814 11374 9298 13856 30689 27732 1604 5795
17982 24183 16482 9785 1553 7285 17048 29455 31045
6191 357 14951 16914 448 25758 31858 4293 12051
30999 29737 11076 20688 5783 29813 21129 26193 29560
16031 20617 4888 15559 12958 10599 15074 27253 29639
29426 7885 508 2043 18485 24960 18672 11125 11742
2934 4553 1239 24648 30777 21219 14321 26035 32712
10157 17090 10846 2353 24812 1628 27196 32557 19296
23625 22122 21520 2270 32440 3401 10150 9776 18951
1983 30464 20335 11052 14397 6863 16853 11701 16952
7633 14575 30487 2616 13459 17251 10595 11905 20676
25731 739 17566 32146 11344 6762 23985 26603 17930
10769 27219 10971 16244 10091 26372 6227 15373 11451
28973 16712 21774 5766 31509 4924 29730 12387 9812
19857 23777 5013 6651 19458 26983 843 5541 6271
23361 21996 25189 15822 22703 2510 1248 29852 24823
21568 15091 26607 11588 18041 2121 29194 11604 7589
1413 27434 32004 29815 16571 5396 6301 31178 8413
5636 25640 23096 28603 9016 29898 28416 25625 30901
21186 20872 26511 12575 5662 31810 13996 464 27401
23554 27084 25238 17754 13871 2892 14331 28338 11765
12748 10172 21035 23623 15743 4505 3714 17491 26782
29463 900 1635 30401 21836 26608 19826 23721 3209
21166 30985 5608 30049 2222 4271 15124 22813 6803
9515 18309 3087 1988 11364 10591 10055 10030 19081
9457 20777 26401 8310 5487 15300 95 19491 25655
29241 9690 2108 718 19418 15355 28464 913 19434
2378 28693 26083 32148 16519 8979 32678 6372 19376
2880 19585 10229 21130 8388 8637 5162 3416 22391
My Output:

Code: Select all

GBC 92157
CBG 108887
GBC 65806
GBC 75461
CGB 39970
GBC 53319
GBC 64689
BCG 58254
GBC 64372
BGC 98211
BCG 82824
CGB 54141
BCG 76058
CBG 86949
BGC 79324
CGB 126287
GBC 31779
CGB 50408
CGB 62308
CBG 117274
BGC 144866
GCB 84619
CGB 86707
BCG 92789
GBC 29430
BCG 90407
BGC 60478
BGC 53043
GBC 92583
CGB 84611
CBG 100326
BCG 47254
GCB 87223
CBG 104423
CBG 88491
BCG 83873
GBC 86785
CBG 92620
GBC 109529
BGC 95076
BCG 90865
GBC 82720
CGB 64230
BGC 77834
BGC 54488
GCB 55328
GCB 25862
GBC 54768
BCG 89287
GBC 77475
CBG 32888
GBC 108083
BGC 71710
GCB 108349
CBG 62600
GBC 60261
CGB 86907
GBC 64337
BCG 46394
CBG 49548
CBG 57796
GCB 77815
CBG 81152
CGB 73108
GBC 59947
BGC 86336
BCG 66153
GCB 66552
BCG 85780
GCB 71699
GCB 88056
GCB 62198
GBC 89805
GCB 54848
BCG 117973
GBC 86803
BCG 59335
BGC 92015
CGB 83081
BGC 69239
GBC 72132
CGB 74656
CBG 86491
GCB 74899
CGB 78574
BCG 62013
BGC 96617
CGB 69561
CBG 65528
GBC 121687
GCB 93799
CBG 93497
CBG 73664
BCG 77807
GBC 71204
BGC 54060
GBC 76231
BGC 57248
GBC 93009
GBC 38712
your output:

Code: Select all

GBC 92157
CBG 108887
GBC 65806
GBC 75461
CGB 39970
GBC 53319
GBC 64689
BCG 58254
GBC 64372
GCB 99370
BCG 82824
CGB 54141
BCG 76058
CBG 86949
BCG 85833
CGB 126287
GBC 31779
CGB 50408
CGB 62308
CBG 117274
BCG 146305
GCB 84619
CGB 86707
BCG 92789
GBC 29430
BCG 90407
BCG 75042
CGB 54092
GBC 92583
CGB 84611
CBG 100326
BCG 47254
GCB 87223
CBG 104423
CBG 88491
BCG 83873
GBC 86785
CBG 92620
GBC 109529
CGB 109113
BCG 90865
GBC 82720
CGB 64230
CGB 86416
GCB 58564
GCB 55328
GCB 25862
GBC 54768
BCG 89287
GBC 77475
CBG 32888
GBC 108083
GBC 91425
GCB 108349
CBG 62600
GBC 60261
CGB 86907
GBC 64337
BCG 46394
CBG 49548
CBG 57796
GCB 77815
CBG 81152
CGB 73108
GBC 59947
BCG 88327
BCG 66153
GCB 66552
BCG 85780
GCB 71699
GCB 88056
GCB 62198
GBC 89805
GCB 54848
BCG 117973
GBC 86803
BCG 59335
GBC 96525
CGB 83081
CGB 80145
GBC 72132
CGB 74656
CBG 86491
GCB 74899
CGB 78574
BCG 62013
CBG 96641
CGB 69561
CBG 65528
GBC 121687
GCB 93799
CBG 93497
CBG 73664
BCG 77807
GBC 71204
GBC 54642
GBC 76231
GCB 71832
GBC 93009
GBC 38712
I hope it helps

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Tue Aug 10, 2004 2:57 am

I suspect this line

[c]
long bgc = bin2[0] + bin3[0] + bin1[2] + bin3[2] + bin1[1] + bin2[1];
[/c]

should be changed to this:

[c]
long bgc = bin1[1] + bin1[2] + bin2[0] + bin2[2] + bin3[0] + bin3[1];
[/c]

[EDIT]
For problems like these, it is very easy to just screw up one index
somewhere and have trouble finding it later. Since you have to keep
track of more indices by keeping track of which things have to be
moved out, you probably will have an easier time debugging if you
keep track of which things you should leave in. The fact that G comes
before C is also confusing, so why not just put it in a #define. What I
mean by this is:

[c]
#define B 0
#define G 1
#define C 2
/* keep track of bins as double index array, first index is bin, second is B / G / C*/
int i,j,sum=0;
for (i=0;i<3;i++) for (j=0;j<3;j++) sum += bins[j];
bgc = bins[0] + bins[1][G] + bins[2][ C ];
bcg = bins[0] + bins[1][ C ] + bins[2][G];
...etc...
result = findMax(bgc,bcg...);
result = sum - result;
[/c]

i wrote that on the spot, so forgive any typos..
but my point is that (at least for me) it is easier to keep track of
which color belongs to each bin than the two colors that don't belong
to each bin.
[/EDIT]

Aalex
New poster
Posts: 2
Joined: Sun Aug 08, 2004 7:07 pm

Thank You

Post by Aalex » Tue Aug 10, 2004 6:23 pm

Whoa!!
Both of you put in a lot of effort!

I submitted the solution before I got to read your post Minilek, but I manged to get it AC-ed.
Thank you 'Almost Human', for the sample input and output. I looked through it and figured something was wrong with the combination 'bgc'.

I changed this line...

[cpp]
long bgc = bin2[0] + bin3[0] + bin1[2] + bin3[2] + bin1[1] + bin2[1];

[/cpp]

to this ...
[cpp]
long bgc = bin2[0] + bin3[0] + bin1[1] + bin3[1] + bin1[2] + bin2[2];
[/cpp]

And Minilek you're right, keeping track of what's in the bin rather than what's not, is much easier. Also the #define tip was great. I'll try to use it next time. (hey, I am just a noob)

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

Problem 102

Post by kasturi » Wed Aug 11, 2004 6:25 am

i am new to this forum. i tried doing the problem 102. but got WA 4 times.
coudl anyone please help me with what is the problem with the following code. please.[cpp]
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
int a[10]={0},b[6];
while(cin>>a[1])
{
for(int i=2;i<10;i++)
scanf("%d ",&a);
int total=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9];
b[0]=total-(a[1]+a[5]+a[9]);//cout<<b[0]<<" "<<" BGC\n";
b[1]=total-(a[1]+a[6]+a[8]);//cout<<b[1]<<" "<<" BCG\n";
b[2]=total-(a[2]+a[4]+a[9]);//cout<<b[2]<<" "<<" GBC\n";
b[3]=total-(a[2]+a[6]+a[7]);//cout<<b[3]<<" "<<" GCB\n";
b[4]=total-(a[3]+a[4]+a[8]);//cout<<b[4]<<" "<<" CBG\n";
b[5]=total-(a[3]+a[5]+a[7]);//cout<<b[5]<<" "<<" CGB\n";
int min=0;
for(int i=0;i<6;i++)
if(b<b[min])
min=i;
switch(min)
{
case 0:
printf("\nBGC");
break;
case 1:
printf("\nBCG");
break;
case 2:
printf("\nGBC");
break;
case 3:
printf("\nGCB");
break;
case 4:
printf("\nCBG");
break;
case 5:
printf("\nCGB");
break;
}
printf(" %d",b[min]);
}
return 0;
}
[/cpp]
i tried those random test cases and tested them with my pgm output. but no improvement. please help me :cry:
Life is like that

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed Aug 11, 2004 11:41 am

I thought that output should be the smallest lexicographically, so if there is 2 configuration ( e.g. : BGC and BCG yield the same size ), "BCG" should be printed ...

I hope it helps

Post Reply

Return to “Volume 1 (100-199)”