10483 - The Sum Equals the Product

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10483 - The Sum Equals the Product

Post by Dominik Michniewski »

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

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen »

8)

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

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

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post by SnapDragon »

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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 :wink:
If so, tell me and I'll remove this post.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

You have right little joey :))
I use incorrect boundary values for this problem :))

DM

PS. You can remove your post now :)))
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

still wrong answer

Post by erfan »

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan »

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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...

Post Reply

Return to “Volume 104 (10400-10499)”