Pascal国庆测试题.docVIP

2010年国庆测试题 题目名称 统计数字 Self-Number 多米诺骨count sn dom 输入文件 count.in sn.in dom.in 输出文件 count.out sn.out dom.out 时间限制 1s 1s 1s 内存限制 64M 64M 64M 1．统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了n个自然数，每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 【输入】 输入文件count.in包含n+1行; 第l行是整数n，表示自然数的个数。 第2~n+l行每行一个自然数。 【输出】 输出文件count.out包含m行(m为n个自然数中不相同数的个数)，按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 【输入输出样例】 count.in count.out 8 2 4 2 4 5 100 2 100 2 3 4 2 5 1 100 2 【限制】 40％的数据满足：1=n=1000 80％的数据满足：1=n=50000 100％的数据满足：1=n=200000，每个数均不超过l 500 000 000(1.5*109) 2、Self-Number (sn.pas/c/cpp) 【问题描述】 在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. . . 【输入格式】 输入包含整数N、K、s1. . . sk，其中1=N=107，1=K=5000，以空格和换行分割。 【输出格式】 在第一行你需要输出一个数，这个数表示在闭区间[1, N]中Self-Number的数量。第二行必须包含以空格划分的K个数，表示a[s1]. . a[sk]，这里保证所有的a[s1]. . a[sk]都小于N。（例如，如果N=100，sk可以为1-13，但不能为14，因为a[14]=108100）? 【样例输入】 100 10 1 2 3 4 5 6 7 11 12 13? 【样例输出】 13 1 3 5 7 9 20 31 75 86 97 3、多米诺骨 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 上方块中点数之和记为，下方块中点数之和记为，它们的差为。例如在图8-1中，=6+1+1+1=9，=1+5+3+2=11，=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。 编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。 对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。 【输入】 输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。 【输出】 输出文件仅一行，包含一个整数。表示求得的最小旋转次数。 【样例】 dom.in dom.out 4 1 6 1 1 5 1 3 1 2