Unlucky Numbers (Codeforces 1808C)
Tags: Greedy, brute force

In this problem, unlike problem A, you need to look for unluckiest number, not the luckiest one.Note that the constraints of this problem differ from such in problem A.Olympus City recently launched the production of personal starships. Now everyone on Mars can buy one and fly to other planets inexpensively.Each starship has a number —some positive integer $$$x$$$. Let's define the luckiness of a number $$$x$$$ as the difference between the largest and smallest digits of that number. For example, $$$142857$$$ has $$$8$$$ as its largest digit and $$$1$$$ as its smallest digit, so its luckiness is $$$8-1=7$$$. And the number $$$111$$$ has all digits equal to $$$1$$$, so its luckiness is zero.Hateehc is a famous Martian blogger who often flies to different corners of the solar system. To release interesting videos even faster, he decided to buy himself a starship. When he came to the store, he saw starships with numbers from $$$l$$$ to $$$r$$$ inclusively. While in the store, Hateehc wanted to find a starship with the unluckiest number.Since there are a lot of starships in the store, and Hateehc can't program, you have to help the blogger and write a program that answers his question.  

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 600$$$) —the number of test cases.Each of the following $$$t$$$ lines contains a description of the test case. The description consists of two integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — the largest and smallest numbers of the starships in the store.

Output: Print $$$t$$$ lines, one line for each test case, containing the unluckiest starship number in the store.If there are several ways to choose the unluckiest number, output any of them.

Note: Let's look at two test examples:   the luckiness of the number $$$59$$$ is $$$9 - 5 = 4$$$;  the luckiness of $$$60$$$ equals $$$6 - 0 = 6$$$;  the luckiness of $$$61$$$ equals $$$6 - 1 = 5$$$;  the luckiness of $$$62$$$ equals $$$6 - 2 = 4$$$;  the luckiness of $$$63$$$ is $$$6 - 3 = 3$$$.  So the unluckiest number is $$$63$$$.In the fifth test case, the unluckiest numbers are $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$11$$$, $$$22$$$, $$$33$$$, $$$44$$$, $$$55$$$, $$$66$$$, $$$77$$$, $$$88$$$, $$$99$$$, so you are allowed to choose any of them.

Sample Inputs:
5
59 63
42 49
48 53
90 90
1 100

Sample Outputs:
63
44
53
90
1

Solution (Python):
from collections import *
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    (a, b) = input().split()
    lena = len(a)
    lenb = len(b)
    l = ''
    f = 1
    ans = ''
    buti = 10
    ans = a
    buti = int(max(list(a))) - int(min(list(a)))
    i = int(max(list(b))) - int(min(list(b)))
    if buti > i:
        ans = b
        buti = i
    if lena != lenb:
        ans = '9' * lena
    elif a == b:
        ans = a
    else:
        for i in range(lena):
            if f and a[i] == b[i]:
                l += a[i]
            elif f:
                numa = a[i]
                numb = b[i]
                f = 0
                break
        k = j = i
        m = lena - i
        start = int(numa)
        end = int(numb)
        maxnum = ''
        minnum = ''
        if l:
            maxnum = max(list(l))
            minnum = min(list(l))
        for i in range(start + 1, end):
            i = str(i)
            if not maxnum:
                (tmax, tmin) = (i, i)
            else:
                (tmax, tmin) = (max([i, maxnum, minnum]), min([i, maxnum, minnum]))
            (tem1, tem2) = (l + i * m, int(tmax) - int(tmin))
            if tem2 < buti:
                ans = tem1
                buti = tem2
        j += 1
        k += 1
        prel = l + numb
        if not maxnum:
            (tmax, tmin) = (numb, numb)
        else:
            (tmax, tmin) = (max([numb, maxnum, minnum]), min([numb, maxnum, minnum]))
        for i in range(j, lenb):
            if b[i] > tmin:
                if int(tmax) - int(tmin) < buti:
                    ans = prel + tmin * (lenb - i)
                    buti = int(tmax) - int(tmin)
                break
            else:
                if a[i] > '0':
                    c = str(int(b[i]) - 1)
                    tem = int(tmax) - int(c)
                    if buti > tem:
                        ans = prel + c * (lenb - i)
                        buti = tem
                prel += b[i]
                (tmax, tmin) = (max([b[i], tmax, tmin]), min([b[i], tmax, tmin]))
        prel = l + numa
        if not maxnum:
            (tmax, tmin) = (numa, numa)
        else:
            (tmax, tmin) = (max([numa, maxnum, minnum]), min([numa, maxnum, minnum]))
        for i in range(k, lena):
            if a[i] < tmax:
                if int(tmax) - int(tmin) < buti:
                    ans = prel + tmax * (lena - i)
                    buti = int(tmax) - int(tmin)
                break
            else:
                if a[i] < '9':
                    c = str(int(a[i]) + 1)
                    tem = int(c) - int(tmin)
                    if buti > tem:
                        ans = prel + c * (lena - i)
                        buti = tem
                prel += a[i]
                (tmax, tmin) = (max([a[i], tmax, tmin]), min([a[i], tmax, tmin]))
    print(ans)

Solution (Python):
def max_prefix(str1, str2):
    prefix = ''
    for (x, y) in zip(str1, str2):
        if x == y:
            prefix += x
        else:
            break
    return (prefix, str1[len(prefix):], str2[len(prefix):])

def luckiness(string: str):
    digits = set((int(_) for _ in string))
    return max(digits) - min(digits)

def view_above(string: str, prefix_set: set):
    assert len(string) >= 2
    lead = string[0]
    m = min(prefix_set.union([int(string[0])]))
    if m < int(string[1]):
        candidate = lead + str(m) * (len(string) - 1)
    elif m == int(string[1]):
        if int(lead + str(m) * (len(string) - 1)) <= int(string):
            candidate = lead + str(m) * (len(string) - 1)
        else:
            candidate = lead + str(m - 1) * (len(string) - 1)
    elif int(lead + string[1] * (len(string) - 1)) <= int(string):
        candidate = lead + string[1] * (len(string) - 1)
    else:
        candidate = lead + str(int(string[1]) - 1) * (len(string) - 1)
    return candidate

def view_mid(string1: str, string2: str, prefix_set: set):
    assert len(string1) >= 2
    assert int(string1) < int(string2)
    assert int(string1[0]) + 2 <= int(string2[0])
    (M, m) = (max(prefix_set), min(prefix_set))
    candidate = str(int(string1[0]) + 1) * len(string1)
    candidate_luck = max(M, int(string1[0]) + 1) - min(m, int(string1[0]) + 1)
    for digit in range(int(string1[0]) + 2, int(string2[0])):
        luck = max(M, digit) - min(m, digit)
        if luck < candidate_luck:
            candidate = str(digit) * len(string1)
            candidate_luck = luck
    return candidate

def view_below(string: str, prefix_set: set):
    assert len(string) >= 2
    lead = string[0]
    M = max(prefix_set.union([int(string[0])]))
    if M > int(string[1]):
        candidate = lead + str(M) * (len(string) - 1)
    elif M == int(string[1]):
        if int(lead + str(M) * (len(string) - 1)) >= int(string):
            candidate = lead + str(M) * (len(string) - 1)
        else:
            candidate = lead + str(M + 1) * (len(string) - 1)
    elif int(lead + string[1] * (len(string) - 1)) >= int(string):
        candidate = lead + string[1] * (len(string) - 1)
    else:
        candidate = lead + str(int(string[1]) + 1) * (len(string) - 1)
    return candidate

def problem():
    (l, r) = input().split()
    if l == r:
        return l
    if len(l) != len(r):
        return '9' * (max(len(l), len(r)) - 1)
    if int(l[0]) + 2 <= int(r[0]):
        return str(int(l[0]) + 1) * len(l)
    (prefix, l, r) = max_prefix(l, r)
    if len(l) >= 2:
        prefix_set = set((int(_) for _ in prefix))
        candidate_above = view_above(r, prefix_set)
        candidate_below = view_below(l, prefix_set)
        if int(r[0]) - int(l[0]) >= 2:
            candidate_mid = view_mid(l, r, prefix_set)
            best = min([prefix + candidate_above, prefix + candidate_mid, prefix + candidate_below], key=luckiness)
        else:
            best = min([prefix + candidate_above, prefix + candidate_below], key=luckiness)
    elif len(l) == 1:
        best = int(prefix + l)
        best_luckiness = luckiness(prefix + l)
        for last in range(int(l), int(r) + 1):
            candidate = prefix + str(last)
            luck = luckiness(candidate)
            if luck < best_luckiness:
                best_luckiness = luck
                best = candidate
    return best
t = int(input())
for _ in range(t):
    print(problem())

Solution (Python):
for _ in range(int(input())):
    (a, b) = input().split()
    res = 0
    for i in range(int(a[0]), 10):
        t = int(str(i) * len(a))
        if int(a) <= t <= int(b):
            res = t
            break
    if res == 0:
        if len(a) < len(b):
            res = '1' + len(a) * '0'
        else:
            min_delta = int(max(a)) - int(min(a))
            res = a
            if int(max(b)) - int(min(b)):
                res = b
                min_delta = int(max(b)) - int(min(b))
            i = 0
            while i < len(a) and a[i] == b[i]:
                i += 1
            left = a[:i]
            if i != len(a):
                for j in range(int(a[i]), int(b[i]) + 1):
                    for k in range(0, 10):
                        v = left + str(j) + str(k) * (len(a) - i - 1)
                        if int(a) <= int(v) <= int(b) and min_delta > int(max(v)) - int(min(v)):
                            res = v
                            min_delta = int(max(v)) - int(min(v))
    print(res)