第二届程序设计大赛题目

1 数字的游戏

输入文件名：gaspar.in 输出文件名：estdout.pc2

问题描述：

N个教徒和N个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是他们想了一个办法：2N个人围成一圈，从第一个人开始依次循环报数，每数到第9个人就将他扔进大海，如此循环直到只剩下N个人为止。问怎样的站法，才能使得每次投入大海的都是非教徒。

输入：

输入文件由一行构成，就是N的值 输出：

输出文件是一行字符串，字符串由N个'@'字符（代表教徒）和N个'+'字符（代表非教徒）排列组成。该排列使得按照提述方法每次投入大海的都是非教徒。

输入样本：

15

输出样本：

@@@@+++++@@+@@@+@++@@+++@++@@+

2 翻译

输入文件：trans.in 输出文件：estdout.pc2

问题描述：

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个软件的原理很简单，他只是从头到尾，一次将每个单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它来翻译；如果内存中没有，软件就会在外存中的词典里查找，查出单词的中文含义然后翻译，并将这个单词和含义放入内存，以备后续查找和翻译。

假设内存中有M个单元，每个单元能存放一个单词和含义。每当软件将一个新单词存入内存前，如果当前内存中已经存入的单词数不超过M，软件会将新单词存入下一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章长度为N个单词，给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入：

多组数据，每组数据共2行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M和N（0

第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

当M=N=0时输入数据结束。 输出：

每组数据占一行，分别包含一个整数，为软件需要查词典的次数。

输入样本： 3 7

1 2 1 5 4 4 1 2 10

8 824 11 78 11 78 11 78 8 264 0 0

输出样本： 5 6

3 自然数的计算

输入文件：natrual.in 输出文件：estdout.pc2 问题描述：

我们要求找出具有以下性质的数的个数（包含输入的自然数本身） 先输入一个自然数n（n<=1000），然后对此自然数进行如下操作：

1.不作任何操作

2.在他左边加上一个自然数，但该自然数不能超过原数最高位数字的一半

3.加上数之后，继续按此规则进行处理，直到不能再加自然数为止

输入：

第一行一个数t，表示有t组数据输入 之后每组数据占一行，每行一个自然数n

输出：

每组数据占一行，一个数，表示满足条件的数的个数

输入样本： 1 6

输出样本： 6

4. 自动纠正拼写错误

输入文件：auto.in 输出文件：estdout.pc2

问题描述：

某些文件编辑器提供纠正英文单词拼写错误的功能。你们本次要解决的问题就是实现这样一个能够完成自动纠正拼写错误（ACM）功能的应用程序。

ACM能够纠正以下几类的单词拼写错误：

1.漏写或多写1个字母，例如单词“letter”被写成了“leter”，或者是“letter”被写成了“lettter”。

2.写错了一个字母，例如“letter”被写成了“ketter”。

3.两个相邻的字母书写顺序弄错了，例如“letter”被写成了“lettre”。 ACM的纠错功能是基于一个已知单词集的字典来进行的。每当一个文档中含有字典中不存在的单词时，ACM就会试图用字典中与该单词最相似的单词替代它。ACM对单词是相似的有这样的定义：只要两个单词能够按照上面叙述的3类拼写错误规则中的任何一种进行相互转换，就认为这两个单词是相似的。如果在字典中没有发现相似的单词，就在原文本中保留这个未知的单词。

输入：

在输入文件的第1行里将给出字典中已知的单词数量：整数n，其中

0<=n<=1000。在紧接着的n行里包含有字典中的n个单词。在这n行后的第1行里将给出1个正整数q，其中0<=q<=1000，它表示需要查询单词的数量。在这之后的q行里包含有q个需要查询的单词。你可以假设在输入文件中每一个单词只能由26个小写字母（'a'~'z'）构成。

输出：

针对每一个需要查询的单词，输出一行字符串。要求：该字符串以需要查询的单词开始，并从下面3个黑体描述中选择一个合适的字串添加在后。

1.如果需要查询的单词在字典中就添加字串“is correct”

2.如果需要查询的单词不在字典中，则添加字串“is a misspelling of ”，其中 是指字典与需要查询的单词相似的单词。若x有多个，则选择在字典中出现最早的那个单词输出。

3.如果前面两种情况都不满足，则添加字串“is unknown”。

输入样本： 10 this is a

dictionary that we will use

for us 6 su as the

dictionary us willl

输出样本：

su is a misspelling of us as is a misspelling of is the is unknown

dictonary is a misspelling of dictionary us is correct

willl is a misspelling of will

5. 轰炸

输入文件：bomb.in 输出文件：estdout.pc2

问题描述：

“我该怎么办？”飞行员klux向你求助。事实上，klux面对的是一个很简单的问题，但是他实在是太菜了。Klux要想轰炸某个区域内的一些地方，它们是位于平面上的一些点，但是klux遇到了抵抗，所以他只能飞一次，而且由于飞机比较破，一旦起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸最多的地方。

输入：

输入由若干组数据构成，每组数据的第一行是整数n，然后是n行整数对组成(1

输出：

针对没组数据输出一个数，它表示一条直线能覆盖的最多的点数

输入样本： 5 1 1 2 2 3 3 9 10 10 11 0

输出样本： 3

6. 国家利益

输入文件：country.in 输出文件：estdout.in

问题描述：

没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力。伊拉克战争结束后N个国家正在联合国开会商讨如何分配伊拉克的M块油田。

N个国家按国家实力编号1，2，3...N，1号国家实力最强，第一个发言，N号最后一个发言；依次类推发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己）；如果50%或以上同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失表决权，下个国家重复上述过程。那么第一个国家提出怎样的方案才能使本国利益最大化？

提示：

每个国家分得的油田都是整数，不会出现几个国家共同拥有一块油田。每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案， X号国家分Y油田，X号国家会进行比较， 如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z < Y，那么X号国家会赞成1号的方案， 否则反对。

输入：

输入文件有由若干行构成，每行包括一组数据由2个整数N，M构成，（N,M <= 10^8），输入文件的最后一行是‘#’表示文件结束。

输出：

按照输入文件的顺序对于每组输入数据输出一行，每行包括1个整数，1号国家能获得的最多油田数。

输入样本： 7 100 6 100 #

输出样本： 97 98

7. 拱猪计分

输入文件：pig.in 输出文件：estdout.pc2

问题描述：

拱猪是一种有趣的扑克牌游戏。即使你不知道他的玩法，你也可以由他的计分方式来了解他的趣味性。假设在此我们仅考虑四个人的拱猪牌局，本题要求你根据下面的积分规则，在牌局结束时计算四位玩家所得分数。

1.我们分别以S、H、D及C来代表黑桃，红心，方块及梅花，并以数字1至13来代表A、2、...、Q、K等牌点，例如：H1为红心A，S13为黑桃K。

2.牌局结束时，由各玩家持有的有关计分的牌（计分牌）计算得分。计分牌仅有S12（猪），所有红心牌，D11(羊)及C10（加倍）等16张牌。其他牌均弃之不计。若未持有这16张牌之中的任意一张，则以得零分计。

3.若持有C10的玩家只有该张牌而没有其他牌则得+50分，若除了C10还有其他计分牌，则将其他计分牌所得分数加倍计算。

4.若红心牌不在同一家，则H1至H13等13张牌均以负分计，其数值为-50，-2，-3，-4，-5，-6，-7，-8，-9，-10，-20，-30，-40.而且S12和D11分别以-100和+100分计算。

5.若红心牌H1至H13均在同一家，有下列情形：

a) 所有红心牌以+200分计算 b) 若S12、D11均在吃下所有红心牌的这一家，则此玩家得+500

分

c) 而C10还是以前面的原则计算分数

例一：

若玩家持有计分牌如下：（每列代表一玩家所持有之牌）

S12 H3 H5 H13 D11 H8 H9

C10 H1 H2 H4 H6 H7 H10 H11 H12

则各玩家得分依次序为：-148，+83，-138及-60。

例二：

若各玩家持有计分牌如下（第四个玩家未持有任何计分牌）

H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 S12 C10 D11

则各玩家得分依次序为：+200，-200，+100及0。 例三：

若有一玩家持有所有16张计分牌，则得分+1000分，其余玩家均得零分。

输入：

每个输入文件有多组数据组成，每组测试数据有四行，每一行第一个数为该玩家所持有计分牌的总数，而后列出其所持有的所有计分牌，牌数与各计分牌均以一个以上的空格分开。

相邻两组测试数据之间不会有空白行，读到四家持牌数都为零表示文件结束。 输出：

每一行输出一组测试数据对应的结果，一次输出各玩家所得分数，共四个整数（含正负号，0除外），相邻两个整数之间用一个空格隔开，符号和数字之间不可以有空格。每组输出之间不需要空白行。 输入样本：

4 S12 H3 H5 H13 3 D11 H8 H9

6 C10 H1 H2 H4 H6 H7 3 H10 H11 H12

13 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 2 S12 C10 1 D11 0 0 0 0 0

输出样本：

-148 +83 -138 -60 +200 -200 +100 0

8. 定向越野

输入文件：cross.in 输出文件：estdout.pc2

问题描述：

XX大学城离市中心比较远，因此占地面积巨大，因而XX市团委准备充分利用资源，在大学城举办定向越野比赛，但规则与普通定向越野不同，每个队被要求从某个起点出发最后到达终点，只要是地图上每个标注的点都可以走，经过一个点时必须在打卡器上打卡做记录，记录该点的打卡器所在位置的海拔高度，高度用一个非负整数来度量，该书将会被保存在卡中。最后到达终点时，该队的成绩就为卡中记录的最大数与最小数之差，差最小的队伍将摘取桂冠。

ZZ和他的同学也参加了这次比赛，拿到地图后，他们想要迅速的找到一条最佳路线以确保获得冠军。

PS:其实光脑子好使能算出最佳路线还不够，还得能跑，但是我们假设ZZ他们队个个都是SUPERMAN，只要你能帮助他们找到最佳路线，它们就一定是冠军。

输入：

由多组数据组成，输入文件以EOF结尾

每组数据的第一行包含一个正整数n，表示校园地图上共有n*n被标注的点(n<=100)，接下来n行每行有n个非负整数Ai,j，表示该点打卡器所在位置高度（Ai,j<=200），ZZ和他的同学从（1,1）出发，目的地为（n,n）

输出：

每组数据对应一行输出，包含一个整数，及最小的高度差的值

输入样本： 5

1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 2 4 4 3 0 3 1 输出样本： 3

Tips:

最佳路线为

(1,1)→(1,2)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)→(5,4)→(5,5)

路线上最高高度为3，最低高度为0，所以答案为3.当然，最佳路线可能不止一条。

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