10483 - The Sum Equals the Product

Dominik Michniewski · Post by **Dominik Michniewski** » Mon Apr 14, 2003 3:26 pm

This problem has 354 such sums / products in range 0.00 ... 256.00 or I'm wrong ? Maybe I miss something ?

DM

Ghost77 dimen · Post by **Ghost77 dimen** » Mon Apr 14, 2003 4:28 pm

Yes , there are 354 sets possibilities within the range from 0.01 to 256.00 .

windows2k · Post by **windows2k** » Mon Apr 14, 2003 6:07 pm

I also gets 354 sets,but I get WA.
any trap in the problem?

SnapDragon · Post by **SnapDragon** » Mon Apr 14, 2003 9:19 pm

Make sure you're sorting them correctly. 35.91, for instance, has 3, and they should be in the order "0.21 + ..." "0.50 + ..." "0.76 + ...".

windows2k · Post by **windows2k** » Tue Apr 15, 2003 4:22 am

Yes,my program generate the same order like above,
I don't know why I get WA@@

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Apr 15, 2003 7:53 am

I got the same problem like windows2k ....
I think, that I sort it correctly, but got WA, I don't know why

DM

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Apr 15, 2003 8:30 am

I got Accepted. I have one incorrect line in my output

)

But I have a question to all. I write brute-force solution, which computes solution for this problem and this program runs for 12 seconds. Is there any fast math solution for this ? Solution, which pass time limit (10 sec) in this site ? I don't have post this code here ... Maybe I miss some pruning condition ?
I use integers instead of doubles, and use only two variables to compute results (i.e. "a" and "b"). Could anyone tell me, if such solution exist ?

Best regards
DM

little joey · Post by **little joey** » Tue Apr 15, 2003 10:52 am

Dominic: I do bruteforcing within the code and finish under 0.05 sec, most of it spent on my lousy sorting algo (O(n^2)).
I think you yourself give the answer: you only have to iterate a and b; c can be calculated from them (a+b+c=a*b*c so c=(a+b)/(a*b-1)). I guess it's all about boundary conditions for a and b. If you set a<=b<=c, then a is bounded by a*a*a<256.00 and b is bounded by a*b*b<256.00. Should be enough to finish in a split second. And: once you know the upper bound for a from your previous brute force, you can even speed up more...

I hope I don't give away too much

If so, tell me and I'll remove this post.

Dominik Michniewski · Tue Apr 15, 2003 11:52 am

You have right little joey

)
I use incorrect boundary values for this problem

)

DM

PS. You can remove your post now

))

windows2k · Post by **windows2k** » Tue Apr 15, 2003 4:56 pm

sorry,I still get Wrong Answer.
But I get the same answer by Adrian Kel from 0.00 to 256.00
Still something i don't noticed?

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Apr 16, 2003 7:53 am

Send me your program and I try to help you ...

DM

erfan · Post by **erfan** » Wed Apr 16, 2003 12:21 pm

I found 354 with 0 = 0 + 0 + 0 = 0 * 0 * 0;
But still wrong answer.Is there anything else?
Or above is invalid?
All types of sort in my code i think correct.But what happen i don't know.Can anyone help me?[/b]

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Apr 16, 2003 1:00 pm

0 = 0 + 0 + 0 = 0 * 0 * 0 is invalid
There are 354 lines without this line.
Maybe you have another mistake in your code

DM

erfan · Post by **erfan** » Thu Apr 17, 2003 2:19 pm

Ohho

Dominik Michniewski pls help me by following result:
1.First output.
2.Last output.
3.How many multiple solution for one sum:

My first output is 5.25=.............=.........
Last one is 254.52=............=............(it is for multiple )

is little joey solve it in a and b as double or long What?

little joey · Post by **little joey** » Thu Apr 17, 2003 2:35 pm

I use pascal longint (32 bit signed) to store a, b and c in cents, so the actual equation is: c:=(10000*(a+b)) div (a*b-10000). The first output is (no. 1) 5.25 = x.xx + x.xx + x.xx = x.xx * x.xx * x.xx, and the last two (no. 353 and no. 354) are 254.52 = x.xx + x.xx + xxx.xx = x.xx * x.xx * xxx.xx and 254.52 = x.xx + x.xx + xxx.xx = x.xx * x.xx * xxx.xx.
Hope it helps...