Submission #3728134

---

Source Code Expand

from functools import lru_cache

A, K = input().split()
K = int(K)

@lru_cache(maxsize=1000)
def digit_search(k, tight, number_s, X):
    if k == len(X):
        diff = abs(int(number_s) -int(A))
        return diff

    digit = int(X[k])
    lim = digit if tight else 9
    res = int(A)
    number_without_0 = number_s
    while True:
        if len(number_without_0)==0 or number_without_0[0]!="0":
            break
        else:
            number_without_0 = number_without_0[1:]
    used = set(number_without_0)
    used_n = len(used)
    if used_n < K:
        res = min(res, digit_search(k+1, tight and digit==X[k],\
                         number_s+str(X[k]), X))
        if X[k]!="0": res = min(res, digit_search(k+1, tight and digit==str(int(X[k])-1),\
                         number_s+str(int(X[k])-1), X))
        if X[k]!="9": res = min(res, digit_search(k+1, tight and digit==str(int(X[k])+1),\
                         number_s+str(int(X[k])+1), X))
    elif used_n == K:
        done = False
        if X[k] in used:
            res = min(res, digit_search(k+1, tight and digit==X[k],\
                         number_s+str(X[k]), X))
            done = True
        if X[k]!="0" and str(int(X[k])-1) in used:
            res = min(res, digit_search(k+1, tight and digit==str(int(X[k])-1),\
                             number_s+str(int(X[k])-1), X))
            done = True
        if X[k]!="9" and str(int(X[k])+1) in used:
            res = min(res, digit_search(k+1, tight and digit==str(int(X[k])+1),\
                             number_s+str(int(X[k])+1), X))
            done = True

        if not done:
            for i in used:
                res = min(res, digit_search(k+1, tight and digit==int(i),\
                                            number_s+str(i), X))
    else:
        pass


    return res

print(digit_search(0, True, "", A))

Submission Info

Judge Result