45 lines
1.1 KiB
Python
45 lines
1.1 KiB
Python
# gives one solution of (x,y) for a x + by = c
|
|
def dioph(a, b, c):
|
|
aa,bb,x,y = a, b, 0, 1
|
|
|
|
while True:
|
|
q,a,b = a//b, b, a%b
|
|
x,y = y - q*x, x
|
|
if abs(a) == 1: break
|
|
|
|
if y*aa % bb != 1: y = -y
|
|
x,y = y*c, (c - aa*y*c)//bb
|
|
#assert(x*aa + y*bb == c)
|
|
return x,y
|
|
|
|
# rems: what monkey got each turn
|
|
# min_share: each sailor needs to get at least this many in the final round
|
|
def calcnuts(rems, min_share = 0):
|
|
n, r = len(rems) - 1, 0
|
|
c = (n - 1)**n
|
|
for x in rems: r,c = r + x*c, c//(n-1)*n
|
|
|
|
a, b = (n-1)**n, n**(n+1)
|
|
x, y = dioph(a, -b, r)
|
|
k = (min_share - y + a - 1)//a
|
|
return x + k*b, y + k*a
|
|
|
|
def distribute(nuts, monkey_nuts):
|
|
n = len(monkey_nuts) - 1
|
|
print("\n%d sailors, %d nuts:"%(n, nuts))
|
|
for r in monkey_nuts[:-1]:
|
|
p = (nuts - r)//n
|
|
print("\tNuts %d, hide %d, monkey gets %d" % (nuts, p, r))
|
|
nuts = p*(n - 1)
|
|
|
|
r = monkey_nuts[-1]
|
|
p = (nuts - r)//n
|
|
print("Finally:\n\tNuts %d, each share %d, monkey gets %d" % (nuts, p, r))
|
|
|
|
for sailors in range(2, 10):
|
|
monkey_loot = [1]*sailors + [0]
|
|
distribute(calcnuts(monkey_loot, 1)[0], monkey_loot)
|
|
|
|
# many sailors, many nuts
|
|
#for i in range(1, 5): print(10**i, calcnuts([1]*10**i + [0])[0])
|