INOI 2003, Sample Question Paper

Related:

Indian National Olympiad in Informatics, 2003

IARCS home > OLYMPIAD > Archives

INOI-2003, Sample questions

Problem 2: Digital rivers

A digital river is a sequence of numbers where the number following n is n plus the sum of its digits. For example, 12345 is followed by 12360 since 1+2+3+4+5 = 15. If the first number of a digital river is k, we call it river k.

For example, river 480 is the sequence beginning {480,492,507,519,...} and river 483 is the sequence beginning {483,498,519,...}.

Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values. For example, river 480 meets river 493 at 519, meets river 507 at 507, and never meets river 481.

It is known that every digital river will eventually meet river 1, river 3 or river 9. Write a program that reads an integer n (1 ≤ n ≤ 16384) and prints out the value where river n first meets one of these three rivers, as well as which of the three rivers it meets at this value (1, 3 or 9).

Sample Input

Sample Output

101 1