# Untitled

By: a guest on Apr 18th, 2012  |  syntax: None  |  size: 0.74 KB  |  hits: 7  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. X = 233
2. Y = 456
3. Z = 787
4. TARGET = 10000000000
5.
6. def gcd(x, y): # x >= y
7.     mod = x%y
8.     if mod == 0: return y
9.     return gcd(y, x%y)
10.
11. def lcm(x, y):
12.     g = gcd(max(x,y), min(x,y))
13.     return x*y / g
14.
15. MAX_X = min(lcm(Y, X)/X, lcm(Z, X)/X)
16. MAX_Y = lcm(Y, Z)/Y
17.
18. def solve():
19.     tgt = TARGET
20.     _X = X
21.     _Y = Y
22.     _Z = Z
23.     min_result = tgt
24.     for num_xy in xrange(MAX_X + MAX_Y - 1):
25.         for x in xrange(num_xy):
26.             y = num_xy - x
27.             if (tgt - y*_Y - x*_X) % Z == 0:
28.                 z = (tgt - y*_Y - x*_X) / Z
29.                 result = x+y+z
30.                 if result < min_result:
31.                     print x, y, z, x*_X+y*_Y+z*_Z
32.                     min_result = result
33.                     break
34.     return min_result
35.
36. print solve()