Джордж Лукас и 1138
В мире "Звездных войн" хорошо известно, что Джордж Лукас был увлечен числом 1138. THX 1138 — это название его первого фильма, и, как утверждает Wookieepedia: The Star Wars Wiki, Джордж Лукас любил использовать ключевые слова и числа в своих последующих фильмах, чтобы объединить все свои работы.
Если вы разбираетесь в деталях "Звездных войн", то знаете, что в Эпизоде V заключенного перевели из блока камер 1138. В Эпизоде II у всех клонов-штурмовиков номер 1138 заметно отображается на задней части их шлемов. А если ввести 1138 при просмотре DVD Эпизода III, вы сразу переходите к сцене, где Йода исполняет брейк-данс.
Менее известен неопубликованный Эпизод Ноль: Рождение Звезды Смерти Клини. История начинается с C3PO в роли подросткового дроида в школе на его родной планете Татуин, где ему поручено определить все способы, которыми можно комбинировать числа 1, 1, 3 и 8, используя традиционные +, -, *, / и () для генерации других положительных чисел. Он быстро замечает, что 8 / 3 / 1 - 1 генерирует 1, 3 / 8 + 1 + 1 генерирует 2, и что (8 / 3 + 1) * 1 генерирует 3. Через несколько секунд C3PO заявляет, что наименьшее положительное целое число, которое не может быть сгенерировано, это 29. Но прав ли C3PO?
Дана строка из n цифр (1 ≤ n ≤ 7), вычислите все способы, которыми эти n цифр могут быть скомбинированы, используя +, -, *, / и скобки, и выведите наименьшее положительное целое число, которое не может быть сгенерировано.
Для строки "12345" числа от 1 до 75 могут быть сгенерированы, но число 76 не может быть.
Для строки "13555" числа от 1 до 55 могут быть сгенерированы, но 56 не может быть.
Дополнительные детали:
Вы должны использовать все цифры, включая дубликаты.
Вы не можете комбинировать цифры с помощью конкатенации, так что 12 + 345 будет *не* релевантно для генерации всех возможностей от имени "12345".
Деление является целочисленным делением, с усечением, которое вы ожидаете от целочисленного деления. Это означает, что 4 * (5/4) равно 4, а не 5 (хотя (4 * 5)/4 это, конечно, 5, которое вы ожидаете).
Вы должны избегать деления на ноль и не допускать его участия в наборе сгенерированных чисел.
Тестовые входные данные будут такими, что все промежуточные и конечные результаты могут поместиться в 32-битное целое число (long).
Входные данные
Ожидайте серию строк с цифрами, по одной на строку. Конец ввода будет обозначен 0 на отдельной строке. Не обрабатывайте этот случай.
Выходные данные
Вы должны вывести одну строку для каждого входного ряда. Каждая строка должна содержать наименьшее положительное целое число, которое *не* может быть сгенерировано с помощью какого-либо арифметического выражения, включающего все цифры.