算法与程序实践1（简单计算）

目 录

CS1：斐波那契数列 ......................................................................................................................... 1 CS2：正整数解 ................................................................................................................................. 3 CS3：鸡兔同笼 ................................................................................................................................. 4 CS4：棋盘上的距离 ......................................................................................................................... 5 CS5：校门外的树木 ......................................................................................................................... 7 CS6：填词......................................................................................................................................... 8 CS7：装箱问题 ................................................................................................................................. 9 CS8：求平均年龄 ........................................................................................................................... 10 CS9：数字求和 ............................................................................................................................... 11 CS10：两倍..................................................................................................................................... 11 CS11：肿瘤面积 ............................................................................................................................. 12 CS12：肿瘤检测 ............................................................................................................................. 12 CS13：垂直直方图 ......................................................................................................................... 13 CS14：谁拿了最多的奖学金 ......................................................................................................... 14 CS15：简单密码 ............................................................................................................................. 15 CS16：化验诊断 ............................................................................................................................. 16 CS17：密码..................................................................................................................................... 17 CS18：数字阶梯 ............................................................................................................................. 18 CS19：假票..................................................................................................................................... 18 CS20：纸牌（Deck） ..................................................................................................................... 19

《算法与程序实践》习 题 解 答1——简单计算

这一章的主要目的是通过编写一些简单的计算题，熟悉C/C++语言的基本语法。 基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。

课堂练习：CS1、CS2、CS3 课堂讲解：CS4

课后练习：CS4、CS5、CS8、CS9、CS10 课堂上机：CS11、CS18、CS19

课后题：CS6、CS7、CS12、CS13、CS15

CS1：斐波那契数列

问题描述：

已知斐波那契数列第n项的计算公式如下。在计算时有两种算法：递归和非递归，请分别给出这两种算法。

当n=0时，Fib(n)=0，当n=1时，Fib(n)=1，当n>1时，Fib(n)= Fib(n-1)+ Fib(n-2)

输入：

第一行是测试数据的组数m，后面跟着m行输入。每行包括一个项数n和一个正整数a。（m，n，a均大于0，且均小于10000000）

输出：

输出包含m行，每行对应一个输入，若a不大于Fib(n)，则输出Yes，否则输出No

输入样例： 3 3 3 10 50 24 20000

输出样例： No Yes Yes

参考程序1（zzg）： 循环版

#include int main() {

1

int fn2,fn1,fn,m,n,a,i,j; fn2=0; fn1=1; //freopen(\ //freopen(\ scanf(\ for(i=1;i<=m;i++) { scanf(\ if(n==1) { if(a<=fn1) printf(\ else printf(\ } else { for(j=2;j<=n;j++) { fn=fn2+fn1; fn2=fn1; fn1=fn; if(a<=fn) { printf(\ break; } } if(j>n) printf(\ } } return 1; }

递归版（zzg） #include int fib(int n) { if(n<2) return n==0?0:1;

2

else return fib(n-2)+fib(n-1); }

int main() { int m,n,a,i,j; scanf(\ for(i=1;i<=m;i++) { scanf(\ for(j=1;j<=n;j++) { if(a<=fib(j)) { printf(\ break; } } if(j>n) printf(\ } return 1; }

注意事项：

这题主要考察递归与非递归的用法，还有数值越界的情况。 1）测试数据可取一下 1 1和1 3试一下。 2）测试数据可以取一下 50 1000和1000 1000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。

CS2：正整数解

求x2+y2=2000的正整数解，输出所有不同的解。

参考程序：

#include #include

int main() { int x,y,m; m=(int)sqrt(2000);

3

for(x=1;x<=m;x++) for(y=x;y<=m;y++) if(x*x+y*y==2000) printf(\ return 0; }

注意事项：

这题主要考察枚举的用法，还有求平方根（数学函数）的用法。

1） 要考虑x和y可调换，所以需要加上y>=x，这样就能保证不会出现重复的解

2） 考虑一下优化的问题for(y=x;y<=m;y++)可以优化为：for(y=m;y>=x;y--)，甚至还可以 int temp=(int)sqrt(2000-x*x) for(y=temp;y>=x;y--)

CS3：鸡兔同笼

（来源：poj.grids.cn 2750） 问题描述：

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

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

输出：

n 行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 输入样例：

2 3 20 输出样例：

0 0 5 10

参考程序：

#include

int main() {

int nCase,nFeet,i; scanf(\

4

}

for(i=1;i<=nCase;i++) {

scanf(\ if(nFeet%2 != 0) printf(\ else if(nFeet%4 != 0)

printf(\ else

printf(\}

return 0;

解题思路：

这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4，N / 2，如果N不是4的倍数，输出N/4+1，N/2 。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。

注意事项：

这里考察数学计算，出错有一下几种情况：

1） 因为对问题分析不清楚，给出了错误的计算公式；

2） 不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时； 3） 试图把所有输入先存储起来，再输出，开的数组太小，因数组越界产生运行错； 4） 在每行输出末尾缺少换行符；

5） 对输入输出语法不熟悉导致死循环或语法错。

CS4：棋盘上的距离

（来源：poj.grids.cn 1657）

问题描述：国际象棋的棋盘是黑白相间的8 * 8 的方格，棋子放在格子中间。如图1-1 所示：

5

图1-1 国际象棋棋盘

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

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

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

第一行是测试数据的组数t（0 <= t <= 20 ）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用\字母-数字\的形式表示，字母从“a”到“h”，数字从“1” 到“8” 。 输出要求：

对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达，就输出“Inf”。 输入样例 2 a1 c3 f5 f8 输出样例 2 1 2 1 3 1 1 Inf

解题思路

这个问题是给定一个棋盘上的起始位置和终止位置，分别判断王、后、车、象从起始位置到达终止位置需要的步数。首先，王、后、车、象彼此独立，分别考虑就可以了。所以这个题目重点要分析王、后、车、象的行走规则特点，从而推出它们从起点到终点的步数。

6

我们假设起始位置与终止位置在水平方向上的距离是x，它们在竖直方向上的距离是y。 根据王的行走规则，它可以横、直、斜走，每步限走一格，所以需要的步数是min(x,y)+abs(x-y) ，即x，y 中较小的一个加上x 与y 之差的绝对值。

根据后行走的规则，她可以横、直、斜走，每步格数不受限制，所以需要的步数是1（x 等于y 或者 x 等于0 或者 y 等于0）或者2(x不等于y)。

根据车行走的规则，它可以横、竖走，不能斜走，格数不限，需要步数为1 （x 或者y 等于0）或者2（x 和y 都不等于0）。

根据象行走得规则，它可以斜走，格数不限。棋盘上的格点可以分为两类，第一类是它的横坐标和纵坐标之差为奇数，第二类是横纵坐标之差为偶数。对于只能斜走的象，它每走一步，因为横纵坐标增加或减小的绝对值相等，所以横坐标和纵坐标之差的奇偶性无论如何行走都保持不变。因此，上述的第一类点和第二类点不能互相到达。如果判断出起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。如果它们属于同一类点，象从起始点走到终止点需要1（x 的绝对值等于y 的绝对值）或者2（x 的绝对值不等于y 的绝对值）。

CS5：校门外的树木

（来源：poj.grids.cn 2808）

问题描述：

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，??，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 输入：

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

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

输入样例：

500 3 150 300 100 200 470 471

输出样例:

298

7

解题思路

这个问题可以概括为输入一个大的整数闭区间，及一些可能互相重叠的在该大区间内的小的整数闭区间。在大的整数闭区间内去除这些小的整数闭区间，问之后剩下的可能不连续的整数区间内有多少个整数。这个题目给出的范围是大的区间在1~10000以内，要去除的小的区间的个数是100个以内。因为规模较小，所以可以考虑用空间换时间，用一个大数组来模拟这些区间，数组中的每个数表示区间上的一个数。例如，如果输入L的长度是500，则据题意可知最初有501棵树。我们就用一个501个元素的数组来模拟这501棵树，数组的下标分别代表从1到501棵树，数组元素的值代表这棵树是否被一走。最初这些树都没有被移走，所以所有数组元素的值都用true来表示。每当输入一个小区间，就将这个区间对应的树全部移走，即将这个区间对应的数组元素下标指示的元素的值置成false。如果有多个区间对应同一个数组元素，会导致多次将某个数组元素置成false。不过这并不影响结果的正确性。当所有小区间输入完成，我们可以数一下剩下的仍旧为true的元素的个数，就可以得到最后剩下的树的数目。当然如果最开始输入的区间不是500，则我们使用的数组大小就不是500。因为题目给出的上限是10000，所以我们可以定义一个大小是10001个元素的数组，这样对所有输入都是够用的。

思考题：

如果马路长度L的值极大，比如是40亿，以至于无法开设这么大的trees数组，本题该如何解决？

CS6：填词

（来源：poj.grids.cn 2801） 问题描述：

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

每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的（可以由竖直转向水平，反之亦然）。 你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。

如果你还不了解规则，我们可以用一个例子来说明，比如在图1-2中寻找单词BEG和GEE。

E B G G E E E G E 正确

E B G G E E E G E 不正确，(2,2)中的字母E属于两个单词

E B G G E E E G E 不正确，(3,1)和(2,2)中的字母E不相邻

E B G G E E E G E 不正确，(2,2)中的字母E被用了两次

8

图1-2 填词游戏方格盘

输入：

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

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

输出要求

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

3 3 2 EBG GEE EGE BEG GEE 输出样例

EEG

解题思路

题目中给出的条件比较隐晦。输入中给出的字母都是大写字母——表明输出也只能是大写字母。输入保证填词游戏至少有一组答案——这说明我们不必寻找单词所在的位置，只要去掉这些单词所占用的字母就可以了。“神秘单词”中的字母要按照字典序给出——说明我们只要知道“神秘单词”中的字母组成就可以了，在字母组成确定的情况下，按字典序输出的方式只有一种。分析到这里我们发现这其实是个很简单的问题。给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！

可以定义一个有26个元素的数组，分别记录在输入的矩形中，每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0 的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。

CS7：装箱问题

（来源：poj.grids.cn 1017）

问题描述：

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

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用

9

空

格隔开，分别为1*1 至6*6 这六种产品的数量。输入文件将以6 个0 组成的一行结尾。 输出要求：

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

0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 输出样例：

2 1

解题思路：

这个问题描述得比较清楚，我们在这里只解释一下输入输出样例：共有两组有效输入，第一组表示有4个3*3的产品和一个6*6的产品，此时4个3*3的产品占用一个箱子，另外一个6*6的产品占用1个箱子，所以箱子数是2；第二组表示有7个1*1的产品，5个2*2的产品和1个3*3的产品，我们可以把他们统统放在一个箱子中，所以输出是1。

分析六个型号的产品占用箱子的具体情况如下：6*6的产品每个会占用一个完整的箱子，并且没有空余空间；5*5的产品每个占用一个新的箱子，并且留下11个可以盛放1*1的产品的空余空间；4*4的产品每个占用一个新的箱子，并且留下5个可以盛放2*2的产品的空余空间；3*3的产品情况比较复杂，首先3*3 的产品不能放在原来盛有5*5或者4*4的箱子中，那么必须为3*3的产品另开新的箱子，新开的箱子数目等于3*3的产品的数目除以4向上取整；同时我们需要讨论为3*3的产品新开箱子时，剩余的空间可以盛放多少2*2和1*1的产品（这里如果有空间可以盛放2*2的产品，我们就将它计入2*2的空余空间，等到2*2的产品全部装完，如果还有2*2的空间剩余，再将它们转换成1*1的剩余空间）。我们可以分情况讨论为3*3 的产品打开的新箱子中剩余的空位，共为四种情况：第一种，3*3的产品的数目正好是4 的倍数，所以没有空余空间；第二种，3*3的产品数目是4的倍数加1，这时还剩5个2*2的空位和7个1*1的空位；第三种，3*3的产品数目是4的倍数加2，这时还剩3个2*2的空位和6个1*1的空位；第四种，3*3的产品数目是4的倍数加3，这时还剩1个2*2的空位和5个1*1的空位；处理完3*3的产品，就可以比较一下剩余的2*2的空位和2*2产品的数目，如果产品数目多，就将2*2的空位全部填满，再为2* 的产品打开新箱子，同时计算新箱子中1*1 的空位，如果剩余空位多，就将2*2的产品全部填入2*2的空位，再将剩余的2*2的空位转换成1*1的空位；最后处理1*1的产品，比较一下1*1的空位与1*1的产品数目，如果空位多，将1*1的产品全部填入空位，否则，先将1*1的空位填满，然后再为1*1的产品打开新的箱子。

CS8：求平均年龄

（来源：poj.grids.cn 2714） 问题描述：

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

10

输入：

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

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

2 18 17

样例输出：

17.50

提示：

要输出浮点数、双精度数小数点后2位数字，可以用下面这种形式： printf(\

CS9：数字求和

（来源：poj.grids.cn 2796） 问题描述：

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

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

输出一行，给出一个正整数，是5个数中小于a的数的和。 样例输入：

10 1 2 3 4 11 样例输出：

10

CS10：两倍

（来源：poj.grids.cn 2807） 问题描述：

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

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

输入：

11

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

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

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

7 5 11 13 1 3 0 -1

样例输出： 3 2 0

CS11：肿瘤面积

（来源：poj.grids.cn 2713） 问题描述：

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

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

输出一行，该行包含一个整数，为要求的肿瘤内的像素点的个数。 样例输入： 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 样例输出：

1

CS12：肿瘤检测

（来源：poj.grids.cn 2677） 问题描述：

12

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

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

输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。 样例输入： 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 样例输出：

9 8

CS13：垂直直方图

（来源：poj.grids.cn 2800） 问题描述：

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

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

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

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

样例输出：

13

* * * *

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

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 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

CS14：谁拿了最多的奖学金

（来源：poj.grids.cn 2715） 问题描述：

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；

2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；

3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得；

4) 西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

输入：

输入的第一行是一个整数N（1 <= N <= 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。 输出：

输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。 样例输入：

14

4

YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 样例输出： ChenRuiyi 9000 28700

CS15：简单密码

（来源：poj.grids.cn 2767） 问题描述：

Julius Caesar曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。比如字符A用F来代替。如下是密文和明文中字符的对应关系。 密文

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 明文

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

你的任务是对给定的密文进行解密得到明文。

你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。 输入：

输入中的测试数据不超过100组。每组数据都有如下的形式，而且各组测试数据之间没有空白的行。

一组测试数据包括三部分

起始行 - 一行，包括字符串 \

密文 - 一行，给出密文，密文不为空，而且其中的字符数不超过200 结束行 - 一行，包括字符串 \

在最后一组测试数据之后有一行，包括字符串 \。

输出：

对每组数据，都有一行输出，给出密文对应的明文。 样例输入： START

NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START

N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ

15

END START

IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END

ENDOFINPUT 样例输出：

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

CS16：化验诊断

（来源：poj.grids.cn 2680） 问题描述：

下表是进行血常规检验的正常值参考范围，及化验值异常的临床意义：

给定一张化验单，判断其所有指标是否正常，如果不正常，统计有几项不正常。化验单上的值必须严格落在正常参考值范围内，才算是正常。正常参考值范围包括边界，即落在边界上也算正常。 输入：

输出：

16

对于每组测试数据，输出一行。如果所有检验项目正常，则输出：normal；否则输出不正常的项的数目。 样例输入：

2

female 4.5 4.0 115 37 200 male 3.9 3.5 155 36 301

样例输出：

normal 3

CS17：密码

（来源：poj.grids.cn 2818） 问题描述：

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

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

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

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

10

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

样例输出：

BolHeol b C RCE

17

CS18：数字阶梯

（来源：POJ 1663 ZOJ 1414） 问题描述：

从坐标（0,0）出发，在平面上写下所有非负整数0,1,2，?，如图1-3所示，例如1、2和3分别是在（1,1）、（2,0）和（3,1）坐标处写下的。

图1-3 数字阶梯

编写一个程序，给定坐标（x,y），输出对应的整数（如果存在的话），输入文件中的x，y坐标范围都是0~5000。 输入：

输入文件的第一行为正整数N，表示输入文件中测试数据的数目。接下来是N个测试数据，每个测试数据占一行，包含两个整数：x和y，代表平面上的坐标（x，y）。 输出：

对输入文件中每一行所表示的坐标点，输出在该点的非负整数，如果没有对应整数，输出“No Number”。 样例输入： 3 4 2 6 6 3 4 样例输出： 6 12

No Number

CS19：假票

（来源：ZOJ 1514） 问题描述：

在你们学校的舞会中会收到很多假票，要求编写程序，统计所有门票中存在假票的门票数。 输入：

18

输入文件中包含多个测试数据，每个测试数据占两行。第1行为两个整数N和M，分别表示发放门票的张数和参加晚会的人数 (1 <= N <= 10000 and 1 <= M <= 20000)。第2行为M个整数Ti ，为收到的M张门票的号码(1 <= Ti <= N)。输入文件最后一行为0 0，代表输入结束。 输出： 对每个输入测试数据，输出一行，为一个整数，表示收上来的门票中有多少张票被伪造过。

样例输入：

5 5

3 3 1 2 4 6 10

6 1 3 6 6 4 2 3 1 2 0 0 样例输出： 1 4

CS20：纸牌（Deck）

（来源：POJ 1607 ZOJ 1216） 问题描述：

一张扑克牌可以放置在桌子的边缘，只要伸出桌子边缘的长度不超过整张牌长度的一半即可。n张牌叠起来放在桌子的边缘，其最长可伸出桌子边缘的长度为1/2+1/4+??+1/(2*n)，输入n，按照题目要求的格式输出n张牌可伸出桌子边缘的最大 。

输入：

输入文件包括多个测试数据，每个测试数据占一行，为一个非负整数。每个整数都是小于99999的。 输出：

输出首先包含一个标题，即首先输出下面一行： Cards Overhang

（Cards和Overhang间有两个空格）

对输入文件中的每个测试数据，首先输出牌的数目n，然后在输出n张牌最长可伸出桌子边缘的长度，保留小数点后3位有效数字，小数点前至少有一位数。牌的数目右对齐到第5列，长度中的小数点对齐到第12列。 样例输入： 1 2 3 4 30

样例输出：

Cards Overhang

19

1 0.500 2 0.750 3 0.917 4 1.042 30 1.997

20

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