UESTC 1639 Fruit Ninja （想法题）

UESTC 1639 Fruit Ninja （想法题）2014-07-08 synapse7 http://www.acm.uestc.edu.cn/problem.php？pid=1639

思路：

这道题目的突破口在于以下两点：

1. m,n都很小：1 <= m, n<= 50

2. 所有数都相同的几率非常小，尤其在分数很大的时候。换句话说，获得额外奖分n的情况很少。

据此，优先分析获得额外奖分m的情况，也就是当得分是5的倍数的时候。

我们从导致INF的情况入手：

1. 当m是10的倍数时，可以无穷地加下去（因为末尾为0，所有数不可能都相同）,。

2. 当m不是10的倍数，但是是5的倍数时，“几乎”可以无限加，但是有限制。例如当分数加到55555时，需要额外加一个n，这可能会导致结果不再是5的倍数。但若n也是5的倍数，则不会出现这种问题。

现在考虑在某一分数终止的情况：

1. 当m不是10的倍数，但是是5的倍数，且n不是5的倍数时，可能卡住的点出现在55555,555555,5555555,……

设初始分数为5a，则当5a＋k*m = 555...55时会被卡住，即a+k*（m/5）＝ 111...11。所以可以通过选择a可以让分数尽量避免终止在较小的数上。

由于m<=50，考虑m=5,15,25,35,45。

m ＝ 5，m/5=1，必终止在55555，结果55555＋m+n

m ＝ 15，m/5＝3，对等式a+3k=111...11两边模3，即a%3=2,0,1,2,0,1,……。我们可以选择a%3=1的a，这时会终止在7个1这里，因此结果是5555555+m+n

m ＝ 25，m/5＝5，对等式a+5k=111...11两边模5，即a%5=1，选择a%5≠1的a就不会终止了，结果为INF。

m ＝ 35，m/5＝7，对等式a+7k=111...11两边模7，即a%7=2,0,1,4,6,5,2,0,1,4,……，选择a%7=3的a就不会终止了，结果为INF。m ＝ 45，m/5＝9，对等式a+9k=111...11两边模9，即a%9=5,6,7,8,0,1,2,3,4,5,6,7,……，选择a%9=4的a，这时会终止在13个1这里，因此结果是5555555555555+m+n 2. 当m,n均不是上述情况时，最大情况就是max（9999+n+（（9999+n）%5？0:m）, 10000+m）了，相信大家都能看懂这句话的含义。

完整代码：

01./*0ms,856KB*/02.03.#include<cstdio>04.05.int main（）06.{07.int T, n, m, cas = 1, max;08.scanf（"%d", &T）;09.for （; cas <= T; ++cas）10.{11.printf（"Case #%d: ", cas）;12.scanf（"%d%d", &m, &n）;13.if （（m % 10） == 0） puts（"INF"）;14.else if （（m % 5） == 0）15.{16.if （（n % 5） == 0） puts（"INF"）;17.else18.{19.switch （m）20.{21.case 5: printf（"%lld
", 55555LL + n + m）; break;22.case 15: printf（"%lld
", 5555555LL + n + m）; break;23.case 25: case 35: puts（"INF"）; break;24.case 45: printf（"%lld
", 5555555555555LL + n + m）;25.}26.}27.}28.else29.{30.max = 9999 + n;31.if （max % 5 == 0） max += m;32.if （10000 + m > max） max = 10000 + m;33.printf（"%d
", max）;34.}35.}36.return 0;37.}