102 - Ecological Bin Packing

[minskcity]

You can use asm in C/C++ like this:

[cpp]int i,j;

asm{
mov eax,i
add eax,ebx
mov i,eax
}[/cpp]

[zerocool]

Try this, it may help:

[cpp]
#include <stdio.h>
....
....
printf("%s%1.0f\n",c,min);
[/cpp]

-novice

Thanks. I corrected the ouput format then I get "Accepted"
Thank a lots.

[Ivan Golubev]

Is this mean that the Online Judge support ASM beside C/C++, Jave and Pascal? If yes, how to submit the solution or any trick to do this?

There cannot be any ASM in JAVA solution, obviously. Don't know about GNU Pascal. In GNU C/C++ it looks like:

Code: Select all

 __asm__ __volatile__ (
	"pushl	%eax\n\t"
	"pushl	%edx\n\t"
	"popl	%edx\n\t"
	"popl	%eax\n\t"
 );

However, if you aren't programming in ASM earlier it doesn't matter. Simply rewriting your code from C to ASM most probably gives you worse results. Modern processors are very complex and you're need to know what to use and what to avoid. C compiler knows basical things so it produces not-so-bad code. But if you're really know ASM you'll got some speed-up when rewrote your code.

Another thing to discuss -- is this needed you or not. If you have poor algorithm then nobody will help you, even ASM.

Learning always need teachers but what will be happen if all teachers take their knowledge as 'trade secret'?

The teachers and competitors are different things! So I can understand why Ivor doesn't want to share his "know-how".

Nobody can teach you how to think and nobody can give you experience. You must do it by your own, teachers rests here.

[Caesum]

minsk - the only thing about the asm here is that you must use gas format which is used by gcc and familiar to linux asm programmers rather than the (imho) easier to use intel format familiar to dos and windows programmers, as in ivans post.

[Ivor]

The teachers and competitors are different things! So I can understand why Ivor doesn't want to share his "know-how".

Nobody can teach you how to think and nobody can give you experience. You must do it by your own, teachers rests here.

Ivan's right -- teachers and competitors are two very different things. But it's not the actual point. I could give out all that I know, all that I have learned with almost a year at acm, but what will it give you? Yes, a bunch of fast reliable code, a lots of tips. But you won't know what, when and where to use -- that's called experience. The only way to know the behaviour of a program is to modify it a bit and see the result. Then modify again... and again... and again! It's quite a painful process.

And to Stefan: you don't have to be a genius. All you need is imagination, determination and a lot of persistency. That's all. Knowledge and experience will come as the time passes.

Ivor

[Stefan Pochmann]

And to Stefan: you don't have to be a genius. All you need is imagination, determination and a lot of persistency. That's all. Knowledge and experience will come as the time passes.

Question: do you have a book about algorithms? If yes, throw it away immediately since it would be better to invent everything yourself. Plus, you could learn more details or general views on something like dynamic programming, for example. And don't forget that you could learn commonly used notation, which you don't need since you don't discuss things with others anyway.

(I guess I don't have to mention you shouldn't take this personal, but just to be safe I do).

I, on the other hand, sometimes prefer to be shown something and then I gain the experience by actually using it, applying it to problems and to modify it. Note that I said "sometimes". Only in very special cases would I give up and ask for the answer for a problem of the OnlineJudge, for example. Usually I do try things on my own first.

[Ivor]

Sorry to disappoint you, Stefan, but I really do not have any good books on algorithms. I'm looking myself for one. But when I need a some sort of algorithm I search the net for any clues.

About taking personally. I could, but I won't. I got your idea, but what I wanted to say, is that I can't give you any general algorithms, only very few ones. The information package I have is basically optimization. And it's kinda specific. As you said, speedup tricks on general algorithms are usually not the thing to invent. But then... any algorithm is given rather generally -- the almost only thing taken into account is time complexity.

So, it's still up to you to optimize it. A simple tip: instead of cycling through the array using indexing variable, use a pointer to the array. Rather easy and it was just an illustarive example.

I, too, don't like to be shown the code. And maybe that's why I don't like to do show it myself. On the other hand, it's the idea you pay in modern world.

But sometimes I use other people's code -- in order to learn. It's a rather painful process to me, I don't like it and it takes a good amount of time. I know I could use a bit of practice, but you know the thing with lazyness and unpleasant things.

But if you have some specific questions I'll see if I can help. As far as I remeber you already know my mail.

Ivor

[Stefan Pochmann]

Yeah, I don't use array index access but pointers. And some other stuff. Just one question: I thought about copying 4 chars at once by using int pointers into char data. Since I'd have to do some alignment stuff then and I'm lazy, I haven't done it yet. Do you use this? And allow me one more question: how big is your program?

[Ivor]

The last version used some other clever tricks, but mainly your idea is fine. A bit more and you could get below 0.100.

I don't know what you meant with 'how big', but if you thought memory usage then it's around 1700-1800 Kb.

[Stefan Pochmann]

Actually I meant the *sourcecode*, i.e. how many bytes, how many lines. Just to get a slight cue of how much work lies before me to reach your speed area.

[Ivor]

Around 200 lines and 4000 bytes.

[mindae]

/* @JUDGE_ID: 19591HZ 102 C */

#include <stdio.h>

unsigned long minimum;
int Solve[3]={0};
unsigned long Data[9]={0};

int main()
{
int i,j,k,l;
unsigned long temp=0;

while(1){

for(i=0;i<=8;i++)
scanf("%ld",&Data);

for(i=0;i<=8;i++)
minimum+=Data;

for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
{
if(i!=j) {
for(k=0;k<=2;k++)
{
if(k!=i && k!=j) {

for(l=0;l<=8;l++)
if(l!=i && l!=j+3 && l!=k+6)
temp+=Data[l];

if(minimum >temp)
{
minimum=temp;
Solve[0]=i;
Solve[1]=j;
Solve[2]=k;
}

temp=0;
}
}
}
}

for(i=0;i<=2;i++)
{
if(Solve==0) printf("%c",'B');
if(Solve==1) printf("%c",'G');
if(Solve==2) printf("%c",'C');
}

printf(" %ld\n",minimum);
}
return 0;
}
Dear mindae:

Your program output is greater (4210688 bytes) than the maximum
allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.


i am a boy.
so, i can't english.
i am a korean.

output data is correct.
but recive error message . (unLimited output) .
and ..
input data {1,2,3,4,5,6,7,8,9}
output data {BCG 30}
BCG 30 = BGC 30

Help Me

[10153EN]

From your program, you use a while loop with condition true to do your calculation. However, there's no stopping or breaking condition, isn't it?

Hope can help~

[mindae]

new code..

BUT..
Dear mindae:

Your program has not solved the problem. It ran during 0.200 seconds.

-_______-;
How do pass to this problem?


/* @JUDGE_ID: 19591HZ 102 C */

#include <stdio.h>

unsigned long minimum;
int Solve[3]={0};
unsigned long Data[9]={0};

int main()
{
int i,j,k,l;
unsigned long temp=0;

while(scanf("%d %d %d %d %d %d %d %d %d",&Data[0],&Data[1],
&Data[2],&Data[3],&Data[4],&Data[5],&Data[6],&Data[7],&Data[8])!=EOF){

for(i=0;i<=8;i++)
minimum+=Data;

for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
{
if(i!=j) {
for(k=0;k<=2;k++)
{
if(k!=i && k!=j) {

for(l=0;l<=8;l++)
if(l!=i && l!=j+3 && l!=k+6)
temp+=Data[l];

if(minimum >temp)
{
minimum=temp;
Solve[0]=i;
Solve[1]=j;
Solve[2]=k;
}

temp=0;
}
}
}
}

for(i=0;i<=2;i++)
{
if(Solve==0) printf("%c",'B');
if(Solve==1) printf("%c",'G');
if(Solve==2) printf("%c",'C');
}

printf(" %ld\n",minimum);
}
return 0;
}




T-t

int solve[6]={0};

solve[0]=Data[0]+Data[1]+Data[3]+...
this method?

[10153EN]

I have not deeply taken a look at your code, but just come to a question for your output.

Code: Select all

printf(" %ld\n",minimum); 

The above code treats minimum as a long, i.e. int in C. when the value is larger than 2^31-1.....

Hope can help~