Джордж Лукас і 1138
У відомій культурі "Зоряних війн" Джордж Лукас мав особливу пристрасть до числа 1138. THX 1138 — це назва його першого фільму, і, за даними Вукіпедії: Вікі Зоряних війн, Лукас часто використовував це число та інші ключові слова в своїх фільмах, щоб об’єднати всі свої роботи.
Якщо ви знаєтеся на деталях "Зоряних війн", то пам’ятаєте, що в Епізоді 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 на окремому рядку. Не обробляйте цей випадок.
Вихідні дані
Ви повинні вивести один рядок виходу на стандартний вихід для кожного рядка вводу. Кожен рядок виходу повинен містити найменше додатне ціле число, яке *не* може бути отримане за допомогою деякого арифметичного виразу, що включає всі цифри.