Problem G
Jimbo and the Zerotron
Jimbo works at the Exclamation Corporation (!Corp) where he needs to write the model number on each machine the company manufactures using a special branding stylus, working on one machine per day. !Corp, however, doesn’t number its models sequentially. Instead, !Corp uses model numbers which are the factorial of each machine’s sequential number, and thus Jimbo has to write these factorials digit by digit.
Jimbo doesn’t mind his job, and the digits that he has to write appear on his screen from most significant to least significant so he doesn’t actually have to calculate the factorials, but he would like to know when he will be able to go home. Jimbo knows that he can write one digit per second indefinitely, but he is not above using mechanical assistance to help him out. To aid him, Jimbo has built the Zerotron 000 (it would be the Zerotron 3000 but it only writes zeros). The Zerotron takes $S$ seconds to boot, accept the branding stylus, and process its input, then it can write as many zeros as needed unsupervised, as long as Jimbo inputs the number of required zeros. Jimbo cannot write any digits himself while setting up the Zerotron.
The Zerotron emits a horrible smell, so if it is turned on, Jimbo has to leave and cannot return for the rest of the day, and the smell lingers a little bit, so Jimbo will also only use the Zerotron if it will enable him to leave earlier than if he didn’t use it. Given the sequential model number $N$ that Jimbo has to write the factorial of, what is the shortest amount of time that Jimbo needs to spend working, and what number does he need to input to the Zerotron 000 at the end of the day, if he uses it, in order to achieve this amount of time?
Input
The input consists of two space-separated integers. The first integer is $N (0 \leq N \leq 10^7),$ the sequential number of the machine that Jimbo is writing on. The second integer is $S (1 \leq S \leq 10^7),$ the number of seconds that it takes to fully prepare the Zerotron 000.
Output
If Jimbo does not use the Zerotron 000, the output should consist of a single integer, the number of seconds that Jimbo spends writing the factorial of $N.$ If Jimbo uses the Zerotron 000, the output should consist of two space-separated integers. The first integer should be the number of seconds that Jimbo spends, both writing digits and preparing the Zerotron, and the second integer should be the number that Jimbo enters into the Zerotron before leaving.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 2 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
25 5 |
25 6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
25 6 |
26 |
