def link_chance(p, n):
return (1-p)**(n-1) * p
def success_chance_under(p, n):
return sum(link_chance(p, i) for i in range(1, n))
def find_p_known_median(m, e=.0000001, p1=0., p2=1.):
p = (p1 + p2) / 2
s = success_chance_under(p, m)
if s < 0.5-e:
return find_p_known_median(m, e, p, p2)
elif s > 0.5+e:
return find_p_known_median(m, e, p1, p)
else:
return p
print '6L'
n = 1500
print 'p=1/%d, under %d fusing: %.06f' % (1400, n, success_chance_under(1./1400, n))
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
n = 5
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
n = 2
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
n = 2000
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
n = 4000
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
n = 10000
print 'p=1/%d, under %d fusing: %.06f' % (1500, n, success_chance_under(1./1500, n))
i = 1
s = 0
while s < 0.5:
s += link_chance(1./1500, i)
i += 1
print 'p=1/%d, under %d fusing: %.06f' % (1500, i, s)
print 1.0/find_p_known_median(1500)
print 1.0/find_p_known_median(1501)
print '\n5L'
n = 150
print 'p=1/%d, under %d fusing: %.06f' % (150, n, success_chance_under(1./150, n))
ZGVmIGxpbmtfY2hhbmNlKHAsIG4pOgogICAgcmV0dXJuICgxLXApKioobi0xKSAqIHAKICAgIApkZWYgc3VjY2Vzc19jaGFuY2VfdW5kZXIocCwgbik6CglyZXR1cm4gc3VtKGxpbmtfY2hhbmNlKHAsIGkpIGZvciBpIGluIHJhbmdlKDEsIG4pKQoJCmRlZiBmaW5kX3Bfa25vd25fbWVkaWFuKG0sIGU9LjAwMDAwMDEsIHAxPTAuLCBwMj0xLik6CglwID0gKHAxICsgcDIpIC8gMgoJcyA9IHN1Y2Nlc3NfY2hhbmNlX3VuZGVyKHAsIG0pCglpZiAgIHMgPCAwLjUtZToKCQlyZXR1cm4gZmluZF9wX2tub3duX21lZGlhbihtLCBlLCBwLCBwMikKCWVsaWYgcyA+IDAuNStlOgoJCXJldHVybiBmaW5kX3Bfa25vd25fbWVkaWFuKG0sIGUsIHAxLCBwKQoJZWxzZToKCQlyZXR1cm4gcAoKcHJpbnQgJzZMJwpuID0gMTUwMApwcmludCAncD0xLyVkLCB1bmRlciAlZCBmdXNpbmc6ICUuMDZmJyAlICgxNDAwLCBuLCBzdWNjZXNzX2NoYW5jZV91bmRlcigxLi8xNDAwLCBuKSkKcHJpbnQgJ3A9MS8lZCwgdW5kZXIgJWQgZnVzaW5nOiAlLjA2ZicgJSAoMTUwMCwgbiwgc3VjY2Vzc19jaGFuY2VfdW5kZXIoMS4vMTUwMCwgbikpCm4gPSA1CnByaW50ICdwPTEvJWQsIHVuZGVyICVkIGZ1c2luZzogJS4wNmYnICUgKDE1MDAsIG4sIHN1Y2Nlc3NfY2hhbmNlX3VuZGVyKDEuLzE1MDAsIG4pKQpuID0gMgpwcmludCAncD0xLyVkLCB1bmRlciAlZCBmdXNpbmc6ICUuMDZmJyAlICgxNTAwLCBuLCBzdWNjZXNzX2NoYW5jZV91bmRlcigxLi8xNTAwLCBuKSkKbiA9IDIwMDAKcHJpbnQgJ3A9MS8lZCwgdW5kZXIgJWQgZnVzaW5nOiAlLjA2ZicgJSAoMTUwMCwgbiwgc3VjY2Vzc19jaGFuY2VfdW5kZXIoMS4vMTUwMCwgbikpCm4gPSA0MDAwCnByaW50ICdwPTEvJWQsIHVuZGVyICVkIGZ1c2luZzogJS4wNmYnICUgKDE1MDAsIG4sIHN1Y2Nlc3NfY2hhbmNlX3VuZGVyKDEuLzE1MDAsIG4pKQpuID0gMTAwMDAKcHJpbnQgJ3A9MS8lZCwgdW5kZXIgJWQgZnVzaW5nOiAlLjA2ZicgJSAoMTUwMCwgbiwgc3VjY2Vzc19jaGFuY2VfdW5kZXIoMS4vMTUwMCwgbikpCgppID0gMQpzID0gMAp3aGlsZSBzIDwgMC41OgoJcyArPSBsaW5rX2NoYW5jZSgxLi8xNTAwLCBpKQoJaSArPSAxCnByaW50ICdwPTEvJWQsIHVuZGVyICVkIGZ1c2luZzogJS4wNmYnICUgKDE1MDAsIGksIHMpCgpwcmludCAxLjAvZmluZF9wX2tub3duX21lZGlhbigxNTAwKQpwcmludCAxLjAvZmluZF9wX2tub3duX21lZGlhbigxNTAxKQoKcHJpbnQgJ1xuNUwnCm4gPSAxNTAKcHJpbnQgJ3A9MS8lZCwgdW5kZXIgJWQgZnVzaW5nOiAlLjA2ZicgJSAoMTUwLCBuLCBzdWNjZXNzX2NoYW5jZV91bmRlcigxLi8xNTAsIG4pKQo=