from math import floor,ceil
import random as rd
import math

memo_f = dict()

fact_mem = [1]

def fact(n):
    if len(fact_mem) > n:
        return fact_mem[n]
    if len(fact_mem) == n:
        a = n * fact_mem[n-1]
        fact_mem.append(a)
        return a
    return n * fact(n-1)

def to_str(a,b,c):
    return str(a) + "," + str(b) + "," + str(c)

def L(a,b,c,i,j):
    s = [a,b,c]
    k = s[i] - 1 - j
    ibig = (i == 0)
    ismall = 2 - (i==2)
    if k <= s[ibig]-s[ismall]:
        return (j,s[ibig],s[ismall] + k)
    r = k - (s[ibig]-s[ismall])
    return (j, s[ibig] + r - r//2, s[ibig] + r//2)

def compute(a,b,c, depth = 0):
    if a + b + c <= 1:
        return 0
    if not(a >= b >= c):
        a,b,c = sorted([a,b,c], reverse=True)
        return compute(a,b,c, depth)
    s = [a,b,c]
    state_str = to_str(a,b,c)
    if state_str in memo_f:
        return memo_f[state_str]
    n = a+b+c
    result = fact(n-1) * (a**2 + b**2 + c**2 - a - b - c)//2
    for i in range(3):
        for j in range(s[i]):
            d,e,f = L(a,b,c,i,j)
            result += compute(d,e,f, depth + 1)
    memo_f[state_str] = result
    return result

def gen_random_state(h):
    return [rd.randint(0,h-1) for _ in range(3)]

def gen_all_states(n):
    for a in range(n+1):
        for b in range(min(a+1,n+1-a)):
            c = n-a-b
            if c <= b:
                yield (a,b,c)

def check_ratio(a,b,c):
    d,e,f = a-1,b+1,c
    v1 = compute(a,b,c)
    v2 = compute(d,e,f)
    delta = a-b-1
    fn = fact(a+b+c-1)
    if (v1 - v2) < (fn * delta):
        print(a,b,c)
        raise(NameError("should not happen rip"))
    return v1,v2,delta,fn

def successors(a,b,c):
    l = []
    s = [a,b,c]
    for i in range(3):
        for j in range(s[i]):
            d,e,f = L(a,b,c,i,j)
            if not(d >= e >= f):
                d,e,f = sorted([d,e,f],reverse=True)
            l.append([d,e,f])
    return l

def check_L_opt():
    n = 10
    while True:
        for a,b,c in gen_all_states(n):
            if a <= b + 1:
                continue
            v1 = compute(a,b,c)
            d,e,f = a-1,b+1,c
            v2 = compute(d,e,f)
            if v1 < v2:
                print("L n'est pas optimal pour",a,b,c)
                return False
        n += 1
        print("L est optimal jusque",n)

check_L_opt()