## 10586 - Polynomial Remains

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 10586 - Polynomial Remains

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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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
New poster
Posts: 1
Joined: Wed Mar 24, 2004 8:24 pm
Location: Warsaw
Contact:

### 10586 test input

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``````

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
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
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm
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
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

### Re: 10586 - Polynomial Remains

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!