10302 - Summation of Polynomials

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

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10302 - Summation of Polynomials

Post by mido » Thu Jun 27, 2002 6:08 pm

I get WA with this code...any tips :
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>

int
num,
i;

float sum;

void main()
{
while (!cin.eof() && cin>>num)
{
sum=0;
for (i=0;i<=num;i++)
sum+=pow(i,3);
printf("%.0lf\n",sum);
}
}
[/cpp]

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Thu Jun 27, 2002 6:29 pm

Clearly, there should be value overflow~

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Thu Jun 27, 2002 7:03 pm

Well a friend just mentioned that any number type can only be accurate upto some length after which there will be some zeroes inputted automatically. Oh well.

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Hint

Post by Joe Smith » Fri Jun 28, 2002 10:18 pm

mido wrote:Well a friend just mentioned that any number type can only be accurate upto some length after which there will be some zeroes inputted automatically. Oh well.
gcc (which is what UVA uses) has a "long long" data type which supports integers up to 2^64. So does Java's "long".

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Location: Dhaka, Bangladesh
Contact:

Formula

Post by popel » Sun Jul 21, 2002 12:29 pm

1^3 + 2^3 + 3^3 + ... ... ... +n^3

Sn=(n*(n+1)/2)^2

:wink:

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

Formula using the question hints

Post by scythe » Mon Oct 07, 2002 9:22 pm

I worked on the helper formulas given in the task and i came up with the following formula:

Sn = ((N-1)*N*(N+1)*(N+2) + 2*N*(N+1)) / 4
which is actually an uglier form of your formula :oops:

I got AC using big numbers.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Re: Formula using the question hints

Post by supermin » Tue Dec 03, 2002 9:04 pm

I think this question can just use the long double.=>(%Lf)

it can solve it very quickly. :P

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Dec 03, 2002 10:15 pm

long long works, and also gets you AC with good time.. =)

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10302 again

Post by mido » Wed Feb 05, 2003 3:09 pm

Anything wrong with this:

[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>

long long
num,
i,j;

long long sum;

void main()
{
while (!cin.eof() && cin>>num && !cin.fail())
{
sum=0;
for (i=0;i<=num;i++)
{
long temp=1;
for (j=0;j<3;j++)
temp*=i;
sum+=temp;
}
cout<<sum<<endl;
}
}


[/cpp]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Feb 09, 2003 11:38 am

Your program seems to run ok.

But you might consider using a formula for the sum of Nth cube instead of using the iteration:

for (i=0;i<=num;i++)
{
long temp=1;
for (j=0;j<3;j++)
temp*=i;
sum+=temp;
}

the formula is :

(N*(N+1)/2)^2

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

10302 why WA??

Post by Chow Wai Chung » Sat May 31, 2003 4:40 am

This problem seem very easy, and i use (n*(n+1)/2)^2 to calculate the answer, but i get a WA.... :x

Would anyone tell me what is my mistake??

[c]
#include <stdio.h>
#include <math.h>

int main()
{
long long result,n;
while(scanf("%lld",&n)!=EOF)
{
result=(long long)pow(n*(n+1)/2,2);
printf("%lld\n",result);
}
return 0;
}
[/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Sat May 31, 2003 5:59 am

Your formula looks great and you might want to try x = 50,000 and check your result using calculator. Most likely it is an overflow or precision problem.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

Post by IIUC GOLD » Sat May 31, 2003 5:22 pm

Use the following

result = n * n * (n + 1) * (n + 1) /4;

instead of

result=(long long)pow(n*(n+1)/2,2);

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Mon Jun 02, 2003 1:45 am

Thank you to turuthok and IIUC GOLD 8)

I solved this problem by using n * n * (n + 1) * (n + 1) /4, may be i lost something when cast the pow() to long long before.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Sat Jul 05, 2003 3:34 pm

Got AC long time ago...who would've thought you needed for the temp variable....:)

Post Reply

Return to “Volume 103 (10300-10399)”