10268 - 498-bis

[@ce]

Getting WA...plzz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

int arr[100000000];
           
main()
{
      string strx,str;
      while(getline(cin, strx))
      {
            stringstream ss(strx);
            long long int x;
            ss>>x;
            getline(cin, str);
            stringstream in(str);
            int n = 0;
            while(in >> arr[n])
                n++;
            long long int poly = 0;
            for(int i = 0;i<n ; i++)
                    poly = poly + (n-i-1)*arr[i]*pow(x,n-i-2.0);
            printf("%lld\n", poly);
      }
}


[brianfry713]

pow() returns a double and could lead to precision errors.

[@ce]

Removing pow() gives TLE

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

int arr[100000000];

long long int power(long long int x, long long int n)
{
     if(n == 1)
          return x;
     else if(n == 0)
          return 1;
     else if(n&1)
            return power(x,n/2)*power(x,n/2+1);
     else
            return power(x,n/2)*power(x,n/2);
}
main()
{
      string strx,str;
      while(getline(cin, strx))
      {
            stringstream ss(strx);
            long long int x;
            ss>>x;
            getline(cin, str);
            stringstream in(str);
            int n = 0;
            while(in >> arr[n])
                n++;
            long long int poly = 0;
            for(int i = 0;i<n ; i++)
                    poly = poly + (n-i-1)*arr[i]*power(x,n-i-2);
            printf("%lld\n", poly);
      }
}


[brianfry713]

http://en.wikipedia.org/wiki/Horner%27s_method