EMPTY = -2
UNKNOWN = -1

import sys
sys.setrecursionlimit(3000)


def heights_to_mat(heights, H):
    W = len(heights)
    m = [[EMPTY for _ in range(H)] for _ in range(W)]
    k = 0
    for i in range(W):
        for j in range(heights[i]):
            m[i][j] = k
            k += 1
    return m

class State:
    def __init__(self, _bay = None, _heights = None, H = 0, _req = None, _order = [], max_ind = None, _presence = None, _position = None):
        self.req = _req
        self.heights = _heights
        if _bay is None:
            self.bay = heights_to_mat(_heights, H)
        else:
            self.bay = _bay
        self.order = _order
        self.H = H
        self.W = len(_heights)
        self.n = sum(self.heights)
        if max_ind is None:
            self.max_ind = max([max(l) for l in self.bay])
        else:
            self.max_ind = max_ind
        if _presence is not None:
            self.presence = _presence
        if _position is not None:
            self.position = _position
        else:
            self.presence = [False] * (self.max_ind + 1)
            self.position = [UNKNOWN] * (self.max_ind + 1)
            for i in range(self.W):
                for j in range(self.heights[i]):
                    if self.bay[i][j] >= 0:
                        self.presence[self.bay[i][j]] = True
                        self.position[self.bay[i][j]] = (i, j)
        self.order_pos = 0

    def copy(self):
        bay_copy = [l.copy() for l in self.bay]
        s = State(bay_copy, self.heights.copy(), self.H, self.req, self.order.copy(), self.max_ind, self.presence.copy(), self.position.copy())
        return s

    def move(self,i,j):
        if self.heights[j] < self.H - 1 and self.heights[i] > 0:
            self.bay[j][self.heights[j]] = self.bay[i][self.heights[i] - 1]
            self.bay[i][self.heights[i] - 1] = EMPTY
            self.heights[i] -= 1
            self.heights[j] += 1
            self.position[self.bay[j][self.heights[j] - 1]] = (j, self.heights[j] - 1)
    
    def retrieve(self, i):
        if self.heights[i] > 0:
            self.heights[i] -= 1
            self.presence[self.bay[i][self.heights[i]]] = False
            self.bay[i][self.heights[i]] = EMPTY
            self.n -= 1

    def next_req(self):
        return self.order_pos
    
    def coordinates(self, x):
        return self.position[x]
                
    def add(self, i, x):
        if self.heights[i] < self.H:
            self.bay[i][self.heights[i]] = x
            self.heights[i] += 1
            self.presence[x] = True
            self.n += 1
            self.position[x] = (i, self.heights[i] - 1)

    def to_str_opt(self):
        return "#".join(map(lambda l : ",".join(map(str,l)),self.bay))   

    def apply_order(self):
        for k in range(len(self.order)):
            x = self.order[k]
            i, j = self.coordinates(x)
            self.bay[i][j] = k
        for i in range(self.W):
            for j in range(self.heights[i]):
                x = self.bay[i][j]
                self.position[x] = (i,j)
        self.order = [i for i in range(len(self.order))]

    def __eq__(self, other):
        return (self.heights == other.heights and
                self.req == other.req and
                self.order == other.order and
                self.position == other.position)

    def __hash__(self):
        return hash(self.to_str_opt())

memo = {}
strat = {}

def opt(s):
    c = s.to_str_opt()
    if c in memo:
        return memo[c]
    if max(s.heights) <= 1:
        return 0 
    if s.req is None:
        x = s.next_req()
        s.order_pos += 1
        s.req = s.coordinates(x)
        v = opt(s)
        s.req = None    
        s.order_pos -= 1
        memo[c] = v
        return v
    i,j = s.req
    if s.heights[i] == j+1:
        x = s.bay[i][j]
        s.retrieve(i)
        s.req = None
        v = opt(s)
        s.req = (i,j)
        s.add(i, x)
        memo[c] = v
        return v
    else:
        mini = float("inf")
        for i2 in range(s.W):
            if i2 != i:
                s.move(i,i2)
                mini = min(mini, 1 + opt(s))
                s.move(i2,i)
        v = mini
        memo[c] = v
        return v
    
def ratio(ref_s, s = None, cost = 0):
    if s is None:
        return ratio(ref_s, ref_s.copy())
    if s.n == 0:
        ref_copy = ref_s.copy()
        ref_copy.apply_order()
        v = opt(ref_copy)
        if v == 0 and cost > 0:
            return float("inf")
        if v == 0 and cost == 0:
            return 1
        return cost/v
    if s.req is None:
        maxi = 0
        for i in range(s.W):
            for j in range(s.heights[i]):
                s.req = (i,j)
                x = s.bay[i][j]
                ref_s.order.append(x)
                maxi = max(maxi,ratio(ref_s,s,cost))
                ref_s.order.pop()
                s.req = None
        return maxi
    i,j = s.req
    if s.heights[i] == j+1:
        x = s.bay[i][j]
        s.retrieve(i)
        s.req = None
        v = ratio(ref_s, s, cost)
        s.req = (i,j)
        s.add(i, x)
        return v
    else:
        mini = float("inf")
        for i2 in range(s.W):
            if i2 != i:
                s.move(i,i2)
                mini = min(mini, ratio(ref_s, s, 1 + cost))
                s.move(i2,i)
        return mini
    
s = State(None, [7,0,0], 10, None, [])

print(s.heights)
import time
t0 = time.time()
print("ratio :", ratio(s))
t1 = time.time()
print("obtained in", (t1 - t0), "s")