11485 - Extreme Discrete Summation

Moderator: Board moderators

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

11485 - Extreme Discrete Summation

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

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

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

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

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

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

thanks sunny..