Project Euler 222

プロジェクトオイラー
http://projecteuler.net/index.php

Q222.
内径R=50mmのパイプに半径30,31,...,50mmの球を詰め込む。最も短いパイプで済む詰め込み方の場合パイプの長さを整数のμmで表せ。

球の大きさが十分に大きいので、2次元で考えればよい。だから、詰め込む順でパイプの長さが決まる。並びは、y = √xが上に凸だから、なるべく単調増加・減少のほうがよい。少ない球の数で試してみて、最小となる並びと同様の並びを試してみた。

from math import sqrt

import time
def length(r):

    l = r[0] + r[R-L]

    for k in range(R - L):

        l += 2 * sqrt(R * abs(r[k] + r[k+1] - R))

    return l
t = time.clock()

R = 50

L = 30

r = range(R, L - 1, -2) + range(L + 1, R, 2)

l = length(r)

print l * 1000

print time.clock() - t