10268 - 498-bis

[Jehad Uddin]

Your input processing may be wrong.

[sazzadcsedu]

At first look this problem seems very easy,But it is very tough to get Acc with the formula given in problem statement (At least for lots of people, i submitted a number of time using data type int/long long/double but couldn't get Acc ).So the best way is to use Horner's rule (I got Acc at first try) . Here is the Horner's rule-

Code: Select all

a_nx^n+a_(n-1)x^(n-1)+...+a_0=((a_nx+a_(n-1))x+...)x+a_0. 

I think the stupid(not always ) pow() function is responsible for this.

[plamplam]

Ok this problem is really very annoying....a couple of tips if you are struggling to get Accepted.

This is very important...whatever you do don't use doubles or power functions. I even tried creating my own power functions which always returns integer value(I got accepted with this in other problems too) because I thought the built-in pow function caused precision error. It seems Horner's rule is the only way to solve this thing.....
btw int data type is fine...no need to use long long and no intermediate steps causes overflow too.

[@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