Рівняння#514

Рівняння (Розбір)

Автор: Костянтин Денисов

Розробник: Ілля Пермяков

Розбір підготовано: Костянтин Денисов

Ідея. Оскільки літер рівно і цифр рівно , будь-яке коректне відображення — це просто перестановка цифр. Тому можна перебрати всі перестановок цифр і знайти ту, що задовольняє умови.

Перебір перестановок. Заведемо масив , який є перестановкою цифр 0..9. Домовимось, що літера 'a'+i отримує цифру .

Переберемо всі перестановки у лексикографічному порядку за допомогою next_permutation: починаємо з \texttt{d} = [0,1,2,\dots,9] і в циклі переходимо до наступної перестановки, доки вони не закінчаться.

Для кожної перестановки:

  • перевіряємо заборону ведучого нуля: цифри для перших літер рядків a,b,c не повинні дорівнювати ;

  • обчислюємо числові значення A,B,C, пробігаючи рядок зліва направо і роблячи x = 10x + \texttt{digit}(\texttt{char});

  • якщо A+B=C, то це шукане відображення.

Після знаходження відображення просто виводимо три рядки, замінивши кожну літеру на її цифру.

Складність. Перестановок . Перевірка однієї перестановки займає O(|a|+|b|+|c|), де кожна довжина не перевищує . Отже, загальний час O(10!\cdot (|a|+|b|+|c|)), пам'ять (не рахуючи збереження рядків).