10719  Quotient Polynomial
Moderator: Board moderators

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
10719  Quotient Polynomial
I cant uderstand what is wrong.
Help, please
Help, please
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.
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
My algorithm:
///// 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?
.....
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?
how about "q(x) = a*x"?
Hi.
How about this input?
for example
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 )
How about this input?
for example
Code: Select all
3
1
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..

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
output???
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
3
1 7 15 8
3
1 7 15 9
3
1
3
0 0 0 0 5
My AC solution outputs.
Output
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

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

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
I got AC.
My mistake was very silly. I forgot that k may be negative
But now I got AC, and I very happy.
Thanks to everybody who tried to help me!
But now I got AC, and I very happy.
Thanks to everybody who tried to help me!
10719 Quotient Polynomial getting TLE
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[ni]=p[ni+1]+k*q[ni+1];
}
r=p[0]+k*q[0];
printf("q(x):");
for(i=n1;i>=0;i)
{
printf(" %ld",q);
}
printf("\nr = %ld\n\n",r);
}
return 0;
}
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[ni]=p[ni+1]+k*q[ni+1];
}
r=p[0]+k*q[0];
printf("q(x):");
for(i=n1;i>=0;i)
{
printf(" %ld",q);
}
printf("\nr = %ld\n\n",r);
}
return 0;
}
Re: 10719 Quotient Polynomial getting TLE
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().
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);
}
}