Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Newton method solution in Speedy category for Feed Pigeons by Sim0000
def checkio(number):
# At first, we calculate the minute from number.
# Using Newton method, I solve the following equation in order to determine the answer.
#
# x^3 + 3*x^2 + 2x - 6*number = 0
#
# Initial value for Newton method is good approximation of the answer.
# Special thanks to macfreek. We can see following URL for his detailed explanation.
# http://www.checkio.org/mission/feed-pigeons/publications/macfreek/python-3/all-math/
#
# The number of iteration for Newton method is 2.
# This is enough for range given in precondition 0 < N < 10^5.
# For confirmation, I examined all the number of this range.
# To expand the range further, I was confirmed that there was no problem up to 10^6.
#
# initial value
t = (6 * number) ** (1 / 3)
# Newton method
for i in range(2):
t -= (t*(t + 1)*(t + 2) - 6*number) / (3*t*(t + 2) + 2)
t = int(t)
# Once the minute is determined, the number of fed pigeons can calculate easily.
return max(t*(t + 1) // 2, number - t*(t + 1)*(t + 2) // 6)
#These "asserts" using only for self-checking and not necessary for auto-testing
April 26, 2014
Comments:
