11485 - Extreme Discrete Summation

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

Moderator: Board moderators

Post Reply
User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11485 - Extreme Discrete Summation

Post by andmej » Thu Sep 18, 2008 9:03 pm

This problem looks so scary! I can only think of brute-force. Please give me a little hint.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Re: 11485 - Extreme Discrete Summation

Post by sunny » Thu Sep 18, 2008 11:22 pm

You only need to deal with the floating point part of all numbers.
Once you realize it , just a simple knapsack like DP is needed.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11485 - Extreme Discrete Summation

Post by mmonish » Sun Sep 21, 2008 2:58 pm

I tried to solve this prob but getting WA..
Anyone check the following i/o please..
Input:

Code: Select all

100 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9 2.9
10 2.6 3.8 1.1 1.2 .3 .5 .6 .4 .9 .9
1 1.1
2 .1 .2
3 .1 .1 .1
4 .2 .3 .3 .2
6 .1 .1 .1 .2 .2 .3
5 .9 .9 .9 .9 1.0
3 1.0 1.0 1.0
12 5.5 .6 .6 .7 .8 .9 .0 .0 .1 .2 .2 .2
11 .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .1
0
My output:

Code: Select all

6107328003373305592
379000000
0
247
0
107264
1642388
2109376
0
1182454139
620666396

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11485 - Extreme Discrete Summation

Post by Robert Gerbicz » Sun Sep 21, 2008 3:17 pm

The first answer is wrong, my AC program gives:

Code: Select all

70000000000000000
If you want to try more testcases you can use Mark Greve's great site: http://uvatoolkit.com/problemssolve.php

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11485 - Extreme Discrete Summation

Post by mmonish » Sun Sep 21, 2008 4:13 pm

>>Robert Gerbicz
thx for ur help.now my program gives the correct output.i checked lots of cases in uva toolkit but couldn't find the coz of getting WA..
here is my code:

Code: Select all

Remove after AC..
Anyone please help me in finding my error..
Last edited by mmonish on Sun Sep 21, 2008 8:16 pm, edited 1 time in total.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Re: 11485 - Extreme Discrete Summation

Post by sunny » Sun Sep 21, 2008 6:52 pm

In your code change
x = (long long)(p*10);

to:
x=(long long)(p*10+.5);

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11485 - Extreme Discrete Summation

Post by mmonish » Sun Sep 21, 2008 8:17 pm

thanks sunny..

Post Reply

Return to “Volume 114 (11400-11499)”