【UVALive】2037 - Digital Rivers（找规律，暴力）

点击打开题目

2037 - Digital Rivers

Time limit: 3.000 seconds

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

Every digital river will eventually meet river 1, river 3 or river 9. Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n(1

n

16384). A test case wit h value of 0 for n terminates the input and this test case must not be processed.

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line ``first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9). If river n meets river x at y for more than one value of x, output the lowest value.

Print a blank line between two consecutive test cases.

Sample Input

86 
12345 
0

Sample Output

Case #1 
first meets river 1 at 101 

Case #2 
first meets river 3 at 12423

首先要找规律，题目给出了，x只能是 1、3、9，那么先看一下1、3、9这几个开始的包括的数有哪些。

1后面的数比较杂，没有什么规律，但是有一个关键的地方：没有3或9的倍数。

3后面的数都是3的倍数，但不是9的倍数。

9后面的数都是9的倍数。

那么就很好找了，把给出的 n 每一位都加起来，先判定是否是9的倍数，是的话 x = 9 ；否则判断是否是3的倍数，是的话 x = 3；否则 x = 1；

然后就往后找数就行了。

代码如下：

#include <cstdio>
int dis(int x)		//计算每一位的和
{
	int sum = 0;
	while (x)
	{
		sum += x % 10;
		x /= 10;
	}
	return sum;
}
int cal(int a,int b)
{
	while (a != b)
	{
		if (a > b)
			b += dis(b);
		else
			a += dis(a);
	}
	return a;
}
int main()
{
	int n;
	int x;
	int ans;
	int num = 1;
	while (~scanf ("%d",&n) && n)
	{
		int sum = dis(n);
		if (num > 1)
			printf ("\n");
		printf ("Case #%d\n",num++);
		if (sum % 9 == 0)
		{
			printf ("first meets river 9 at ");
			ans = cal(n , 9);
		}
		else if (sum % 3 == 0)
		{
			printf ("first meets river 3 at ");
			ans = cal(n , 3);
		}
		else
		{
			printf ("first meets river 1 at ");
			ans = cal(n , 1);
		}
		printf ("%d\n",ans);
	}
	return 0;
}