## 10268 - 498-bis

Moderator: Board moderators

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### same here

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
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
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
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.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 10268, unknown error????? plizzzzzzzz help

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### hey plizzzzzzzzzzzzz help

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
so..
do i need to use all things as BigInt?

i got TLE in such way.

can anybody help me?
Impossible is Nothing.

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Contact:
Use Horner's Rule to solve the Problem.

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

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
what's that?
Impossible is Nothing.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
Solved finally.
Thank you, IIUC!
Impossible is Nothing.

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

### 10268~~with WA

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);
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
New poster
Posts: 2
Joined: Tue Feb 10, 2004 2:24 pm
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);
}
}``````

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.