英文解析

34. [ 20 ] (Caos) A cao [sic] has 6 legs, 3 on each side. A walking pattern for the cao is defined as anordered sequence of raising and lowering each of the legs exactly once (altogether 12 actions), startingand ending with all legs on the ground. The pattern is safe if at any point, he has at least 3 legs onthe ground and not all three legs are on the same side. Estimate N , the number of safe patterns.
    ⌊ ⌋
    An estimate of E > 0 earns 20 min( N/E, E/N ) points.4
    Proposed by:
    Answer: 1416528

1 = on ground, 0 = raised, 2 = back on groundcache = {}

def pangzi(legs):
if legs == (2,2,2,2,2,2): return 1
elif legs.count(0) > 3: return 0
elif legs[0] + legs[1] + legs[2] == 0: return 0
elif legs[3] + legs[4] + legs[5] == 0: return 0
elif cache.has_key(legs): return cache[legs]
cache[legs] = 0
for i in xrange(6): # raise a legif legs[i] == 1:
new = list(legs)
new[i] = 0
cache[legs] += pangzi(tuple(new))
elif legs[i] == 0: # lower a legnew = list(legs)
new[i] = 2
cache[legs] += pangzi(tuple(new))
return cache[legs]
print pangzi((1,1,1,1,1,1))