Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Feed Pigeons by DiZ
#Let m be the number of passed minutes.
#Let p(m) be the number of pigeons to feed at minute m.
#Let f(m) be the total of pigeons to feed at minute m,
#aka. the maximum amount of given food at minute m.
#At minute M, p(M) = sum(k for k in range(M+1)) = M(M+1)//2
#And f(M) = sum(p(k) for k in range(M+1)) = M(M+1)(M+2)//6
#
#We search M such as f(M-1) < N <= f(M).
#So, 6N <= M(M+1)(M+2) < (M+1)**3
#Thus, M+1 > cubic_root(6N) => M >= cubic_root(6N) as we deal with integers.
#
#Finally, number of fed pigeons will the maximum between:
#- number of fed pigeons at minute M-1 => p(M-1)
#- number of possibly fed pigeons at minute M => N - f(M-1)
def checkio(n):
m = int((6*n)**(1/3))
m += m*(m+1)*(m+2) < 6*n
return max((m-1)*m//2, n - (m-1)*m*(m+1)//6)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio(1) == 1, "1st example"
assert checkio(2) == 1, "2nd example"
assert checkio(5) == 3, "3rd example"
assert checkio(10) == 6, "4th example"
Jan. 6, 2014
Comments:
