Summary
Problems
Problem #1 Count
Description
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
Input Format
输入文件count.in包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1每行一个自然数。
Output Format
输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
Sample Input
8
2
4
2
4
5
100
2
100
Sample Output
2 3
4 2
5 1
100 2
Data Range
40%的数据满足：1<=n<=1000
80%的数据满足：1<=n<=50000
100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）Problem #2 Decode
Description
小s和小t为了打发无聊的数学课经常传小纸条。
但是由于小纸条内容往往是一个secret，为了不让别人偷看到这个secret，小s用了一种编码方式。
对于每个英文的大写字母都找到一个替换的字母。
这样原来的LOVE可能decode之后就变成HATE。
这样传纸条的时候就不用担心secret被泄露了～
Input Format
第一行，一个字符串，长度不超过10000。
只包含大写字母和空格。
第二行，一个长度为26的大写字符串，分别表示A～Z编码后变成什么大写字母。
Output Format
一行，一个字符串，表示输入文件的第一行字符串编码后的字符串。
Sample Input
HPC PJVYMIY
BLMRGJIASOPZEFDCKWYHUNXQTV
Sample Output
ACM CONTEST
Problem #3 Gap
Description
小s对素数的研究慢慢朝着炉火纯青的地步发展，在研究完素数本身之后，小s开始研究起了素数之间的gap。
对于素数2，3，5，7，11，13，17，素数之间的间距分别为1，2，2，4，2，4。
每个合数都处于某一个素数gap中，比如合数15处于间距为4的素数gap。
现在小s想知道，对于一个正整数N，它处于的素数gap的间距是多少。
Input Format
一行，一个正整数N
Output Format
一行，一个整数K，表示N所在的素数gap的间距。
若N本身为一个素数，输出0
Sample Input
10
Sample Output
4
Data Range
20%的数据满足：1<=n<=100
40%的数据满足：1<=n<=1000
100%的数据满足：1<=n<=1,000,000
Problem #4 Palin
Description
大家都知道回文串吧～简单地说就是左右对称的一个串，比如abcba,werrew。
小s对回文串的研究已经够深刻了，现在她转而研究其他方面的回文，比如，数的回文拆分。
对于自然数的拆分，就是把一个自然数N用若干个整数之和表示。
比如15=1+2+3+4+5=1+2+1+7+1+2+1。
那么怎样的拆分才算是回文的呢？我们用从归纳的角度来定义数的回文拆分。
首先一个数A=A是一个回文拆分。
其次，一个自然数N=A+A 或是N=A+x+A，其中A 是一个回文拆分，x 是任意一个自然数，这两种也是回文拆分。
举个例子，7的所有回文拆分有7,1+5+1,2+3+2,1+1+3+1+1,3+1+3,1+1+1+1+1+1+1。
现在小s想知道，一个正整数N的回文拆分到底有多少种。
由于这个数字可能很大，小s只需要你告诉她答案mod 1,000,000,007的值。
Input Format
一行，一个正整数N
Output Format
一行，一个整数M，为N的回文拆分数mod 1,000,000,007的值
Sample Input
4
Sample Output
4
Data Range
30%的数据满足：1<=n<=20
100%的数据满足：1<=n<=1,000
Problem #5 Self-Number
Description
在1949年印度数学家D. R. Daprekar发现了一类称作Self-Numbers的数。
对于每一个正整数n，我们定义d(n)为n加上它每一位数字的和。
例如，d(75)=75+7+5=87。
给定任意正整数n作为一个起点，都能构造出一个无限递增的序列：n, d(n), d(d(n)), d(d(d(n))), . . . 例如，如果你从33开始，下一个数是33+3+3=39，再下一个为39+3+9=51，再再下一个为51+5+1=57，因此你所产生的序列就像这样：33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, . . . 数字n被称作d(n)的发生器。
在上面的这个序列中，33是39的发生器，39是51的发生器，51是57的发生器等等。
有一些数有超过一个发生器，如101的发生器可以使91和100。
一个没有发生器的数被称作Self-Number。
如前13个Self-Number为1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97。
我们将第i个Self-Number表示为a[i]，所以a[1]=1, a[2]=3, a[3]=5. . .
Input Format
输入包含整数N、K、s1. . . sk，其中1<=N<=107，1<=K<=5000，以空格和换行分割。
Output Format
在第一行你需要输出一个数，这个数表示在闭区间[1, N]中Self-Number的数量。
第二行必须包含以空格划分的K个数，表示a[s1]. . a[sk]，这里保证所有的a[s1]. . a[sk]都小于N。
（例如，如果N=100，sk可以为1-13，但不能为14，因为a[14]=108>100）
Sample Input
100 10
1 2 3 4 5 6 7 11 12 13
Sample Output
13
1 3 5 7 9 20 31 75 86 97。