NGM - A Game with Numbers

no tags 

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 non-zero 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.


The input contains the positive integer from which the game is started.


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.




Author: Filimonenkov D.O.

hide comments
incomplet_: 2018-04-17 09:44:55

Best move means that they try their best to win the game, it does not mean the largest number in each turn

srjsunny: 2018-01-24 16:04:57

long long int will work

bani_raheja: 2018-01-15 10:23:09

lol. what kind of prob is this.

michaelscof: 2017-10-29 09:50:26

The easiest one on spoj.just pen and paper needed.

hitesh87: 2017-10-05 13:26:13

easy AC in one go!!!

techventer_936: 2017-09-11 20:03:09

Digits to be subtracted will always be from (1-9). carry on!! :)

dangerous321: 2017-08-27 23:24:10

' If Nikifor wins then in the second line' got wa becoz of this
Easy one

diaaeddin: 2017-08-24 12:23:11

1 2 3 4 5 6 7 8 9 are wining status because he can win in one move
10 is loss status because he have to subtract 1 at least then Trofim wins
11 12 13 14 15 16 17 18 19 are wining status because he can lead Trofim to state 10 which is loss status
and so on.

dark_harry: 2017-07-25 20:49:40

what if the number is 0?

hunnychauhan: 2017-07-22 11:32:04

unable to understand problem clearly yet solved it using sample case :)

Added by:Roman Sol
Time limit:0.620s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZCon 2007