A Zero-Sum Game of Threes - Dailyprogrammers [2015-11-04] Challenge #239 [Intermediate]

dlyprgrmr239i.py

import functools

@functools.lru_cache(maxsize=None)
def redu(n, s=0):
    if n < 1 or s < -2 or s > 2:
        return None
    if n == 1:
        if s == 0:
            return [(1, 0)]
        else:
            return None
    if n%3 == 0:
        for_zero = redu(n//3, s)
        if for_zero:
            return [(n, 0)] + for_zero
        else:
            return None
    elif n%3 == 1: # -1 or +2
        for_neg_1 = redu((n - 1)//3, s + 1)
        if for_neg_1:
            return [(n, -1)] + for_neg_1
        else:
            for_pos_2 = redu((n + 2)//3, s - 2)
            if for_pos_2:
                return [(n, 2)] + for_pos_2
            else:
                return None
    elif n%3 == 2: # +1 or -2
        for_pos_1 = redu((n + 1)//3, s - 1)
        if for_pos_1:
            return [(n, 1)] + for_pos_1
        else:
            for_neg_2 = redu((n - 2)//3, s + 2)
            if for_neg_2:
                return [(n, -2)] + for_neg_2
            else:
                return None

seq = redu(int(input()))
if seq:
    for t in seq:
        print(*t)
else:
    print('Impossible')