Submit | All submissions | Best solutions | Back to list |
ININT - Incrementing The Integer |
Starting from the number '1', every time you can choose a digit from the current number and add it to the number itself. 23, for example, could be changed into 25 or 26. To get 100, using the above scheme, paths A and B are both possible. A requires 21 steps, but B needs only 17 (which is also the minimum)
A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100
B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100
C is another 17 step solution for 100.
C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100
Now, you are given several numbers, for each number, print the minimum steps S and number of solutions T. As T could be quite large, you should print T%1000000007 instead.
Input
Each line of input contains a integer K as a test case. Input ends with End Of File.
Output
For each test case print the minimum steps and solutions in a single line. If it's impossible to get the number, print "IMPOSSIBLE" instead. ( without the quotes ).
Example
Input: 16 100 87 Output: 4 1 17 2 IMPOSSIBLE
Constraints and Limits
Number of test cases ≤ 100, 1 ≤ K ≤ 10^9.
Added by: | Ajay Somani |
Date: | 2008-02-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 C CPP14 D-DMD ELIXIR ERL FANTOM JAVA JS-RHINO JS-MONKEY PERL6 PIKE |
Resource: | CodeCraft 08, Problem Setter: Jin Bin |