Разбор задачи «Цепочка волшебных ингредиентов»

Идея задачи

Нам дано число из n цифр. Для каждой цифры важна не она сама, а значение её факториала. Нужно построить максимально возможное число, такое что произведение факториалов его цифр совпадает с произведением факториалов цифр исходного числа.

Иными словами, если исходные цифры — это a_1, a_2, ..., a_n, то нужно найти такое число из цифр b_1, b_2, ..., b_k, что:

a_1! · a_2! · ... · a_n! = b_1! · b_2! · ... · b_k!

среди всех подходящих вариантов.

Главная трудность в том, что ответ нужно не просто сделать корректным, а ещё и максимальным как число.

Наблюдение 1. Цифры 0 и 1 бесполезны

Поскольку:

• 0! = 1
• 1! = 1

они никак не влияют на произведение. Значит, при построении «сильного» ответа от них нет пользы.

Наблюдение 2. Не нужно работать с большими числами

Если напрямую считать факториалы и их произведение, числа быстро станут огромными. Но это и не нужно.

Нас интересует только то, как разложить вклад каждой цифры на более выгодные цифры.

Ключевая идея: любую цифру можно заменить на набор других цифр так, чтобы произведение факториалов сохранилось, а итоговое число стало больше.

Наблюдение 3. Выгодные цифры — это 2, 3, 5, 7

Посмотрим на цифры от 2 до 9.

Простые случаи

• 2! уже удобно представлять цифрой 2
• 3! — цифрой 3
• 5! — цифрой 5
• 7! — цифрой 7

Эти цифры уже «хорошие».

Составные цифры

Теперь посмотрим, как выгодно заменить остальные:

• 4! = 24 = 3! · 2! · 2! → 4 заменяем на 322
• 6! = 720 = 5! · 3! → 6 заменяем на 53
• 8! = 40320 = 7! · 2! · 2! · 2! → 8 заменяем на 7222
• 9! = 362880 = 7! · 3! · 3! · 2! → 9 заменяем на 7332

Итоговая таблица замен:

• 0 -> ""
• 1 -> ""
• 2 -> "2"
• 3 -> "3"
• 4 -> "322"
• 5 -> "5"
• 6 -> "53"
• 7 -> "7"
• 8 -> "7222"
• 9 -> "7332"

Это стандартное и самое важное наблюдение во всей задаче.

Почему именно такие замены дают максимум

Здесь важно не просто сохранить произведение факториалов, но и получить максимальное число.

Например, для цифры 4 можно было бы думать про разложение через простые множители числа 24, но нас интересуют именно факториалы цифр, а не просто произведение чисел.

Замена 4 -> 322 хороша по двум причинам:

1. она сохраняет нужный вклад;
2. цифры 3, 2, 2 выгоднее одной цифры 4, если потом отсортировать всё по убыванию.

То же самое относится к 6, 8, 9.

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

Почему этого достаточно:

• набор цифр уже оптимален;
• среди всех перестановок одного и того же набора максимальное число получается, если расположить цифры по убыванию.

Алгоритм

1. Считываем n и строку s.
2. Для каждой цифры s[i] дописываем в ответ соответствующую строку по таблице замен.
3. Сортируем все полученные цифры в порядке убывания.
4. Выводим результат.

Пример

Пусть дано:

4
1234

Тогда:

• 1 -> ""
• 2 -> "2"
• 3 -> "3"
• 4 -> "322"

Собираем все цифры:

23322

Сортируем по убыванию:

33222

Это и есть ответ.

Доказательство корректности

Докажем, что описанный алгоритм действительно строит правильный и максимальный ответ.

Лемма 1

Для каждой цифры от 0 до 9 замена из таблицы сохраняет значение произведения факториалов.

Доказательство.

Проверим все случаи:

• 0! = 1, значит замена на пустую строку ничего не меняет;
• 1! = 1, аналогично;
• 2, 3, 5, 7 остаются сами собой;
• 4! = 24 = 3! · 2! · 2!, значит 4 -> 322;
• 6! = 720 = 5! · 3!, значит 6 -> 53;
• 8! = 40320 = 7! · 2! · 2! · 2!, значит 8 -> 7222;
• 9! = 362880 = 7! · 3! · 3! · 2!, значит 9 -> 7332.

Во всех случаях произведение факториалов сохраняется. Лемма доказана.

Лемма 2

После выполнения всех замен полученный набор цифр можно переставлять как угодно без изменения корректности ответа.

Доказательство.

Корректность зависит только от произведения факториалов цифр, а произведение не зависит от порядка множителей. Значит, перестановка цифр не меняет корректность. Лемма доказана.

Лемма 3

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

Доказательство.

Это стандартный факт: чтобы получить наибольшее число из фиксированного набора цифр, нужно поставить на старшие позиции наибольшие цифры. Лемма доказана.

Теорема

Алгоритм выводит максимальное корректное число.

Доказательство.

По лемме 1 каждая замена сохраняет произведение факториалов, значит итоговый набор цифр корректен. По лемме 2 можно свободно переставлять эти цифры. По лемме 3 максимальная перестановка — это сортировка по убыванию. Следовательно, алгоритм выводит максимальное корректное число. Теорема доказана.

Сложность

Пусть длина исходной строки равна n.

Каждая цифра заменяется на не более чем 4 цифры, поэтому длина промежуточного ответа не превышает 4n.

• Построение ответа: O(n)
• Сортировка: O(m log m), где m <= 4n

Итого:

• Время: O(n log n)
• Память: O(n)

При ограничении n <= 15 решение работает мгновенно.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    string ans;

    for (char c : s) {
        if (c == '0' || c == '1') {
            continue;
        } else if (c == '2') {
            ans += '2';
        } else if (c == '3') {
            ans += '3';
        } else if (c == '4') {
            ans += "322";
        } else if (c == '5') {
            ans += '5';
        } else if (c == '6') {
            ans += "53";
        } else if (c == '7') {
            ans += '7';
        } else if (c == '8') {
            ans += "7222";
        } else if (c == '9') {
            ans += "7332";
        }
    }

    sort(ans.rbegin(), ans.rend());
    cout << ans << '\n';

    return 0;
}

Реализация на Python

n = int(input())
s = input().strip()

ans = []

for c in s:
    if c == '0' or c == '1':
        continue
    elif c == '2':
        ans.append('2')
    elif c == '3':
        ans.append('3')
    elif c == '4':
        ans.extend('322')
    elif c == '5':
        ans.append('5')
    elif c == '6':
        ans.extend('53')
    elif c == '7':
        ans.append('7')
    elif c == '8':
        ans.extend('7222')
    elif c == '9':
        ans.extend('7332')

ans.sort(reverse=True)
print(''.join(ans))

Частые ошибки

1. Разлагать цифру, а не её факториал

Ошибка: пытаться работать так, будто 4 = 2 * 2, и поэтому заменить 4 на 22.

Это неверно, потому что в задаче участвуют факториалы цифр, а не сами цифры.

Нужно смотреть на 4!, а не на 4.

2. Не сортировать итоговые цифры

Даже если замены выполнены правильно, без сортировки можно получить не максимальный ответ.

Например, набор цифр 3, 2, 7, 3 лучше вывести как 7332, а не как 3273.

3. Пытаться считать огромные факториалы

Это не нужно и только усложняет решение.

Вся задача решается на уровне готовой таблицы замен.

Вывод

Эта задача выглядит необычно, но на самом деле сводится к двум шагам:

1. заменить каждую цифру на оптимальный набор цифр по таблице;
2. отсортировать все полученные цифры по убыванию.

Главное содержательное наблюдение — правильные замены для 4, 6, 8, 9.

После этого решение получается коротким, аккуратным и полностью жадным.