846 - Steps

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

Moderator: Board moderators

New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 846 - Steps

Post by Hikari9 »

There is no strict precision to this problem. You just need to manipulate the formula.

Given two integers a, b, we want n such that n*(n+1) = 4*(b-a)-1
(Pascal Triangle formula)

In addition, when the range (a to b) is odd, we actually have n^2 = 4*(b-a)-1 because of the extra n.
Thus, we can get n = floor( sqrt( 4*(b-a)-1 ) )].

Note that we can also apply the same sqrt function for even ranges:
since n*(n+1) = 4*(b-a)-1
n <= sqrt( 4*(b-a)-1[/b] ) <= n+1
( we can use floor! :D )

thus for both even and odd ranges, n = floor( sqrt( 4*(b-a)-1 ) )
*special case: (b-a) == 0

Hope this helps :D
Post Reply

Return to “Volume 8 (800-899)”