Organ-free Man
면접 대비시간 제한1초메모리 제한1024 MB
y가 주어질 때 각 자릿수의 팩토리얼 합이 y가 되는 가장 작은 음이 아닌 정수 x를 구한다.
문제
Every so often, a shipment of universal robots comes from Earth to Mars in order to help you with routine colonization tasks. The robots are called Organ-free Men (precisely OFMv5001.41.912) and each one of them is identified by a unique serial number, which is a positive integer.
To prevent space theft, OFMs are transported from Earth to Mars in a locked state and have to be first unlocked by a special password. The password to unlock an OFM is based on its serial number and a function f(x). The function f(x) is defined as follows:
If 0 ≤ x ≤ 9, then f(x) = x!, and if x > 9, then f(x) = (x mod 10)! + f(⌊x/10⌋). The brackets ⌊⌋ denote the floor value of a number (e.g. ⌊2.43⌋ = 2). Exclamation mark denotes the factorial, i.e., x! = 1 × 2 × · · · × x for x > 0 and 0! = 1.
To unlock an OFM with a serial number y, you need to input smallest such non-negative integer x, so that f(x) = y holds.
Will you manage to unlock all robots that were shipped to you?
입력
The input consists of one integer y (1 ≤ y ≤ 109), the serial number of a particular OFM.
출력
Output a single non-negative integer x, the password to unlock the particular OFM.