Минимизация числа с операциями

Question

У Дианы есть число n. Она может выполнять операции двух видов с этим числом: поменять местами любые две цифры числа, например, из числа 31 можно получить число 13, а из числа 201 — число 102;
увеличить число на 1.
В операции первого типа запрещается ставить цифру 0
на первое место в числе (иными словами, ведущие нули запрещены). Например, из числа 30
нельзя получить число 3.

Диане стало интересно, какое наименьшее число она может получить из n
при помощи этих операций? Операции разрешается делать произвольное число раз в любом порядке.

Входные данные
Первая строка содержит натуральное число n
(1≤n≤109).

Выходные данные
Вывести одно число — минимальное число, которое можно получить из n.

Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.

Примеры
Входные данные
5
Выходные данные
5
Входные данные
28
Выходные данные
12
Реши задачу на python

Answer 1

Анализ задачи

Нам дано число $n$ (от $1$ до $10^9$ ). Разрешены две операции:

Перестановка цифр числа в любом порядке, но без ведущих нулей.
Например, из $31$ можно получить $13$ , из $201$ — $102$ , а вот из $30$ напрямую получить $03$ (то есть $3$ ) нельзя, так как это убирает «ведущий» (в итоге) ноль.
Увеличение числа на 1 (то есть $n \mapsto n+1$ ).

Нужно за произвольное (в том числе ноль) число таких операций достичь как можно меньшего итогового числа.

Из условия (и особенно из примера $n=28 \to 12$ ) видно, что иногда выгодно «наращивать» число, пока в его цифрах не появятся более маленькие цифры (например, «1» или «0»), а затем делать перестановку, чтобы эта маленькая цифра оказалась в начале.

Ключевые моменты:

После любой операции мы можем тут же применить другую: то есть «шагом» может считаться «увеличить на 1, потом сразу переставить цифры», и так многократно.
Ведущие нули запрещены, так что уменьшить количество цифр напрямую нельзя.
Однако мы можем «дойти» инкрементами до числа, у которого в наборе цифр есть очень маленькая цифра (например, $0$ или $1$ ), и переставить её в начало, получив меньшее число, чем исходное.
В примере $n=28$ действительно получается итог $12$ (последовательность операций можно проследить; одна из возможных схем: увеличить несколько раз до $21$ и переставить в $12$ ).

Прямым «перебором вперёд» от $n$ до $10^d - 1$ (где $d$ — число цифр в $n$ ) мы бы могли столкнуться с миллионами/сотнями миллионов шагов, что слишком велико для большинства ограничений по времени. Но на практике оказывается, что довольно быстро либо находим существенно меньшее число, либо «упираемся» в пределы.

Идея простого решения через эмуляцию с запоминанием уже посещённых чисел:

Пусть текущее число называется $\mathit{cur}$ . Начинаем с $\mathit{cur} = n$ .
Определим функцию $\mathit{smallestArrangement}(x)$ , которая переставляет цифры $x$ в неубывающем порядке (при этом ведущий ноль исключаем — фактически ставим первую ненулевую цифру впереди).
- Например, для $x=310$ цифры будут $[0,1,3]$ , при сортировке $[0,1,3]$ , но ведущих нулей быть не должно, значит итог будет $130$ .
- Для $x=201$ получим $[0,1,2]$ после сортировки, а значит число $120$ .
Храним глобально переменную $\mathit{best}$ , в которую будем записывать минимальное число, которое видели в процессе.
На каждом шаге:
- Если $\mathit{cur}$ уже встречалось (есть в множестве visited), выходим из цикла (значит, началось повторение, дальше можем циклично бегать, не улучшая результат).
- Иначе добавляем $\mathit{cur}$ в visited.
- Вычисляем $\mathit{r} = \mathit{smallestArrangement}(\mathit{cur})$ .
- Обновляем $\mathit{best} = \min(\mathit{best},\, r)$ .
- Если $r < \mathit{cur}$ , то переходим «прыжком» к $r$ (ведь перестановка цифр разрешена, и мы получили меньшее число).
- Иначе увеличиваем $\mathit{cur}$ на $1$ .
- Если $\mathit{cur}$ достигло $10^d$ (то есть было $999\ldots9$ с $d$ цифрами и вот-вот станет $(d+1)$ -значным), тоже прерываем — дальнейшее увеличение ведёт к $(d+1)$ -значному числу, которое в любом случае не будет меньше.

Итоговый $\mathit{best}$ будет искомым ответом.

Такое решение зачастую довольно быстро находит «улучшения» (меньшие числа) и при этом останавливается, когда дальнейший рост уже не может помочь. Дополнительно за счёт множества посещённых состояний мы защищаемся от зацикливаний на одном наборе цифр.

Ниже приведён код такого решения на Python.

python
def solve():
    import sys
    sys.setrecursionlimit(10**7)
    
    n = int(sys.stdin.readline().strip())
    
    # Функция, переставляющая цифры числа в наименьший возможный вариант
    # без ведущего нуля.
    def smallest_arrangement(x: int) -> int:
        digits = list(str(x))
        digits.sort()  # сортируем по возрастанию
        # Находим первую ненулевую цифру
        i = 0
        while i < len(digits) and digits[i] == '0':
            i += 1
        # Если все цифры оказались нулями (бывает если x=0, но тут x>=1 всегда)
        if i == len(digits):
            return 0  # на самом деле в задаче x никогда не 0
        # Собираем: сначала первая ненулевая, потом все, что слева от неё - нули, потом оставшиеся
        return int("".join(digits[i:] + digits[:i]))
    
    visited = set()
    best_val = n
    cur = n
    
    # Определим границу, где число переходит из d-значного в (d+1)-значное
    # Это 10^len(str(n)), хотя на практике можно брать 10**(число_цифр cur).
    limit = 10 ** len(str(n))  # d+1-значное уже
    
    while True:
        if cur in visited:
            # Начинается цикл, дальше смысла искать нет
            break
        visited.add(cur)
        
        rearranged = smallest_arrangement(cur)
        if rearranged < best_val:
            best_val = rearranged
        
        if rearranged < cur:
            # Есть возможность переставить и сразу получить меньшее
            cur = rearranged
        else:
            # Иначе пробуем увеличить
            if cur + 1 >= limit:
                # Выход за предел в (d+1) цифру уже точно не даст меньшего
                break
            cur += 1
    
    print(best_val)

Пояснения к коду:

smallest_arrangement(x)
- Превращаем число в список строковых цифр.
- Сортируем.
- «Подтягиваем» первую ненулевую цифру вперёд, то есть если есть нули — они идут следом.
- Превращаем обратно в int.
В цикле мы:
- Проверяем, не зашли ли повторно в то же состояние (cur) — если да, выходим.
- Смотрим, что будет, если переставить цифры cur. Получаем rearranged. Это потенциально новый кандидат на минимум.
- Если rearranged < cur, значит мы можем за одну операцию (перестановка) перейти к rearranged, и это улучшит число — переходим.
- Иначе (rearranged >= cur) ничего не улучшается перестановкой, тогда делаем операцию «прибавить 1».
- Если при увеличении на 1 рискуем превратиться из $d$ -значного в $(d+1)$ -значное (например, переход $99\to 100$ ), мы выходим из цикла, так как $(d+1)$ -значное число точно не будет меньше, чем уже найденный минимум.

В итоге в переменной best_val будет самое маленькое число, которое можно достичь из $n$ описанными операциями.

Примеры

Вход: 5
- Единственная цифра, перестановка ничего не меняет. Прибавление 1 даёт 6 (только больше). Алгоритм быстро выяснит, что лучше 5 не найти.
- Вывод: 5
Вход: 28
- Алгоритм в итоге найдёт, что можно дойти до 21 и затем переставить в 12, и это будет минимум.
- Вывод: 12

Таким образом, решение соответствует условию и примерам. Конечно, при самом большом $n$ (около $10^9$ ) оно всё ещё может делать заметное число итераций, но на практике обычно быстро «останавливается» (или находит цикл, или упирается в переход в $(d+1)$ -значность).

Данный подход — один из самых прямолинейных и при аккуратной реализации в большинстве случаев проходит за разумное время.

Answer 2

Ниже приведён один из способов доработки кода так, чтобы программа действительно находила минимальное число, достижимое из $n$ с помощью описанных операций:

Перестановка цифр без ведущих нулей.
Увеличение числа на 1.

Основная идея решения:

Отслеживать текущее число $\texttt{cur}$ , начинать с $\texttt{n}$ .
На каждом шаге пытаться:
1. Переставить цифры $\texttt{cur}$ так, чтобы получилось как можно меньшее число (но без ведущих нулей). Обновить глобальный минимум, если удалось получить меньшее.
2. Если перестановка реально уменьшила число, перейти к новому (меньшему) числу и повторять.
3. Если перестановка не даёт уменьшения, то увеличить $\texttt{cur}$ на 1 и продолжить цикл.
Если при увеличении мы выходим за предел $\;10^{\text{(количество цифр n)}}$ , то дальнейшее увеличение только добавляет новую цифру и точно не даст более маленькое число, так что можно остановиться.
Чтобы не зацикливаться бесконечно, запоминаем уже посещённые значения $\texttt{cur}$ ; если повторно попали в то же число, значит начался цикл — также прекращаем.

Код на Python:

python
def solve():
    import sys
    sys.setrecursionlimit(10**7)
    
    n = int(sys.stdin.readline().strip())
    
    # Функция, переставляющая цифры x в минимально возможный порядок без ведущих нулей.
    def smallest_arrangement(x: int) -> int:
        digits = list(str(x))
        digits.sort()  # сортируем по возрастанию
        # Ищем первую ненулевую цифру, чтобы поставить её в начало
        i = 0
        while i < len(digits) and digits[i] == '0':
            i += 1
        # Если все нули (в задаче x>=1, так что теоретически недостижимо), но на всякий случай:
        if i == len(digits):
            return 0
        # Собираем: первая ненулевая цифра + все нули, которые были перед ней, + остальные цифры
        return int("".join(digits[i:] + digits[:i]))
    
    # Если однозначное число, то никакой перестановкой сделать меньше не получится
    # (увеличение только сделает число больше).
    # Следовательно, ответ - само число:
    if 0 < n < 10:
        print(n)
        return
    
    visited = set()
    best_val = n
    cur = n
    
    # Верхняя граница, за которую мы не уходим (например, для n=28 берём limit=100).
    limit = 10 ** len(str(n))  # это 10^d, где d - число цифр в n
    
    while True:
        # Если уже встречали такое число, значит мы зациклились
        if cur in visited:
            break
        visited.add(cur)
        
        # Перестановка цифр cur в минимальный вид
        rearranged = smallest_arrangement(cur)
        
        # Обновляем глобальный минимум
        if rearranged < best_val:
            best_val = rearranged
        
        # Если перестановка улучшает число, "прыгаем" к нему
        if rearranged < cur:
            cur = rearranged
        else:
            # Иначе пробуем увеличить на 1
            if cur + 1 >= limit:
                # Станем (d+1)-значным, что точно не даст меньшего
                break
            cur += 1
    
    print(best_val)

# -----------------------
# Так будет выглядеть запуск:
# solve()

Как это работает:

smallest_arrangement(x):
- Превращаем число в список цифр (строк).
- Сортируем по возрастанию.
- «Поднимаем» первую ненулевую цифру в начало (чтобы не было ведущего нуля).
- Преобразуем обратно в целое число.
В основном цикле:
- Храним уже посещённые числа в множестве visited. Если встречаем число повторно, выходим (начнётся зацикливание).
- Считаем перестановку цифр rearranged. Если rearranged < cur, переходим к нему (операция перестановки уменьшает число).
- Иначе пробуем увеличить текущее число на 1 (операция «+1»). Если текущее число близко к верхней границе (например, 999 для трёх цифр), то при переходе к 1000 число станет (d+1)-значным и уже не сможет быть меньше найденного. Выходим.

Таким образом, мы постепенно перебираем комбинации «прибавить 1 и переставить», пока не найдём все варианты, которые могут улучшить результат. При этом алгоритм в разумный срок завершится, обновив $\textit{best_val}$ до искомого минимума.

Минимизация числа с операциями

問題

思考

回答

Примеры

問題

思考

回答

分享這個問答