10719 - Quotient Polynomial

[Martin Macko]

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:

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

[Moussa]

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]

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

GOOD LUCK

that would be very good

[legnaleurc]

I got it.
Use "while(cin >> k)" instead of "while(!cin.eof())", and I got AC.
Thanks.

[Jan]

Check mamun's post.

[rongtuli]

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

[nayimsust]

i got ac now i used pow function for interger variable

[amishera]

This is the code:

Code: Select all

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

#define MAX_DEGREE 20000
#define MAX_LEN 200000

char 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]

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.

[sohel]

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

[amishera]

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.

[mliu_buet]

@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]

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

}