Skip to content

UKSPC Practice Problems » Rivers Are Meeting

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, and 12345 + 15 = 12360. The next number in this sequence is 12372, because 12360 + 1 + 2 + 3 + 6 + 0 = 12372. If the first number of a digital river is k we will call it river k.

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 483 at 519, meets river 507 at 507, and never meets river 481.

It can be proven that every digital river will eventually meet river 1, river 3 or river 9. Write a program which inputs a single integer n (1≤n≤16384) and outputs the value where river n first meets one of these three rivers.

Sample Input

86

Sample Output

River 86 first meets river 1 at 101

Sample Input

1

Sample Output

River 1 first meets river 1 at 1

Sample Input

900

Sample Output

River 900 first meets river 9 at 909