10268 - 498-bis

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

same here

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

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
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:

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.

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

10268, unknown error????? plizzzzzzzz help

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

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

hey plizzzzzzzzzzzzz help

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

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

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?
Impossible is Nothing.

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

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.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

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

what's that?
Impossible is Nothing.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

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

Solved finally.
Thank you, IIUC! :P
Impossible is Nothing.

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

10268~~with WA

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]

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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 ?

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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
New poster
Posts: 2
Joined: Tue Feb 10, 2004 2:24 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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.

Post Reply

Return to “Volume 102 (10200-10299)”