10268 - 498-bis

Nick · Post by **Nick** » Wed Sep 03, 2003 8:03 pm

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 · Post by **sidky** » Thu Sep 11, 2003 8:14 am

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 · Post by **Alexander Denisjuk** » Thu Sep 11, 2003 10:15 am

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 · Post by **Riyad** » Thu Sep 25, 2003 4:54 pm

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 · Post by **Riyad** » Sat Sep 27, 2003 4:12 am

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 · Post by **cytmike** » Mon Jul 12, 2004 12:03 pm

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

i got TLE in such way.

can anybody help me?

IIUC GOLD · Post by **IIUC GOLD** » Mon Jul 12, 2004 3:34 pm

Use Horner's Rule to solve the Problem.

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

cytmike · Post by **cytmike** » Mon Jul 12, 2004 3:37 pm

what's that?

cytmike · Post by **cytmike** » Mon Jul 12, 2004 5:00 pm

Solved finally.
Thank you, IIUC!

Wei · Post by **Wei** » Sun Oct 31, 2004 3:22 pm

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 · Post by **Sedefcho** » Tue Jan 25, 2005 12:43 pm

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 · Post by **Sedefcho** » Tue Jan 25, 2005 2:11 pm

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 · Post by **Sedefcho** » Tue Jan 25, 2005 2:12 pm

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 · Post by **tacolin** » Sat Feb 19, 2005 10:49 am

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 · Post by **Sedefcho** » Sat Feb 19, 2005 5:30 pm

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.

OJ Board

10268 - 498-bis

same here

10268, unknown error????? plizzzzzzzz help

hey plizzzzzzzzzzzzz help

10268~~with WA