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

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

Post by IIUC GOLD » Sun Feb 20, 2005 6:52 am

I didn't find any wrong with this problem.

You have to careful about the intermediate calcualtions. Although the problem description says that the output will fit in 32 bit integer, but the intermediate values may be larger than that. So, use Horner's rule to evaluate the derivative of polynomial . Also, careful about the input processing. I used gets() to take the input and strtok() to separate the coefficients.

Code: Select all


char buf[1000000];

int main()
{
                // declare variables
	while (gets(buf))
	{
		sscanf(buf, "%ld", &x);
		px = 0;
		ppx = 0;
		gets(buf);
		ptr = strtok(buf, " \n");
		while (ptr)
		{
			a = atol(ptr);
			ppx = ppx * x + px;
			px = px * x + a;
			ptr = strtok(NULL, " \n");
		}
		// print ppx
	}
	...
}

tacolin
New poster
Posts: 2
Joined: Tue Feb 10, 2004 2:24 pm

Post by tacolin » Sun Feb 20, 2005 3:09 pm

To IIUC GOLD:

Thx for your help!! I rewrite my code and got AC! :D

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10268

Post by CodeMaker » Mon Mar 28, 2005 5:00 pm

Hi I got WA, I used honor's rule and used long long data type....what i can do more? what will be the array limit?

Code: Select all

#include<cstdio>
#include<cstring>
long long a[3000000];
int main()
{
	long long x,sum,i,j,n;
	char temp[3000000],*ptr;

	while(scanf("%lld",&x)==1)
	{
		getchar();
		gets(temp);

		ptr=strtok(temp," ");
		i=0;
		while(ptr)
		{
			sscanf(ptr,"%lld",&a[i++]);
			ptr=strtok(NULL," ");
		}
		i--;
		n=i;
		for(j=0;j<i;j++)
		{
			a[j]*=n--;
		}
		sum=a[0];
		for(j=1;j<i;j++)
		{
			sum=sum*x+a[j];
		}
		printf("%lld\n",sum);
	}
	return 0;
}
Jalal : AIUB SPARKS

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Mar 28, 2005 6:24 pm

As a matter of fact, you don't need any arrays or whatever in this problem.

A hint: the "definition" of derivative given in the statement is not the best way to proceed. Remember the product rule of differentiation: d(uv) = du v + u dv. Using it and Horner's method you can avoid arrays.

long long was enough in my solution.

lyc
New poster
Posts: 2
Joined: Fri Jun 17, 2005 8:30 am

10268-WA

Post by lyc » Sun Jun 26, 2005 9:50 am

i always got WA. help me plz.

Code: Select all

#include<stdio.h>
#include<math.h>
int main(void)
{
    int i,j,x,l;
    static int c[2000000];
    long long sum;
    char flag;
    while(scanf("%d",&x)!=EOF)
    {
        i=0;
        while(scanf("%d%c",&c[i],&flag)!=EOF)
        {
            if(flag=='\n')break;
            i++;
        }
        sum=0;
        for(j=i;j>0;j--)
            sum+=c[i-j]*j*pow(x,j-1);
        printf("%lli\n",sum);
    }
    return 0;
}

liqu
New poster
Posts: 2
Joined: Thu Aug 25, 2005 6:50 pm

10268 (498') got WA!

Post by liqu » Mon Sep 05, 2005 10:30 am

It seems that my program works ok with all the cases i can figure out , but i consistently get WA !
Maybe some good guy can help me with it~

Code: Select all

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

using namespace std;

int main()
{
    int x;
    char a[1000000],*p;
    int num[1000],i,n,j;
    while(scanf("%d\n",&x)==1)
    {
        long total = 0;
        gets(a);
        p = strtok(a," ");
        num[0] = atoi(p);
        for(p=strtok(NULL," "),i=1; p!=0; p=strtok(NULL," "),i++)
                num[i] = atoi(p);
        
        for(j=0;j<i;j++)
                num[j] *= i-j-1;
        
                for(j=0;j<i-1;j++)
                         total += num[j] * static_cast<long>(pow((double)x,(double)i-j-2)); 
                printf("%ld\n",total);                 
      }    
        
}

Vladislav Andrushkevich
New poster
Posts: 1
Joined: Sun Nov 13, 2005 8:49 pm

10268 - WA :(

Post by Vladislav Andrushkevich » Sun Nov 13, 2005 9:00 pm

It seems that my program works ok with all the cases i can figure out , but i consistently get WA !
Can anyone help me please!

program P10268;
var A,X,C,j:integer;
S:string;
Sum:LongInt;
begin
while not EOF do
begin
ReadLn(X);
Read(S);
j:=0;
Sum:=0;
for C:=0 to Length(S) do
if S[C]=' ' then j:=j+1;
while j>0 do
begin
if POS(' ',S)>0 then
begin
VAL(COPY(S,1,POS(' ',S)-1),A,C);
DELETE(S,1,POS(' ',S));
Sum:=Sum+A*j*Round(Exp((j-1)*Ln(X)));
end;
j:=j-1;
end;
WriteLn(Sum);
end;
end.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10268 - 498'

Post by helloneo » Mon Dec 12, 2005 7:00 pm

I got RTE.. but I don't see why..~!
Somebody please tell me why.. ~

Code: Select all

CUT AFTER AC
Thanks.. :-)
Last edited by helloneo on Fri Jun 08, 2007 6:28 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Dec 17, 2005 2:19 am

Use buf size 1000001 and coef size 400000. I think these are the reasons for which you are getting RTE.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

handsomepot
New poster
Posts: 5
Joined: Sun Jul 08, 2007 12:15 pm

int & long long

Post by handsomepot » Thu Aug 16, 2007 2:34 am

I use int and got AC
But long long results in WA.
Who can explain why?

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

wrong answer

Post by Mata » Wed Mar 26, 2008 9:00 pm

hi, I try this problem, but it I get wrong answer, i use the same in the 498 and got Ac in that, what could be wrong with this

Code: Select all

#include <iostream>
#include <cmath>
int main()
{
	double cof[200000], xval=0.0, r=0.0;
	int x=0, a=0, k=0;
	char ca=' ';
	while(true)
	{
		x=0, r=0, a=0, k=0;
		scanf("%lf%c",&xval,&ca);
		while((k=scanf("%lf%c",&cof[x],&ca))>=1)
		{
			x++;
			if(ca=='\n')
				break;
		}
		while(a<x)
		{
			if(x-(a+2)>=0)
			{
				r+=cof[a]*(x-(a+1))*pow(xval,x-(a+2));
			}
			a++;
		}
		printf("%.0lf\n",r);
		if(k!=2)
			return 0;
	}
	return 0;
}
If you have some sample input please post it, thanks.
/********************************
********************************/

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 27, 2008 5:56 pm

Check the cases.

Input:

Code: Select all

1
1073741824 -1073741824 0
1
2147483647 -2147483647 0
2
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1
2
-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
-2
-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
-1
1 1 1
Output:

Code: Select all

1073741824
2147483647
-65244729
-2147483647
1155763769
-1
Your code prints an extra 0 at the end of output. May be your input taking part is not fully correct.

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

stil wa

Post by Mata » Thu Mar 27, 2008 6:28 pm

Hi, thanks for the test cases, I try them and i got the same output as you, i didn't find the extra 0 at the end of my output.

Code: Select all

1073741824
2147483647
-65244729
-2147483647
1155763769
-1
/********************************
********************************/

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 10268 - 498'

Post by deadangelx » Sat Dec 20, 2008 7:42 am

test cases

Code: Select all

100000000000000
1
answer

Code: Select all

0

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10268 - 498'

Post by Obaida » Mon Mar 16, 2009 8:18 am

I did something wrong?
Some one please figure my mistake. Why this gives me wa? :cry:

Code: Select all

#include<math.h>
long long int a[10000001];
int main()
{
	long long int sum,x,i,j,t;
	char c;
	while(scanf("%lld",&x)==1)
	{
		i=0;
		while(1)
		{
         scanf("%lld%c",&a[i++],&c);
         if(c==10)break;
      }
      sum=0;t=0;
      for(j=i-2;j>=0;j--)
      {
         sum += (j+1)*a[t++]*pow(x,j);
      }
      printf("%lld\n",sum);
   }
   return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 102 (10200-10299)”