UFPT2015F - Vampire Numbers
The number 1827 is an interesting number, because 1827 = 21 * 87, and all of the same digits appear on both sides of the ‘=’. The number 136948 has the same property: 136948 = 146 * 938.
Such numbers are called Vampire Numbers. More precisely, a number v is a Vampire Number if it has a pair of factors, a and b, where a * b = v, and together, a and b have exactly the same digits, in exactly the same quantities, as v. None of the numbers v, a or b can have leading zeros. The mathematical definition says that v should have an even number of digits and that a and b should have the same number of digits, but for the purposes of this problem, we’ll relax that requirement, and allow a and b to have differing numbers of digits, and v to have any number of digits.
Given a number X, find the smallest Vampire Number which is greater than or equal to X.
Input
There will be several test cases in the input. Each test case will consist of a single line containing a single integer X (10 ≤ X ≤ 1,000,000). The input will end with a line with a single 0.
Output
For each test case, output a single integer on its own line, which is the smallest Vampire Number which is greater than or equal to X. Output no extra spaces, and do not separate answers with blank lines.
Example
Input: 10 126 127 5000 0 Output: 126 126 153 6880
Added by: | Cormac |
Date: | 2015-09-20 |
Time limit: | 1s-4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | 2011 ACM ICPC Southeast Regional Programming Contest |