E>COINS_COUNT = 12
E>SCALE_RESULTS = "<=>" # возможные результаты взвешивания

E>ALL_COINS = set(range(1,COINS_COUNT+1))    
E>ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
E>MAX_SPLIT_SIZE = COINS_COUNT

E>def _get_subsets_sizes( max_size, max_diff, max_sum ) :
E>    """
E>    Генерируем последовательность размеров пар подмножеств, таких, 
E>    что бы каждое следующее можно было получить из какого-то предыдущего
E>    И что бы сначала перебирать группы множеств с меньшей вариативностью. 
E>    """
E>    res = set() # будем строить множество, что бы не париться с повторами, хотя мы и строим каждую пару один раз
E>    for left_size in range(1, max_size+1) : # леове множество всегда не пустое и максимум max_size
E>        for right_size in range( max(0, left_size-max_diff), min(max_size, left_size+max_diff ) + 1 ) :
E>            to_add = left_size, right_size
E>            assert to_add not in res, f"Повторно сгенерировали пару {to_add}" #это для эстетов
E>            # Мы уже итерируем такие значения right_size, что 0 <= right_size <= max_size
E>            # И -max_diff <= right_size - max_size <= max_diff
E>            if sum(to_add) <= max_sum : # Но есть ещё условие на максимальную сумму размеров
E>                res.add( to_add ) 
E>    # множество построено, осталось отсортировать.
E>    return sorted( res, key=lambda x:(sum(x), max(x), x))

E>def _build_start_1_0_trios( items ) :
E>    """
E>    Строим самое первое подмножество подмножеств, в котором в левом по одному, а правое пустое
E>    За одно вычисляем в каждом случае упорядоченный rest, все элементы в котором больше, 
E>    чем элемент в левом подмножестве
E>    """
E>    items = tuple( sorted( set(items) ) ) #делаем уникальный упорядоченный набор элемнтов
E>    return [(items[i:i+1], tuple(), items[i+1:]) for i in range(len(items))]

E>def _gen_add_item_to_left( trios ) :   
E>    """
E>    перечисляет результаты возможного расширения левых подмножества, за счёт остатков из той же тройки
E>    """
E>    for l, r, rest in trios : #для всех троек
E>        used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
E>        rest = [c for c in rest if c not in used]
E>        for c in rest :
E>            if c > l[-1] : #l пустым быть не может. Строим только упорядоченные подмножества
E>                yield l+(c,), r, rest

E>def _gen_add_item_to_right( trios ) :
E>    """
E>    перечисляет результаты возможного расширения правых подмножества, за счёт остатков из той же тройки
E>    """
E>    for l, r, rest in trios : #для всех троек
E>        if r : # правое подможество, в отличии от левого, может быть пустым!
E>            used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
E>            rest = [c for c in rest if c not in used]
E>            for c in rest :
E>                if c > r[-1] : # Строим только упорядоченные подмножества
E>                    yield l, r+(c,), rest
E>        else : # случай пустого правого подмножества -- некоторые отсечения нельзя выполнить.
E>            used = set( l ) # строим остаток, в котором нет элемнтов из l и r (но оно всё равно пустое)
E>            rest = [c for c in rest if c not in used]
E>            for c in rest :
E>                yield l, (c,), rest

E>def gen_sorted_pairs( items, max_diff, max_size ) :
E>    """
E>    Генерирует множество пар упорядоченных подмножеств items
E>    """
E>    if max_size < 1 : # нечего генерировать
E>        return
E>    trios_1_0 = _build_start_1_0_trios(items)
E>    if max_diff < 1 : # особый случай, когда надо "преодолевать пропасть в два прыжка"
E>        cur_trios = list( _gen_add_item_to_right(trios_1_0) ) #построили тройки для множеств 1х1
E>        for t in cur_trios :
E>            yield (set(t[0]), set(t[1]))
E>        for i in range(2, max_size+1) :
E>            # Прыжок №1. Сортируем, что бы удобнее было ориентироваться
E>            tmp = _gen_add_item_to_left( sorted( cur_trios ) ) # в генерируемых множествах
E>            # Прыжок №2. Выдаём множества по одному, что бы у перебора была возможность отсечься
E>            cur_trios = [] # Но, если, нам потребуется и более поздняя группа, сохраняем выданное только что множество
E>            for t in _gen_add_item_to_right( tmp ):
E>                cur_trios.append( t )
E>                yield (set(t[0]), set(t[1]))
E>    else : # max_diff >= 1 -- можем позволить себе строить подмножества увеличивая их по одному!
E>        cache = { (1,0):trios_1_0 } # в этом словаре будем хранить наборы множеств, которые планируем расширять
E>        for size in _get_subsets_sizes(max_size, max_diff, len(items)) :
E>            left_size, right_size = size
E>            tmp = []
E>            if size in cache :
E>                for t in cache[size] :
E>                    yield (set(t[0]), set(t[1]))
E>            elif (left_size, right_size-1) in cache :
E>                for t in _gen_add_item_to_right( cache[(left_size, right_size-1)] ) :
E>                    yield (set(t[0]), set(t[1]))
E>                    tmp.append(t)
E>                tmp.sort()
E>                cache[size] = tmp
E>            elif (left_size-1, right_size) in cache :
E>                for t in _gen_add_item_to_left( cache[(left_size-1, right_size)] ) :
E>                    yield (set(t[0]), set(t[1]))
E>                    tmp.append(t)
E>                tmp.sort()
E>                cache[size] = tmp
E>            else :
E>                assert False

E>def _scale_all_states( left, right, states ) :
E>    """
E>    разбить множество состояний на случаи < = >
E>    """
E>    res = { "count":None, "vs": (left, right), '<':[], '=':[], '>':[] }
E>    for s in states :
E>        if -s in left or s in right :
E>            res['<'].append( s )
E>        elif s in left or -s in right :
E>            res['>'].append( s )
E>        else :
E>            res['='].append( s )
E>    return res
    
E>def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
E>    """
E>    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
E>    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
E>    states -- множество возвожных исходов
E>    max_count - максимальное число взвешиваний
E>    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
E>    """
E>    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
E>        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
E>    if len(states) > 3**max_count :
E>        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
E>    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
E>    coins_count = coins_count or len( unknown )
E>    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
E>        scale_res = _scale_all_states( l, r, states )
E>        #if max_count == 3 and len(l) == 4 and len(r) == 4:
E>        #    print( l, r, scale_res )
E>        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
E>        if max_state_len > 3**(max_count-1) :
E>            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
E>        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
E>            scale_res["count"] = 1
E>            return scale_res
E>        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
E>        #    continue #Это только эвристика, но правдоподобная!
E>        if max_count <= 1 :
E>            continue # больше ничего сделать нельзя
        
E>        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
E>        scale_count = 0
E>        for k in SCALE_RESULTS :
E>            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
E>            if substrategy is None : # разделить не удалось!
E>                scale_res = None
E>                break
E>            scale_res[k] = substrategy
E>            scale_count = max(substrategy["count"], scale_count)
E>        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
E>            scale_res["count"] = scale_count + 1
E>            return scale_res 
E>    return None

E>get_scale_strategy( ALL_STATES, 3 )
E>