NGM  A Game with Numbers
Nikifor and Trofim play the following game: they write some positive integer smaller than 2,000,000,000 and take turns one after another. Nikifor is the first to make a move. The turn is made by the following rule: from the written integer any nonzero digit is subtracted, and the new integer replaces the old one on the desk. For example for integer 40534, the next move can be: 40530, 40531 or 40529. The winner is the player who writes zero on the desk.
Write a program to decide who will win if both players do their best.
Input
The input contains the positive integer from which the game is started.
Output
In the first line you must write 1 if Nikifor wins and 2 otherwise. If Nikifor wins then in the second line you must output the move in the first turn which guarantees victory for him. If there are many such moves then output any of them.
Example
Input: 14 Output: 1 4
Author: Filimonenkov D.O.
hide comments
scorpion_ajay:
20170114 09:39:48
try hubullu before this, it will be double fun :) 

pradeepgangwar:
20170109 10:27:56
Last edit: 20170109 10:31:34 

anikdeyshaon:
20161231 13:33:42
Last edit: 20161231 13:34:35 

aditya9125:
20161228 07:38:20
Sometimes just using pen paper solves the problem..try it. 

narutohokage_1:
20161024 19:37:00
KNOW THAT YOU ARE NO LESS THAN ANYONE ELSE. Do not look for hint , Just be patient and hardworking. I saw this problem one month ago , i gave 5 minutes to it , i was not able to think out , i left the problem. Now today i tried and succeded , if you are unable to think clear just take a break , relax. You will surely solve it. Learnt Something Today, Do not look for hint , as it will not help you learn anything ... and that feeling of solving will not be there ... 

narutohokage_1:
20161024 19:35:34
Do not read the comment , every problem before knowing the logic or having intuition behind it look difficult after that it looks easy. Just know this thing and 

angel_of_death:
20161020 15:49:06
Awesome problem. Simple but clever logic. 

sayedathar11:
20160814 09:25:59
Too easy to miss out Ac in One go my 30 th :) 

cnexans:
20160727 18:06:18
I got TLE because the algorithm was playing the game... this can be done in constant time... AC. 

pt97:
20160719 21:12:10
In a move a person can subtract 19 no from the n..is it 
Added by:  Roman Sol 
Date:  20060505 
Time limit:  0.620s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JS NODEJS PERL 6 VB.net 
Resource:  ZCon 2007 