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

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

10719 - Quotient Polynomial

Post by Victor Barinov » Sun Oct 03, 2004 10:08 am

I cant uderstand what is wrong.
Help, please :cry:

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Oct 03, 2004 10:56 am

Hello Victor Barinov.
I think if your algo is right you won't get WA, because I think ther aren't spesial cases.Tell me your algorithm and may be I can help you.

Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

My algorithm:

Post by Victor Barinov » Sun Oct 03, 2004 11:25 am

///// c[] - array of coefficients p(x)

.....

lc = 0;
for (i = 1; i < n; ++i) {
cc = k*lc + c; /// calculating coefficient for q(x)
printf(" %ld", cc); /// out coefficient for q(x)
lc = cc;
}

cc = k*lc + c; /// calculating reminder r
printf("\nr = %ld\n", cc); /// out reminder r

....

May be you can give me some tests?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

how about "q(x) = a*x"?

Post by wook » Sun Oct 03, 2004 12:24 pm

Hi.

How about this input?

for example

Code: Select all

3
1
or

q(x) = x
q(x) = 2 * x


I think that if your algorithm is correct,

you will get accepted :)

(Check for output format, too )
Sorry For My Poor English.. :)

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

output???

Post by Victor Barinov » Sun Oct 03, 2004 7:48 pm

Can anybody give me correct output file for this input:

3
1 -7 15 -8
3
1 -7 15 -9
3
1
3
0 0 0 0 5

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Oct 03, 2004 8:05 pm

My AC solution outputs.
Output

Code: Select all

q(x): 1 -4 3
r = 1
q(x): 1 -4 3
r = 0
q(x):
r = 1
q(x): 0 0 0 0
r = 5
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sun Oct 03, 2004 8:07 pm

there maybe some residue spaces/endlines in the end of input.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

I got AC.

Post by Victor Barinov » Sun Oct 03, 2004 8:37 pm

My mistake was very silly. I forgot that k may be negative :oops:
But now I got AC, and I very happy. :D
Thanks to everybody who tried to help me!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue May 03, 2005 7:30 am

I find something interesting, when I implemented it, I actually have
q(x) : 0

if p(x) is constant and get WA.

So much for unnecessary steps :lol:

soumit
New poster
Posts: 4
Joined: Wed Feb 25, 2004 4:42 pm
Location: Bangladesh
Contact:

10719 Quotient Polynomial getting TLE

Post by soumit » Thu Jul 07, 2005 5:50 am

How on earth can i get TLE in 10719 ... any ideas ????

heres my code

#include<stdio.h>
#include<math.h>
#include<ctype.h>
#define MAXN 10020


long p[MAXN],q[MAXN],r;
char input[MAXN*12];


void swap(long &a,long &b)
{
long temp;
temp=a;
a=b;
b=temp;
}


long read_p()
{
long i,j,n;

gets(input);

n=0;

for(i=0;input;i++)
{
sscanf(&input,"%ld",&p[n++]);

do{
i++;
}while(input=='-' || isdigit(input));

if(input==0)
break;
}

--n;
for(i=0,j=n;i<=j;i++,j--)
swap(p,p[j]);

return n;
}



int main()
{
long i,n,k;

// freopen("in10719.txt","r",stdin);

while(scanf("%ld\n",&k)==1)
{
n=read_p();

q[n]=0;

for(i=1;i<=n;i++)
{
q[n-i]=p[n-i+1]+k*q[n-i+1];
}

r=p[0]+k*q[0];

printf("q(x):");

for(i=n-1;i>=0;i--)
{
printf(" %ld",q);
}

printf("\nr = %ld\n\n",r);
}

return 0;
}

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

Re: 10719 Quotient Polynomial getting TLE

Post by Zuberul » Sat Jul 09, 2005 4:38 am

soumit wrote:
sscanf(&input,"%ld",&p[n++]);



use only input as the first param.
i havnt tested your code.
but looking at it i think there may be some problem in input
parsing.
try to use strtok().

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

Post by Sanny » Sat Jul 09, 2005 4:56 am

I'm not sure if this TLE is for input parsing. But I'm pretty much sure that if you use strtok(), you'll get TLE. I took input character by character in this problem.

Regards
Sanny

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Jul 09, 2005 9:27 am

sanny wrote: But I'm pretty much sure that if you use strtok(), you'll get TLE
Not quite..
.. I used strtok() and got it AC.

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

Post by Sanny » Sat Jul 09, 2005 10:44 am

Then maybe you use strtok() in a more efficient way than me. During contest time, I got TLE on this problem for using strtok().

Regards
Sanny

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Jul 09, 2005 11:53 am

I use strtok() in the standard way, I think.

Code: Select all

#include<string.h>
#include<vector>

using namespace std;

int main() {
 char *p;
 int a;
 char str[1000];
 vector<int> V;
 gets(str);
 p = strtok(str, " ");
 sscanf(p, "%d", &a);
 V.push_back(a);
 while(1) {
  p = strtok(NULL, " ");
  if( !p ) break;
  sscanf(p, "%d", &a);
  V.push_back(a);
 }
}

Post Reply

Return to “Volume 107 (10700-10799)”