Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Analytical solution solution in Clear category for Feed Pigeons by quarkov
from math import sqrt
'''
The point of this solution is to avoid loop, so it is fast for big n-s.
Sequence of the pigeons amount for the every minute is 1, 3, 6, 10, 15 ...
It's the triangular numbers sequence, which is a(i) = (i+1)*i/2
Sequence of the fed pigeons for the every minute is 1, 4, 10, 20, 35 ...
It's the tetrahedral numbers sequence, which is a(i) = i*(i+1)*(i+2)/6.
Put a(i) = n (amount of the wheat portions)
Get the cubic equation: i*(i+1)*(i+2) - 6*n = 0 which is possible to solve
(have a look into the Cardano's method).
The result is the very moment the wheat should run out.
Be aware it's not working for n = 0.
'''
def checkio(n):
alpha = (3*n - sqrt(9*(n**2)-1/27)) ** (1/3)
beta = (3*n + sqrt(9*(n**2)-1/27)) ** (1/3)
minute = (alpha + beta - 1) // 1 + 1
last_pigeons = (minute-1)*minute/2
last_feed = (minute**2 - 1)*minute / 6
if n - last_feed > last_pigeons:
last_pigeons = n - last_feed
return last_pigeons
'''
Below you can see simple loops solution.
def checkio(n):
pigeons = 0
i = 1
while n > pigeons:
n -= pigeons
pigeons = i*(i+1)/2
i += 1
if n > (i-2)*(i-1)/2:
return n
else:
return (i-2)*(i-1)/2
'''
June 15, 2018
Comments: