10719 - Quotient Polynomial

[Sanny]

I use it in this way:

Code: Select all

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

int main()
{
	char str[100],*p;
	long int temp;
	gets(str);
	while(1)
	{
		sscanf(str,"%ld",&temp);
		p=strtok(str," ");
		p=strtok(NULL,"");
		if(!p)
			break;
		else
			strcpy(str,p);
	}
	return 0;
}

As you can see, it involves lots of string copy. So it is very inefficient.

Regards
Sanny

[Zuberul]

no string copy is required.
after p=strtok(params)
you can use temp=atol(p);
i think this is the easiest way to parse a line for
unknown number of inputs.

[soumit]

thanx guyz ... i got ACC with strtok and I was getting TLE may coz of the indexing of input

[murkho]

can anybody tell why wrong answer
or
pls give me for some input && ouput

Code: Select all

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


int main()
{

	long k,count,i,pre,sum,j;
	long p[15000],q[15000];
	char str[100000] , *pointer,ch;
	//freopen("c:\\10719.in","r",stdin);
	while(scanf("%ld",&k)!= EOF)
	{
		//scanf("%c",&ch);
		gets(str);
		gets(str);
		count = -1;

		pointer = strtok(str," -");

		while(pointer)
		{
			p[++count] = atol(pointer);
			pointer = strtok(NULL, " ");
		
		
		}

		pre = 0;
		printf("q(x):");
		for(i = 0;i<count;i++)
		{
			pre = p[i] + pre*k;
			printf(" %ld",pre);		
		
		
		}

		sum = 0;
		for(i = 0,j = count;i<=count;i++,j--)
			sum += p[i] * pow(k,j);
		printf("\nr = %ld\n",sum);

	
	printf("\n");
	
	
	}






	return 0;
}

[Antonio Ocampo]

What problem it is?

[murkho]

Sorry, as i did not gave the number. In fact the number is 10719 (Quotient Polynomial). So i am waiting for a reply.

[Martin Macko]

Hi,

your program is not working for

Code: Select all

3
-7 2 2

The answer should be

Code: Select all

q(x): -7 -19
r = -55

good luck

[Jan]

Code: Select all

    sum = 0;
    for(i = 0,j = count;i<=count;i++,j--)
        sum += p[i] * pow(k,j);
    printf("\nr = %ld\n",sum);

The problem says that n can be 10000, and you are calculating k^10000.
Consider that k=3, and there are 10000 elements then your program would try to calculate 3^10000. You should avoid pow() function and try to find another way to calculate the sum...

suppose you have n numbers in an array p[] numbering from 0 to n-1, where the 0-th element is a(n), 1st element is a(n-1) and so on.

Then you can use ...

Code: Select all

    sum = 0;
    for(i=0;i<n;i++)
        sum = sum*k+p[i] ;    

Hope it helps.

[Raiyan Kamal]

to Zuberul vai,
i can show you an way easier than the easiest way you have shown. See the piece of code bellow.

to Soumit vai ( and also Sanny vai) ,
why on earth do we need to use strtok and other sophisticated things when we can do it using getchar() !!!??

Code: Select all

while(c=getchar())
{
     if((isdigit(c)  ||  (c=='-') )
     {
          //you know what to do now
     }
}

[zero_cool]

does anyone know how to read numeric data til the end of line?

[sumankar]

K&R has something called getword() function. Implementing a getnum()
on similar lines is trivial.

You've not mentioned the type of numeric data you want to proceed, the kind
of complexity you wish to delve in etc. And these can affect your input scanning routine quite a bit. One example might've helped.

[zero_cool]

i need input for problem 10719

The input is like this

_____________________________________________________________
3
1

[misof]

For this problem I did my own input parsing. A simplified version follows:

Code: Select all

char buf[120000];

fgets(buf,119000,stdin);
int bl=strlen(buf);
int n=0, current_number=0;
for(int i=0;i<=bl;i++) {
  if (isdigit(buf[i]) || buf[i]=='-') {
    // we have a digit, update the current number
  } else {
    if (current_number != 0) result[n++] = current_number;
    current_number = 0;
  }
}

[shamim]

The function strtok() is there to handle such task.

[Krzysztof Duleba]

strtok is slower than parsing strings on your own, esp. when you know what to expect. Also, from the manual:

Code: Select all

BUGS
       Never use these functions. If you do, note that:

              These functions modify their first argument.

              These functions cannot be used on constant strings.

              The identity of the delimiting character is lost.

              The strtok() function uses a static  buffer  while  parsing,  so
              it's not thread safe. Use strtok_r() if this matters to you.