10719 - Quotient Polynomial

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

Moderator: Board moderators

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Jul 09, 2005 2:42 pm

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. :oops:

Regards
Sanny

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul » Sat Jul 09, 2005 8:07 pm

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
New poster
Posts: 4
Joined: Wed Feb 25, 2004 4:42 pm
Location: Bangladesh
Contact:

Post by soumit » Sat Jul 09, 2005 8:22 pm

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

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

10719 - Quotient Polynomial

Post by murkho » Sun Jul 24, 2005 10:07 pm

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Tue Jul 26, 2005 4:08 am

What problem it is?

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

Thankx Antonio

Post by murkho » Tue Jul 26, 2005 8:29 pm

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: why wrong answer !! some sample input &output (pls)

Post by Martin Macko » Fri Jul 29, 2005 6:26 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: why wrong answer !! some sample input &output (pls)

Post by Jan » Tue Aug 02, 2005 5:30 am

murkho wrote:

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. :o
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.
Ami ekhono shopno dekhi...
HomePage

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Fri Aug 05, 2005 4:25 pm

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
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

read til the end of line

Post by zero_cool » Tue Sep 13, 2005 6:04 am

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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Tue Sep 13, 2005 8:25 am

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
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

Post by zero_cool » Tue Sep 13, 2005 7:59 pm

i need input for problem 10719

The input is like this

_____________________________________________________________
3
1

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Sep 13, 2005 11:46 pm

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;
  }
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Sep 14, 2005 6:42 am

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Sep 14, 2005 8:46 am

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.

Post Reply

Return to “Volume 107 (10700-10799)”