10586 - Polynomial Remains

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10586 - Polynomial Remains

Post by little joey » Wed Jan 14, 2004 7:20 pm

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

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Thu Jan 15, 2004 8:55 am

Hello, little joey!

I also found it to be funny. :D
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

Post by blazer » Tue Apr 20, 2004 12:08 am

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.

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

Post by little joey » Tue Apr 20, 2004 8:17 am

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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Apr 28, 2005 8:00 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.

Ashganek
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

Post by Ashganek » Wed Mar 15, 2006 2:35 am

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

Post by magurmach » Sat Jun 09, 2012 9:53 am

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!

Post Reply

Return to “Volume 105 (10500-10599)”