10586 - Polynomial Remains

Moderator: Board moderators

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 05 10 07`

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

little joey
Guru

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

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.
Andrey Mokhov
Experienced poster

Posts: 130
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

10586 test input

I am not sure, but fourth case in test input seems wrong to me.
It's
Code: Select all
`6 32 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.
blazer
New poster

Posts: 1
Joined: Wed Mar 24, 2004 8:24 pm
Location: Warsaw

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.

little joey
Guru

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

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.
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

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.
Ashganek
New poster

Posts: 8
Joined: Thu Jan 19, 2006 10:42 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!
magurmach
New poster

Posts: 26
Joined: Mon May 14, 2012 8:19 pm