poison_mice.py

#-*- coding:utf-8 -*-

import math
from pprint import pprint

combinations = {}
def combination(m, n):
    if n > m: return 0
    if n == 0 or n == m:
        return 1
    else:
        if m not in combinations:
            combinations[m] = {}
        if n not in combinations[m]:
            combinations[m][n] = combination(m-1, n) + combination(m-1, n-1)
            combinations[m][m-n] = combinations[m][n]
        return combinations[m][n]

k = {}
k[2] = 0
k[3] = 2
k[4] = 3
k[5] = 4
k[6] = 5
k[7] = 6
def count_mouse(m):
    if m not in k:
        k_i = []
        for i in range(1, m-1):
            dead_limit = math.ceil(math.log(combination(m, 2) - combination(m-i, 2), 2))
            alive_limit = count_mouse(m-i)
            k_i.append(max(dead_limit, alive_limit))
        k[m] = min(k_i) + 1
    return k[m]
    
def print_combinations(m):
    for i in range(0, m+1):
        print(m, i, combination(m,i))

pprint([{i: count_mouse(i)} for i in range(2, 1001)])