10586 - Polynomial Remains

[little joey]

It's been a while since I left school, but they tought me that n^0=1 for any value of n.
In this problem we are required to divide by the polynomial x^k+1, which evaluates to 1+1=2 if k=0. (At least that's what they told be in kindergarten some 40+ years ago).
So for the example input

Code: Select all

1 0
5 1
0 0
7

we should get "??" and "1", instead of "0" and "0", as the example output.

Only after accepting the judge's golden rule 1+1=1, I got my submission accepted...

[Andrey Mokhov]

Hello, little joey!

I also found it to be funny.
First variant of my program gave wrong sample output. So I had to remove some if's to make it behave the way judges want...

Bye.
Andrey.

[blazer]

I am not sure, but fourth case in test input seems wrong to me.
It's

Code: Select all

6 3
2 3 -3 4 1 0 1

and the answer is:

Code: Select all

-1 2 -3

but

Code: Select all

2x^6 + 3x^5 -3x^4 + 4x^3 + x^2 + 1 = (x^3 + 1)(2x^3 + 3x^2 - 3x + 2) + (-2x^2 + 3x - 1)

so in my opinion the right answer should be -2 3 -1.
Please tell me, where I am wrong.

[little joey]

Read carefully!

The next n+1 integers give the coefficients of a(x), starting from a0 and ending with an.

So 2 3 -3 4 1 0 1 means x^6 +x^4 +4x^3 -3x^2 +3x +2.

[sumankar]

Can i get some tricky i/o? I read the other post, and my code conforms to the oddity pointed
out by Little Joey.Still WA...
Regards,
Suman.

[Ashganek]

It is not that x^0 + 1 = 1 + 1 = 1.

Try to div by x^0 + 1:

x^2 - x^2
-------------------
x^2 + 2x + 4 : x^0 + 1
-x^2 - x^2
-------------------
-x^2 + 2x + 4
+x^2 + x^2
-------------------
x^2 + 2x + 4

you got a neverending loop.

[magurmach]

I think application of polynomial theorem make the problem lot easier to understand and easier to solve!
As we are dividing y=f(x) by (x^k+1) so we can alter (x^k) with -1... that makes the problem really easy!