10268 - 498'

[Nick]

I am also having trouble with this problem. Is the inputs and output really won't exceed 2^31?
I thought that maybe the intermediate results can be larger than 2^31 or maybe even much more...so I used BigInt anyway, but got runtime error!!

Can somebody post some sample input? I need to know how likely the inputs could be, thanks.

[sidky]

Maybe the problem is, you used unsigned long to store the value. Although the problem description says that the output will fit in 32 bit integer, but the intermediate values may be larger than that. Try using custom data type for calculation

[Alexander Denisjuk]

Consider, for instance, the following relation:

f(x)=(x-7)^10=x^10 - 70 x^9 + 2205 x^8 - 41160 x^7 + 504210 x^6 - 4235364 x^5 + 24706290 x^4+ 24706290 x^3 + 259416045 x^2 - 403536070 x+ 282475249

Test your problem for f'(7)=0. Then try f(x)*(x^100+1) for x=7. And so on.

[Riyad]

THE FOLLOWING CODE OF MINE GIVES UNKNOWN ERROR . I HAVE NEVER CONFRONTED SOME THING LIKE THIS . PLIZ HELP .

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int c[100000],x;
int index1;
double result;
void calculate(){
   double sum;
   register int i,j ,k;
   int e1;
   double es,ep;
      sum=0.0;
      for(i=index1-1,j=0,k=index1-2;j<index1;j++){
         e1=c[j];
         if(x==0 && k==0){
            ep=1;
         
         }
         else{
            ep=((i--)*pow(x,k--));
         }
         es=(e1*ep);
         sum+=es;
      }      
      result=sum;   
   printf("%.0lf\n",result);

}
int main(){
   char *p;
   char input[100000];
   while(gets(input)){
      x=atoi(input);
      gets(input);
      index1=0;
      p=strtok(input," ");
      while(p){
         c[index1++]=atoi(p);
         p=strtok(NULL," ");
      }
      calculate();   
   }
   return 0;
}

BUT IF I USE INTEGER DATA TYPE INSTEAD OF DOUBLE FOR THE VARIABLES SUM,RESULT ,ES,EP IT GIVES ME WRONG ANSWER .

PLIZZZZZZZZ HELP ME IN THIS , LOOKING FORWARD FOR U R HELP.
BYE
Riyad

[Riyad]

I GOT A NOTIFICATION FROM THE JUDGE SCRIPT THAT IT WAS NOT UNKNOWN ERROR , IT WAS RTE . I USED BOTH DOUBLE AND INT FOR THIS PROB BUT GOT RTE . WHAT AMI I DOING WRONG PLIZZZZZZZZZZZZZZZZZZZ DO HELP ME .

PLIZZZZZZZZZZZZZ HELP .
BYE
RIYAD

[cytmike]

so..
do i need to use all things as BigInt?

i got TLE in such way.

can anybody help me?

[IIUC GOLD]

Use Horner's Rule to solve the Problem.

No need to use BigInt. Long is enough to solve the problem.

[cytmike]

what's that?

[cytmike]

Solved finally.
Thank you, IIUC!

[Wei]

Well~I got WA on this problem~~
Could anyone help me???
[c]#include <stdio.h>
#include <stdlib.h>
int main(void)
{
double a[1000005],b,ans,all;
int i,j;
char ch;
while(scanf("%lf",&b)!=EOF)
{
i=-1;
ch=15;
while(ch!=10)
{
i++;
scanf("%lf",&a[i]);
scanf("%c",&ch);
}
ans=0;all=1;
for(j=i-1;j>=0;j--)
{
if(j!=i-1)
all=all*b;
ans=ans+all*(i-j)*a[j];
a[j]=0;
}
printf("%.0lf\n",ans);
}
return 0;
}[/c]

[Sedefcho]

To: Alexander Denisjuk

The formula you've given for (X-7)^10 is not correct.
The term in front of X^3 should be at least negative.
Can you give the correct formula or some other tests.

I am sure everything is OK ( logically ) with my program
but apparently there're some boundary cases which
cause problems.

[Sedefcho]

I think the tests of this Problem 10268 are quite strange.
I am sure my algorithm is OK, I have tried using double, long,
int, BigInt ( custom class written by me ).

And none of them works. It keeps saying wrong answer.

I need some decent tests to check my program agains them.

Can anyone help ?

[Sedefcho]

I think the tests of this Problem 10268 are quite strange.
I am sure my algorithm is OK, I have tried using double, long,
int, BigInt ( custom class written by me ).

And none of them works. It keeps saying wrong answer.

I need some decent tests to check my program agains them.

Can anyone help ?

[tacolin]

To: Alexander Denisjuk

The fomula you give for (x-7)^10 should be f(x)=(x-7)^10=x^10 - 70 x^9 + 2205 x^8 - 41160 x^7 + 504210 x^6 - 4235364 x^5 + 24706290 x^4 -98825160 x^3 + 259416045 x^2 - 403536070 x+ 282475249.

Could you plz explain what the fomula mean. I use the Horner's Rule to make my program walk efficiently, but I still got a TLE.

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>

#define MAX 1000000

using namespace std;

void main()
{
   long c[MAX/2], pos, n, len, x, i, res;
   char str[MAX], tmp[MAX];

   while (scanf("%ld", &x) == 1)
   {
      getchar();
      gets(str);
      pos = n = 0;
      len = strlen(str);
      while (pos < len)
      {
         sscanf(str+pos, "%s", tmp);
         sscanf(tmp, "%ld", &c[n++]);
         pos += strlen(tmp) + 1;
      }

      n--;
      for (i = 0, res = 0; i < n; i++)
         res = res * x + (n - i) * c[i];
      printf("%ld\n", res);
   }
}

Thx for your help.

[Sedefcho]

Tacolin,

There's something wrong with this problem, that is my
opinion. I also had TLE while using the horner's rule.

I thought the reason could be that i was writing in java, but
obviously this is not the reason.

This problem and problem 498 are pretty simple but ...
Hard to get ACC in them, I have no idea why is that.