程序设计竞赛练习题

徐州师范大学 程序设计竞赛 练习题

徐州师范大学 程序设计竞赛练习题

2012-2-9酆格斐

练习1 A+B Problem Description

Calculate a + b Input

Two integer a,b (0 ≤ a,b ≤ 10) Output

Output a + b Sample Input

1 2 Sample Output

3 练习2 肿瘤面积 Time Limit:1000MS Memory Limit:65536K Description

在一个正方形的灰度图片上，肿瘤是一块矩形的区域，肿瘤的边缘所在的像素点在图片中用0表示。其它肿瘤内和肿瘤外的点都用255表示。现在要求你编写一个程序，计算肿瘤内部的像素点的个数（不包括肿瘤边缘上的点）。已知肿瘤的边缘平行于图像的边缘。 Input

只有一个测试样例。第一行有一个整数n，表示正方形图像的边长。其后n行每行有n个整数，取值为0或255。整数之间用一个空格隔开。已知n不大于1000。 Output

输出一行，该行包含一个整数，为要求的肿瘤内的像素点的个数。 Sample Input

5

255 255 255 255 255 255 0 0 0 255 255 0 255 0 255 255 0 0 0 255

255 255 255 255 255 Sample Output

1 Hint

如果使用静态数组来表示图片数据，需要将该数组定义成全局变量。

poj.grids.cn 2713 poj.grids.cn 1000 1

徐州师范大学 程序设计竞赛 练习题

练习3 求平均年龄 poj.grids.cn 2714 Time Limit:1000MS Memory Limit:65536K Description

班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。 Input

第一行有一个整数n（1<= n <= 100），表示学生的人数。其后n行每行有1个整数，取值为15到25。 Output

输出一行，该行包含一个浮点数，为要求的平均年龄，保留到小数点后两位。 Sample Input

2 18 17 Sample Output

17.50

Hint

要输出浮点数、双精度数小数点后2位数字，可以用下面这种形式： printf(\ 练习4 数字求和 Time Limit:3000MS Memory Limit:65536K Description

给定一个正整数a，以及另外的5个正整数，问题是：这5个整数中，小于a的整数的和是多少？ Input

输入一行，只包括6个小于100的正整数，其中第一个正整数就是a。 Output

输出一行，给出一个正整数，是5个数中小于a的数的和。 Sample Input

10 1 2 3 4 11 Sample Output

10 练习5 两倍 Time Limit:1000MS Memory Limit:65536K Description

给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。

比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。

2

poj.grids.cn 2807 poj.grids.cn 2796 徐州师范大学 程序设计竞赛 练习题

Input

输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。 Output

对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。 Sample Input

1 4 3 2 9 7 18 22 0 2 4 8 10 0

7 5 11 13 1 3 0 -1 Sample Output

3 2 0 练习6 鸡兔同笼 Time Limit:1000MS Memory Limit:65536K Description

一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物 Input

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a < 32768) Output

输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开 如果没有满足要求的答案，则输出两个0。 Sample Input

2 3 20 Sample Output

0 0 5 10 练习7 棋盘上的距离 Time Limit:1000MS Memory Limit:10000K Description

国际象棋的棋盘是黑白相间的8 * 8的方格，棋子放在格子中间。如下图所示：

poj.grids.cn 1657 poj.grids.cn 2750 3

徐州师范大学 程序设计竞赛 练习题

王、后、车、象的走子规则如下：

王：横、直、斜都可以走，但每步限走一格。 后：横、直、斜都可以走，每步格数不受限制。 车：横、竖均可以走，不能斜走，格数不限。 象：只能斜走，格数不限。

写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。 Input

第一行是测试数据的组数t（0 <= t <= 20）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用\字母-数字\的形式表示，字母从\到\，数字从\到\。 Output

对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达,就输出\

Sample Input

2

a1 c3 f5 f8 Sample Output

2 1 2 1 3 1 1 Inf 练习8 校门外的树 Time Limit:1000MS Memory Limit:65536K Description

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每

4

poj.grids.cn 2808 徐州师范大学 程序设计竞赛 练习题

个整数点，即0，1，2，……，L，都种有一棵树。

马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 Input

输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 Output

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。 Sample Input

500 3 150 300 100 200 470 471 Sample Output

298 练习9 填词 Time Limit:1000MS Memory Limit:65536K Description

Alex喜欢填词游戏。填词是游戏是一个非常简单的游戏。填词游戏包括一个N * M大小的矩形方格盘和P个单词。玩家需要把每个方格中填上一个字母使得每个单词都能在方格盘上找到。每个单词都能找到要满足下面的条件：

每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的。

你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。

如果你还不了解规则，我们可以具一个例子，比如在下图中寻找单词BEG和GEE。

poj.grids.cn 2801

Input

输入的第一行包括三个整数N，M和P (2 <= M, N <= 10, 0 <= P <=100)。接下来的N行，每行包括M个字符，来表示方格盘。接下来P行给出需要在方格盘中找到的单词。

输入保证填词游戏至少有一组答案。 输入中给出的字母都是大写字母。 Output

5

徐州师范大学 程序设计竞赛 练习题

输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。 Sample Input

3 3 2 EBG GEE EGE BEG GEE Sample Output

EEG 练习10 装箱问题 Time Limit:1000MS Memory Limit:10000K Description

一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。 Input

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开，分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。 Output

除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。 Sample Input

0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 Sample Output

2 1 练习11 肿瘤检测 Time Limit:1000MS Memory Limit:65536K Description

一张CT扫描的灰度图像可以用一个N*N（0

6

poj.grids.cn 2677 poj.grids.cn 1017 徐州师范大学 程序设计竞赛 练习题

要求计算其中的肿瘤的面积和周长。 Input

输入第一行包含一个正整数N（0

输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。 Sample Input

6

99 99 99 99 99 99 99 99 99 50 99 99 99 99 49 49 50 51 99 50 20 25 52 99 40 50 99 99 99 99 99 99 99 99 99 99 Sample Output

9 8 练习12 垂直直方图 Time Limit:1000MS Memory Limit:65536K Description

输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注意：只用输出字符的出现次数，不用输出空白字符，数字或者标点符号的输出次数。 Input

输入包括4行由大写字母组成的文本，每行上字符的数目不超过80个。 Output

输出包括若干行。其中最后一行给出26个大写英文字母，这些字母之间用空格隔开。前面的几行包括空格和星号，每个字母出现几次，就在这个字母的上方输出一个星号。注意：输出的第一行不能是空行。 Sample Input

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG. THIS IS AN EXAMPLE TO TEST FOR YOUR HISTOGRAM PROGRAM. HELLO! Sample Output

* * * *

* * * * * * * * * * * * * * * * * * * * * * * *

7

poj.grids.cn 2800 徐州师范大学 程序设计竞赛 练习题

* * * * * * * * * * * * *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 练习13 Ugly Numbers Time Limit: 1000MS Memory Limit: 10000K Description

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

shows the first 10 ugly numbers. By convention, 1 is included.

Given the integer n,write a program to find and print the n'th ugly number. Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0. Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0. Sample Input

1 2 9 0 Sample Output

1 2 10 练习14 密码 Time Limit:1000MS Memory Limit:65536K Description

Bob 和 Alice 开始使用一种全新的编码系统。它是一种基于一组私有钥匙的。他们选择了n个不同的数a1 ， . . .，an, 它们都大于0小于等于n。 机密过程如下：待加密的信息放置在这组加密钥匙下，信息中的字符和密钥中的数字一一对应起来。信息中位于i位置的字母将被写到加密信息的第ai个位置, ai 是位于i位置的密钥。加密信息如此反复加密，一共加密 k 次。

信息长度小于等于n。如果信息比 n 短, 后面的位置用空格填补直到信息长度为n。 请你帮助 Alice 和 Bob 写一个程序，读入密钥，然后读入加密次数 k 和要加密的信息，按加密规则将信息加密。 Input

输入包括几块。每块第一行有一个数字n, 0 < n <= 200. 接下来的行包含n个不同的数字。数字都是大于0小于等于n的。下面每行包含一个k和一个信息字符串，它们之间用空格格开。每行以换行符结束，换行符不是要加密的信息。每个块的最后一行只有一个0。 最

8

poj.grids.cn 2818 poj.grids.cn 1338 徐州师范大学 程序设计竞赛 练习题

后一个块后有一行，该行只有一个0。 Output

输出有多个块，每个块对应一个输入块。每个块包含输入中的信息经过加密后的字符串，顺序与输入顺序相同。所有加密后的字符串的长度都是 n。 每一个块后有一个空行。 Sample Input

10

4 5 3 7 2 8 1 6 10 9 1 Hello Bob 1995 CERC 0 0 Sample Output

BolHeol b C RCE 练习15 数字平方和 求所有满足如下条件的三位数：它除以11得的商等于它各位数字的平方和。例如550，除以11商为50，52+52+02=50 #include int main(int argc, char *argv[]) { int i, j, n, s; for(i=100;i<=999;i++) { n = i; j = n / 11; s = 0; while(_____A_____) { _____B_____; n /= 10; } if(j==s) printf(\ } return 0; } 练习16 立方和 求所有这样的三位数，这些三位数等于它各位数字的立方和。例如，153=13+53+33。

9

徐州师范大学 程序设计竞赛 练习题

练习17 最小自然数 求具有下列两个性质的最小自然数n： 1．n的个位数是6；

2．若将n的个位数移到其余各位数字之前，所得的新数是n的4倍。 练习18 倒序数 寻找160以内的素数，它的倒序数（如123的倒序数为321）、数码和、数码积不是素数便是1。 练习19 完全平方数 寻找具有完全平方数，且不超过7位数码的回文数。所谓回文数是指这样的数，它的各位数码是左右对称的，例如121，676，94249等。（完全平方数是指可以写成某个整数的平方的数，即其平方根为整数的数。例如，9 = 3 × 3，它是一个完全平方数。） 练习20 等差素数 寻找6个成等差级数且小于160的素数。 练习21 排列70项数 取{2m, 3n | m>=1, n>=1}中由小到大排列的前70项数。 练习22 循环数 Time Limit:1000MS Memory Limit:10000K Description

n 位的一个整数是循环数（cyclic）的条件是：当用一个 1 到 n 之间的整数去乘它时, 会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说，如果把原来的数字和新的数字都首尾相接，他们得到的环是相同的。只是两个数的起始数字不一定相同。例如，数字 142857 是循环数，因为:

142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 Input

写一个程序确定给定的数是否是循环数。输入包括多个长度为 2 位到 60 位的整数。(注意，先导的0也是合理的输入不应该被忽略,例如 \是 2 位数，\是 1 位数。) Output

对于每一个输入的整数，输出一行表明它是否是循环数。

10

poj.grids.cn 1047，2952

徐州师范大学 程序设计竞赛 练习题

练习34 散列表插入 本题是对散列表进行插入的算法，采用结合的同义词链表解决冲突。函数HASH是散列函数，散列表的长度为LEN，nf为一外部变量，用来寻找空的单元，其初始值为LEN-1。 #define LEN 51 typedef struct { char ww[5]; int next; }element; element table[LEN]; char key[5]; void HASH_INSERT(char *k) { int i; i = HASH(k); if(!strcmp(table[i].ww, \ { strcpy(table[i].ww, k); table[i].next = -1; } else { while((table[i].next != -1) && strcmp(table[i].ww, k)) _____A_____; if(!strcmp(table[i].ww, k)) printf(\ else { while(strcmp(table[nf].ww, \ _____B_____; if(nf < 0) printf(\ else { _____C_____; strcpy(table[nf].ww, k); _____D_____; } } } } 21

徐州师范大学 程序设计竞赛 练习题

练习35 确定进制 poj.grids.cn 2972 Time Limit:1000MS Memory Limit:65536K Description

6*9 = 42 对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13) * 9(13) = 42(13)， 而 42(13) = 4 * 131 + 2 * 130 = 54(10)。 你的任务是写一段程序读入三个整数p、q和 r，然后确定一个进制 B(2<=B<=16) 使得 p * q = r. 如果 B有很多选择, 输出最小的一个。例如： p = 11, q = 11, r = 121. 则有 11(3) * 11(3) = 121(3) 因为 11(3) = 1 * 31 + 1 * 30 = 4(10) 和 121(3) = 1 * 32 + 2 * 31 + 1 * 30 = 16(10)。 对于进制 10,有 11(10) * 11(10) = 121(10)。这种情况下，应该输出 3。如果没有合适的进制，则输出 0。 Input

输入有 T组测试样例。 T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。 p、q、r的所有位都是数字，并且1 <= p、q、r <= 1,000,000。 Output

对于每个测试样例输出一行。该行包含一个整数：即使得p * q = r成立的最小的B。如果没有合适的B，则输出 0。 Sample Input

3

6 9 42 11 11 121 2 2 2 Sample Output

13 3 0 练习36 skew数 Time Limit:1000MS Memory Limit:65536K Description

在 skew binary表示中, 第 k 位的值xk表示xk*(2k+1-1)。 每个位上的可能数字是0 或 1，最后面一个非零位可以是2, 例如, 10120(skew) = 1*(25-1) + 0*(24-1) + 1*(23-1) + 2*(22-1) + 0*(21-1) = 31 + 0 + 7 + 6 + 0 = 44. 前十个skew数是 0、1、2、10、11、12、20、100、101、以及102。 Input

输入包含一行或多行，每行包含一个整数n。 如果 n = 0 表示输入结束，否则n是一个skew 数 Output

对于每一个输入，输出它的十进制表示。转换成十进制后， n 不超过 231-1 = 2147483647 Sample Input 10120

200000000000000000000000000000 10

22

poj.grids.cn 2973 徐州师范大学 程序设计竞赛 练习题

1000000000000000000000000000000 11 100

11111000001110000101101102000 0

Sample Output 44

2147483646 3

2147483647 4 7

1041110737 练习37 判断闰年 Time Limit:1000MS Memory Limit:65536K Description

判断某年是否是闰年。 Input

输入只有一行，包含一个整数a(0 < a < 3000) Output

一行，如果公元a年是闰年输出Y，否则输出N Sample Input

2006 Sample Output

N

Hint

公历纪年法中，能被4整除的大多是闰年，但能被100整除而不能被400整除的年份不是闰年， 能被3200整除的也不是闰年，如1900年是平年，2000年是闰年，3200年不是闰年。 练习38 细菌繁殖 Time Limit:1000MS Memory Limit:65536K Description

一种细菌的繁殖速度是每天成倍增长。例如：第一天有10个，第二天就变成20个，第三天变成40个，第四天变成80个，??。现在给出第一天的日期和细菌数目，要你写程序求出到某一天的时候，细菌的数目。 Input

第一行有一个整数n，表示测试数据的数目。其后n行每行有5个整数，整数之间用一个空格隔开。第一个数表示第一天的月份，第二个数表示第一天的日期，第三个数表示第一天细菌的数目，第四个数表示要求的那一天的月份，第五个数表示要求的那一天的日期。已知第一天和要求的一天在同一年并且该年不是闰年，要求的一天一定在第一天之后。数据保

23

poj.grids.cn 2712 poj.grids.cn 2733 徐州师范大学 程序设计竞赛 练习题

证要求的一天的细菌数目在长整数（long）范围内。 Output

对于每一组测试数据，输出一行，该行包含一个整数，为要求的一天的细菌数。 Sample Input

2

1 1 1 1 2 2 28 10 3 2 Sample Output

2 40 练习39 日历问题 Time Limit:1000MS Memory Limit:65536K Description

在我们现在使用的日历中, 闰年被定义为能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它们不是闰年。例如：1700, 1800, 1900 和 2100 不是闰年，而 1600, 2000 和 2400是闰年。 给定从公元2000年1月1日开始逝去的天数，你的任务是给出这一天是哪年哪月哪日星期几。 Input

输入包含若干行，每行包含一个正整数，表示从2000年1月1日开始逝去的天数。输入最后一行是?1, 不必处理。可以假设结果的年份不会超过9999。 Output

对每个测试样例，输出一行，该行包含对应的日期和星期几。格式为“YYYY-MM-DD DayOfWeek”, 其中 “DayOfWeek” 必须是下面中的一个： \\或 \“。 Sample Input

1730 1740 1750 1751 -1 Sample Output

2004-09-26 Sunday 2004-10-06 Wednesday 2004-10-16 Saturday 2004-10-17 Sunday Hint

2000.1.1. 是星期六 练习40 八进制小数 Time Limit:1000MS Memory Limit:65536K Description

24

poj.grids.cn 2765 poj.grids.cn 2964 徐州师范大学 程序设计竞赛 练习题

八进制小数可以用十进制小数精确的表示。比如，八进制里面的0.75等于十进制里面的0.963125 (7/8 + 5/64)。所有小数点后位数为n的八进制小数都可以表示成小数点后位数不多于3n的十进制小数。

你的任务是写一个程序，把(0, 1)中的八进制小数转化成十进制小数。 Input

输入包括若干八进制小数，每个小数占用一行。每个小数的形式是0.d1d2d3 ... dk，这里di是八进制数0...7，而且已知0 < k < 15。 Output

对于每个输入的八进制小数，输入如下形式的一行 0.d1d2d3 ... dk [8] = 0.D1D2D3 ... Dm [10]

这里左边是输入的八进制小数，右边是相等的十进制小数。输出的小数末尾不能有0，也就是说Dm不等于0。 Sample Input

0.75 0.0001

0.01234567 Sample Output

0.75 [8] = 0.953125 [10]

0.0001 [8] = 0.000244140625 [10]

0.01234567 [8] = 0.020408093929290771484375 [10] Hint

如果你使用字符串读取八进制小数，你可以使用如下的形式中止输入 char octal[100];

while(cin >> octal) { ... } 练习41 acm.pku.edu.cn 3191 The Moronic Cowmpouter Time Limit: 1000MS Memory Limit: 65536K Description

Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it's a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base ?2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base ?2, the place values are 1, ?2, 4, ?8, 16, ?32, ... (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1's and 0's but no sign. Consider counting from ?1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000..2,000,000,000) to their counterpart representation in base ?2. Input

Line 1: A single integer to be converted to base ?2

25

本文来源：https://www.bwwdw.com/article/vaqf.html