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.
hide comments
nadstratosfer:
2017-12-21 16:54:59
In my experience, problems where the fastest C solution exceeds 0.04s are not solvable in Python unless the TL is relaxed (eg. this one probably isn't). |
|
offero:
2017-12-20 02:26:49
Does python even run in the provided time limit? |
|
kayacan:
2014-02-25 11:16:13
what is the limit K |
Added by: | Ajay Somani |
Date: | 2008-02-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | CodeCraft 08, Problem Setter: Jin Bin |