Page 1 of 33

Posted: Wed Dec 19, 2001 8:32 pm
by konsept
Can someone please tell what is wrong with this problem, because I can't figure out why the online judge fails to accept it.

#include <stdio.h>
#include <string.h>

int box[4][4];

int bestcost;
char bestbin[16];

int check( int a,int b,int c ){
int cost=0;

cost+=box[1][1]+box[1][2]+box[1][3]-box[1][a];
cost+=box[2][1]+box[2][2]+box[2][3]-box[2];
cost+=box[3][1]+box[3][2]+box[3][3]-box[3][c];

return cost;
}

void main( void ){

while ( scanf( "%d %d %d", &box[1][1],&box[1][2],&box[1][3] )>0 ){
scanf( "%d %d %d", &box[2][1],&box[2][2],&box[2][3] );
scanf( "%d %d %d", &box[3][1],&box[3][2],&box[3][3] );

bestcost=1000000;

if ( check(1,3,2)<bestcost ){
bestcost=check(1,3,2);
strcpy( bestbin, "BCG" );
}

if ( check(1,2,3)<bestcost ){
bestcost=check(1,2,3);
strcpy( bestbin, "BGC" );
}

if ( check(3,1,2)<bestcost ){
bestcost=check(3,1,2);
strcpy( bestbin, "CBG" );
}

if ( check(3,2,1)<bestcost ){
bestcost=check(3,2,1);
strcpy( bestbin, "CGB" );
}


if ( check(2,1,3)<bestcost ){
bestcost=check(2,1,3);
strcpy( bestbin, "GBC" );
}

if ( check(2,3,1)<bestcost ){
bestcost=check(2,3,1);
strcpy( bestbin, "GCB" );
}

printf( "%s %dn", bestbin, bestcost );
}

}

Posted: Thu Dec 20, 2001 5:18 am
by bigredteam2000
We thought we got it but the judges did not.
I am trying all the six different possibilities.
I still donot understand why they talk about dynamic programming at the beginning of the problem.

#include<iostream.h>

int main()
{
long int b1,g1,c1;
long int b2,g2,c2;
long int b3,g3,c3;
long int sum[7];
int i;
int indexofmin;
long int min;

while(cin>>b1)
{
cin>>g1>>c1;
cin>>b2>>g2>>c2;
cin>>b3>>g3>>c3;

sum[1] = c1+g1+b2+c2+b3+g3;
sum[2] = g1+c1+b2+g2+b3+c3;
sum[3] = b1+g1+g2+c2+b3+c3;
sum[4] = b1+g1+b2+c2+g3+c3;
sum[5] = b1+c1+g2+c2+b3+g3;
sum[6] = b1+c1+g2+b2+g3+c3;

min = sum[1];
indexofmin = 1;
for(i = 2; i<=6;i++)
{
if( min>=sum)
{
min = sum;
indexofmin = i;

}
}
switch(indexofmin)
{
case 1:
cout<<"BGC "<<min<<endl;
break;
case 2:
cout<<"BCG "<<min<<endl;
break;
case 3:
cout<<"CBG "<<min<<endl;
break;
case 4:
cout<<"CGB "<<min<<endl;
break;
case 5:
cout<<"GBC "<<min<<endl;
break;
case 6:
cout<<"GCB "<<min<<endl;
break;
}
}


return 0;
}

Posted: Thu Dec 20, 2001 1:09 pm
by cyfra
Hi

I know what's wrong with your program.

If there are two posibilities you have to print this one which is earlier in alphabetical order.

And your program will write BGC instead of BCG. (if they have the same values).
You have to change 2 cases (1 and 2) in your program and everything will be OK.

Posted: Fri Apr 05, 2002 5:21 pm
by FireDragon
Can someone tell me what is wrong with the program.If there are two posibilities I do print the one which is earlier in alphabetical order.
Thank you.

#include<stdio.h>
#include<iostream.h>
long r1,r2,r3;
long bin[4][4];
long total;
char mark[5]=" BCG";

long count(long r1,long r2,long r3){
return total-bin[1][r1]-bin[2][r2]-bin[3][r3];
}

void main(){
while(!feof(stdin)){
long i,j,o,t,min=2147483647;
for (i=1;i<=3;i++) t=scanf("%ld%ld%ld",&bin[1],&bin[3],&bin[2]);//Not the ori_order
if (t!=3) break;
total=0;
for (i=1;i<=3;i++) for (j=1;j<=3;j++) total+=bin[j];
for (i=1;i<4;i++)
for (j=1;j<4;j++)
if (i!=j) for (o=1;o<4;o++) if (o!=i&&o!=j)
if ((t=count(i,j,o))<min) {
min=t;
r1=i;r2=j;r3=o;
}
cout<<mark[r1]<<mark[r2]<<mark[r3]<<' '<<min<<endl;
}
}


<font size=-1>[ This Message was edited by: FireDragon on 2002-04-05 17:30 ]</font>

Posted: Sat Apr 06, 2002 5:58 pm
by FireDragon
I still don't know why I got WA.
Here are some of my test data.

1 2 3 4 5 6 7 8 9
1000 200 1500 350 5000 1000 1000 2000 13000
5 10 5 20 10 5 10 20 10
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

And My output.
BCG 30
BGC 6050
CBG 50
CGB 1620
GBC 2140
GCB 2440


_________________
I failed over and over and over again.
And that's why I succeed.

<font size=-1>[ This Message was edited by: FireDragon on 2002-04-06 17:59 ]</font>

Posted: Sun Apr 07, 2002 12:26 pm
by Adrian Kuegel
Your output is correct.

Thank you.

Posted: Tue Apr 09, 2002 3:38 am
by FireDragon
Thank you.

prob 102

Posted: Sat Apr 27, 2002 4:45 am
by jydy
The following is my code
but I get WA's
please advise, thanks!
[c]#include<stdio.h>
#define MAX 32767
int main()
{
int b1,b2,b3;
int g1,g2,g3;
int c1,c2,c3;
int moves[6],min;
int i, switcher;

while(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==9)
{
min=MAX;

moves[0]=b1+c1+b2+g2+g3+c3;
moves[1]=b1+c1+g2+c2+b3+g3;
moves[2]=b1+g1+b2+c2+g3+c3;
moves[3]=b1+g1+g2+c2+b3+c3;
moves[4]=g1+c1+b2+c2+b3+g3;
moves[5]=g1+c1+b2+g2+b3+c3;

for(i=0;i<6;i++)
{
if(min>=moves)
{
min=moves;
switcher=i;
}
}

switch(switcher)
{
case 0:
printf("GCB %d",min);
break;
case 1:
printf("GBC %d",min);
break;
case 2:
printf("CGB %d",min);
break;
case 3:
printf("CBG %d",min);
break;
case 4:
printf("BGC %d",min);
break;
case 5:
printf("BCG %d",min);
break;
}

}

return 0;
}[/c]

Posted: Sat Apr 27, 2002 7:37 am
by Stefan Pochmann
Maybe it's because you assume a fairly small maximum. Read the problem statement again, it says "The total
number of bottles will never exceed 2^31".

What is the fastest way of input/output? (102)

Posted: Wed May 15, 2002 10:34 am
by minskcity
My program runs 5000 times faster than input/output. Is there any way to fix it????

I/O works 2 times faster after I've changed cin/cout to scanf/prinf, but it is still too slow.........

Anybody knows fast way of input??

Posted: Wed May 15, 2002 12:32 pm
by minskcity
This code (just input) takes 0.140s, while the best time for this problem is 0.010s.

(output works quite fast)

[cpp]#include <stdio.h>

int main(){

unsigned long data00,data01,data02;
unsigned long data10,data11,data12;
unsigned long data20,data21,data22;

while(scanf("%d %d %d %d %d %d %d %d %d",&data00,
&data01,&data02,&data10,&data11,&data12,&data20,
&data21,&data22) == 9){};

return 0;
}[/cpp]

iostream vs stdio?

Posted: Wed May 15, 2002 4:48 pm
by Fresh
I don't know how some people solved this problem just in 0.010s. But honestly to say, your time still fast since mine is 0.380s. From my experince, 'cin' is much faster than 'scanf' but 'cout' is slower than 'printf' so use 'cin' for input and 'printf' for output. For those who solved this problem in 0.010s, plz share your algo with us.

-novice :wink:

102 - Ecological Bin Packing

Posted: Thu May 16, 2002 9:06 am
by zerocool
The following my source code for P.102
[cpp]
#include <iostream>
using namespace std ;
void main()
{
unsigned long k1=0, data[9]={0} ;
char *c ;
while ( cin >> data[0] ) {
double min=2147483648 , sum=0 ;
sum += data[0] ;
for( k1=1 ; k1<9 ; k1++ ) {
cin >> data[k1] ;
sum += data[k1] ;
}
if ( min >= (sum-data[1]-data[5]-data[6]) )
c = "GCB " ,
min = sum-data[1]-data[5]-data[6] ;
if ( min >= (sum-data[1]-data[3]-data[8]) )
c = "GBC " ,
min = sum-data[1]-data[3]-data[8] ;
if ( min >= (sum-data[2]-data[4]-data[6]) )
c = "CGB " ,
min = sum-data[2]-data[4]-data[6] ;
if ( min >= (sum-data[2]-data[3]-data[7]) )
c = "CBG " ,
min = sum-data[2]-data[3]-data[7] ;
if ( min >= (sum-data[0]-data[4]-data[8]) )
c = "BGC " ,
min = sum-data[0]-data[4]-data[8] ;
if ( min >= (sum-data[0]-data[5]-data[7]) )
c = "BCG " ,
min = sum-data[0]-data[5]-data[7] ;
cout << c << min << endl;
}
}
[/cpp]
I cannot find any bug in it, but the judge always says "Wrong answer".
Anybody could help me what happen ?
Thanks..

Posted: Thu May 16, 2002 10:27 am
by Stefan Pochmann
My guess is that they optimized IO by reading/writing large blocks of data in raw format and parsing/printing it on their own. Since I'm too old for that kind of optimization, I'm happy with my much slower (but still way under the limit) time using simple cin/cout/scanf/printf...

Posted: Fri May 17, 2002 2:59 am
by Ivan Golubev
Stefan absolutely right -- if you want fast I/O then forget about cin/scanf. Use at least gets(), it works much faster. And parse input by your own (again, without something like strtok()). I've used read()/write() in my solution, however, I don't know is it the fastest way possible -- I haven't got 0.010... yet.