from fractions import Fraction

def frac_to_binary(f):
    x = Fraction(2, 1)
    while f > 0:
        r = f * x
        if r.numerator >= r.denominator:
            f -= Fraction(1, x)
            yield '1'
        else:
            yield '0'
        x *= 2
        
def binary_to_frac(b):
    x = Fraction(0)
    e = 2
    for c in b:
        if c == '1':
            x += Fraction(1, e)
        e *= 2
    return x


def string_to_binary(s, dct):
    s += 'Z'    
    h = {}
    r = 0
    for key, val in dct.items():
        h[key] = (r, r + val)
        r += val
    a, b = Fraction(0), Fraction(1)
    for c in s:
        u, v = h[c]
        a, b = a + Fraction(u, 100) * (b - a), a + Fraction(v, 100) * (b - a)
        if c == 'Z': break
    return a, b

def encode(s, dct):    
    a, b = string_to_binary(s, dct)
    print(a, b)
    ita, itb = map(frac_to_binary, (a, b))
    s, t = "", ""
    while 1:
        try:
            x, y = next(ita), next(itb)
            if x == "0" and y == "1":
                try:
                    yy = next(itb)
                    res = s + '1'
                    return "0." + res
                except:
                    s += '0'
                    while 1:
                        try:
                            xx = next(ita)
                            s += '1'
                            if xx == '0':
                                return "0." + s
                        except:
                            return "0." + s
            s += x
            t += y
        except:
            break
    return "0." + s

def decode(binfrac, model):
    pass