## 10719 - Quotient Polynomial

Moderator: Board moderators

Karthekeyan wrote:I found the reason!!
isdigit was the problem....i removed it and i got PE now!! So, how to remove the PE??

You write trailing spaces. Check this:

Karthekeyan wrote:
code wrote:......cout<<q[0]<<" ";
......for(int i=1;i<n;i++)
......{
.........q[i]=q[i-1]*k+a[i];
.........cout<<q[i]<<" ";
......}

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

i don't know what to say today by accident i saw my post on that problem, and i tried to solve it

and its still wrong answer i changed the cin.eof() to cin>> and it worked in all the cases and still WA
Martin said:
Your solution doesn't work even for the example from the problem statement. It returns:Code:
q(x):
r = 0

q(x):
r = 0

i think you copied and pasted the test case in the problem statement, when you do that the clipboard don't recognize it as a 45(-) but recognizes it as -106(-)

hope you kindly help me get AC
Moussa
New poster

Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

Rocky wrote:i not debug your code but if you need some test data then i can post you..

GOOD LUCK

that would be very good
Moussa
New poster

Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

I got it.
Use "while(cin >> k)" instead of "while(!cin.eof())", and I got AC.
Thanks.
Last edited by legnaleurc on Sun May 06, 2007 10:50 am, edited 1 time in total.
legnaleurc
New poster

Posts: 4
Joined: Mon Apr 23, 2007 6:05 am

Check mamun's post.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### 10719- Quotient Polynomial

hi,
i m getting WA and can't figure out my error . can anyone give me some test case.
-tulip
by tulip
rongtuli
New poster

Posts: 5
Joined: Fri Aug 17, 2007 4:38 am

i got ac now i used pow function for interger variable
nayimsust
New poster

Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

### Re: 10719 - Quotient Polynomial

This is the code:

Code: Select all
`#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX_DEGREE 20000#define MAX_LEN 200000char input[MAX_LEN];int main(){   int i;   long a[MAX_DEGREE];   int k;   int degree;   long r;   int j;   long q[MAX_DEGREE];   long t;   char* p;   int n;   char word[100];   int first = 1;//   freopen("in5.txt", "r", stdin);   while (scanf("%d", &k) != EOF)   {      scanf(" %[^\n]", input);            i = 0;      p = strtok(input, " ");      while (p != NULL)      {         a[i] = atoi(p);                  p = strtok(NULL, " ");         i++;      }            degree = i;      if (first)      {         first = 0;      }      else      {         printf("\n");      }/*      if (degree < 2)      {         printf("q(x): 0\nr = %ld\n", a[0]);         continue;               }*/      r = 0;      j = 0;      for (i = 0;i < degree-1;i++)      {         t = a[i]-r;         q[j] = t;         r = -t*k;         j++;      }      r = a[i]-r;      printf("q(x): ");      for (i = 0;i < degree-1;i++)      {         printf("%ld ", q[i]);      }      printf("\n");      printf("r = %ld\n", r);   }   return 0;}`

This is the test input:
3
1 -7 15 -8
3
1 -7 15 -9
1
1 0 0 -3
1
1 -1
1
5 -5
3
1 -3
3
3 -9
4
1 -3
4
1 -1
1
5
1
1 -2 1
1
1 -3 3 -1
3
1 -7 12
1
1 -4 6 -4 1
4
1 0 -16
1
1 -4 5 -2
2
1 -4 5 -2
1
1 0 0 0 -1 1
1
1 0 0 0 -1 0
3
-7 2 2
3
1
3
1 -7 15 -8
3
1 -7 15 -9
3
1
3
0 0 0 0 5
-2
1 1 -2

This is the test output:
[quoteq(x): 1 -4 3
r = 1

q(x): 1 -4 3
r = 0

q(x): 1 1 1
r = -2

q(x): 1
r = 0

q(x): 5
r = 0

q(x): 1
r = 0

q(x): 3
r = 0

q(x): 1
r = 1

q(x): 1
r = 3

q(x):
r = 5

q(x): 1 -1
r = 0

q(x): 1 -2 1
r = 0

q(x): 1 -4
r = 0

q(x): 1 -3 3 -1
r = 0

q(x): 1 4
r = 0

q(x): 1 -3 2
r = 0

q(x): 1 -2 1
r = 0

q(x): 1 1 1 1 0
r = 1

q(x): 1 1 1 1 0
r = 0

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

q(x):
r = 1

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

q(x): 1 -1
r = 0
][/quote]

cases considered:
1) x-k
2) q (x-k)
3) 1/0
4) x-a, a < k
5) (x-k)^2
6) (x-k)^3
7) (x-k)^4
(x-k)(x-a)
9) x^2-k^2
10) x^2-a, a<k
11) x^5-x+1
12) (x-k)^2 ( x-a)
13) (x-k)(x-a)^2
14) k can be negative number
15) also included the test cases in previous posts.
16) k = 0

Moreover, made everything long so that no overflow. Size of the holding array is 2x ~ 10x. Kept the array in the heap. Included blank lines between cases.

Still the judge seems to be unfairly giving WA.

Got any ideas?
amishera
New poster

Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10719 - Quotient Polynomial

It seems like there are only 2 ways left to solve this:

1. beseech
2. bribe

if it were a girl instead then there would be a 3rd approach.
amishera
New poster

Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10719 - Quotient Polynomial

Option 3) You can verify whether the test cases you have posted are correct using http://uvatoolkit.com/problemssolve.php

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### Re: 10719 - Quotient Polynomial

That is a pretty cool site.

But it still didn't work. The both outputs match (tested using diff -b). Still WA. I don't understand what else can remain. k can be >0, <0 and ==0. the polynomial can be degree 0, 1, 2, 3, 4. Upto degree 4 polynomial should be representative. That should be all. But what a crap.
amishera
New poster

Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10719 - Quotient Polynomial

@amishera,
You used,
printf("q(x): ");
for (i = 0;i < degree-1;i++)
{
printf("%ld ", q[i]);
}

it should have been,
printf("q(x):");
for (i = 0;i < degree-1;i++)
{
printf(" %ld", q[i]);
}

Thanks
mliu_buet
New poster

Posts: 2
Joined: Sat May 14, 2011 7:01 pm

### Re: 10719 - Quotient Polynomial

I think you are tired of the input format:(strtok,sscanf,...bla bla)
lets check this out,

//declarations
while(scanf("%d",&k)!=EOF)
{
for(i=0;;i++)
{
scanf("%d",&poly[i]);
if(getchar()=='\n') break;
}

// rest of the code

}

mliu_buet
New poster

Posts: 2
Joined: Sat May 14, 2011 7:01 pm

Previous