NOIP1995年复赛试题
1. 设有下列的算式：求出□中的数字，并打印出完整的算式来。 8 0 9 ------------- □□) □□□□ □□
------------- □□□ □□□ ------------- 1
2. 方阵填数：在一个N?N的方阵中，填入1，2，??N?N个数，并要求构成如下的格式： 例：
制数称为A类数，否则就称其为B类数。
例如：（13）10=（1101）2 其中1的个数为3，0的个数为1，则称此数为A类数； （10）10=（1010）2 其中1的个数为2，0的个数也为2，称此数为B类数； （24）10=（11000）2 其中1的个数为2，0的个数为3，则称此数为B类数； 程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。
4.编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
例如：N=6时，有： A=（4，3，0，5，1，2） 此时，数组A的编码定义如下： A[0]的编码为0；
A[i]的编码为：在A[0]，A[1]，??A[i-1]中比A[i]的值小的个数（i=1，2??N-1） ∴上面数组A的编码为：
B=（0，0，0，3，1，2）
程序要求解决以下问题：给出数组A后，求出其编码；给出数组A的编码后，求出A中的原数据。 5. 灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，??Nk（k表示不同颜色灯的个数）。
放灯时要遵守下列规则：同一种颜色的灯不能分开；不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序 R R R
N=5
13 14 15 16 1 12 23 24 17 2 11 22 25 18 3 10 21 20 19 4 9 8 7 6 5
N=6
16 17 18 19 20 1 15 30 31 32 21 2 14 29 36 33 22 3 13 28 35 34 23 4 12 27 26 25 24 5 11 10 9 8 7 6
3. 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进
R R R R R R R R B R 1 B B B B B B B B B B B B B B B B B B-R顺序
B B B N
P1（颜色，为一个字母） N1（灯的数量） P2 N2 ??
Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。
B B B B B B B B B B B B B B R B R R R R R R R R R R R 放置的总数为12种。数据输入的方式为：
NOIP1996年复赛试题
1．编制一个乘法运算的程序（20分）
从键盘读入2个100以内的正整数，进行乘法运算并以竖式输出。 例如，输入格式：8913 又如，输入格式：16 8
输出格式： 89 输出格式： 16 × 13 × 8 267 128 89 1157
2．输入三个自然数N，i，j （1<=i<=N，1<=j<=N），输出在一个N*N格的棋盘中，与格子（i，j）同行、同列、同一对角线的所有格子的位置。（20分）
如：n=4，i=2，j=3表示了棋盘中的第二行第三列的格子，如下图： 第一列 第二列 第三列 第四列 (2,3) 第1行 第2行 第3行 第4行 当n=4，i=2，j=3时，输出的结果是： (2,1) (2,2) (2,3) (2,4) (1,3) (2,3) (3,3) (4,3) (4,1) (3,2) (2,3) (1,4)
{同一行上格子的位置} {同列列上格子的位置}
{左上到右下对角线上的格子的位置}
2
(1,2) (2,3) (3,4)
{左下到右上对角线上的格子的位置}
3．字符串编辑（30分）
从键盘输入一个字符串（长度<=40个字符），并以字符 ’.’ 结束。 例如：’This is a book.’ 现对该字符串进行编辑，编辑功能有： D：删除一个字符，命令的方式为： D a 其中a为被删除的字符
例如：D s 表示删除字符 ’s’ ，若字符串中有多个 ‘s’，则删除第一次出现的。 如上例中删除的结果为： ‘Thi is a book.’ I：插入一个字符，命令的格式为：
I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。
例如：I s d 表示在指定字符 ’s’ 的前面插入字符 ‘d’ ，若原串中有多个 ‘s’ ，则插入在最后一个字符的前面，如上例中：
原 串：’This is a book.’ 插入后：’This ids a book.’ R：替换一个字符，命令格式为：
R a1 a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1则应全部替换。
例如： 原 串： ‘This is a book.’
输入命令：R o e 替换后的字符串为： ‘This is a beek.’ 在编辑过程中，若出现被改的字符不存在时，则给出提示信息。 4．比赛安排（30分）
设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。例如n=2时的比赛安排： 队 1 2 比赛 1==2 1==3
3 4 3==4 2==4
一天 二天
1==4 2==3 三天
NOIP1997年复赛试题
1．设有一个n*m方格的棋盘（1≤m,n≤100）。（30%）
求出该棋盘中包含多少个正方形、多少个长方形（不包括正方形）。 例如：当n=2，m=3时
长方形的个数有10个； 即2*1的长方形有4个；
1*2的长方形有3个； 3*1的长方形有2个；
3*2的长方形有1个。
3
正方形的个数有8个；即边长为1的正方形有6个； 边长为2的正方形有2个。
程序要求：输入：n和m 输出：正方形的个数与长方形的个数 如上例： 输入：2 3 输出：8，10
2．将1，2，······,9共9个数排成下列形态的三角形。（30%） a b c d e f g h i
其中：a～i分别表示1，2，······,9中的一个数字，并要求同时满足下列条件： （1）a （3）a+b+d+f=f+g+h+i=i+e+c+a=P 程序要求： 根据输入的边长之和P 输出所有满足上述条件的三角形的个数以及其中的一种方案。 3．设有一个N＊M（l≤ N≤50， l≤ M≤ 50）的街道（如下图）：（40%） 北 5 B（9，5） 4 东 * * * * * * 3 西 2 * * * * * * 1 1 2 3 4 5 6 7 8 9 A（1，1） 南 规定行人从A(1,1)出发，在街道上只能向东或北方向行走。 如下为N＝3，M=3的街道图，从A出发到达B共有6条可供行走的路径： A6 A7 B（N，M） 1.A-A1-A2-A5-B 2. A-A1-A4-A5-B 3. A-A1-A4-A7-B A3 A4 A5 4. A-A3-A4-A5-B 5. A-A3-A4-A7-B A A1 A2 6. A-A3-A6-A7-B 若在N＊M的街道中，设置一个矩形障碍区域（包括围住该区域的街道）不让行人通行，如图中用“＊”表示的部分。此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2，2),(8，4),此时从 A出发到达B的路径仅有两条。 程序要求：任务一：给出N，M后，求出所有从A出发到达B的路径的条数。 任务二：给出N，M，同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1), （X2，Y2），然后求出此种情况下所有从A出发到达B的路径的条数。 NOIP1998年复赛试题 1．将1，2，?，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成 1：2：3的比例，试求出所有满足条件的三个三位数。 例如：三个三位数192，384，576满足以上条件。 {30%} 4 2．用高精度计算出S=1！+2！+3！+?+n！（n≤50） 其中“！”表示阶乘，例如：5！=5*4*3*2*1。 输入正整数N，输出计算结果S。 {30%} 3．任何一个正整数都可以用2的幂次方表示。例如： {40%} 137=2+2+2 7 3 0 b 同时约定方次用括号来表示，即a 可表示为a（b）。 由此可知，137可表示为： 2（7）+2（3）+2（0） 进一步：7= 2+2+2 2 0 （2用2表示） 3=2+2 10 8 5 10 所以最后137可表示为： 2（2（2）+2+2（0））+2（2+2（0））+2（0） 又如： 1315=2 +2 +2 +2+1 所以1315最后可表示为： 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0） 输入：正整数（n≤20000） 输出：符合约定的n的0，2表示（在表示中不能有空格） NOIP1999年复赛试题 第一题 Cantor表（30分） 现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 1/1 1/2 1/3 1/4 1/5 ? 2/1 2/2 2/3 2/4 ? 3/1 3/2 3/3 ? 4/1 4/2 ? 5/1 ? ? 我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，? 输入：整数N（1≤N≤10000000） 输出：表中的第N项 样例： INPUT OUTPUT N=7 1/4 第二题 回文数（30分） 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（2<=N<=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6 5 1/1 1/2 1/3 1/4 1/5 ? 2/1 2/2 2/3 2/4 ? 3/1 3/2 3/3 ? 4/1 4/2 ? 5/1 ? ? 第三题 旅行家的预算（40分） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，?，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 样例： INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号I 1 2 离出发点的距离Di 102.0 220.0 每升汽油价格Pi 2.9 2.2 OUTPUT 26.95（该数据表示最小费用） NOIP2000年复赛试题 题一 计算器的改良 (18分) 问题描述：NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例： 4＋3x＝8 6a－5＋1＝2－2a －5＋12y＝0 ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及＋、－、＝这三个数学符号（当然，符号“─”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。 问题求解：编写程序，解输入的一元一次方程, 将解方程的结果(精确至小数点后三位)输出至屏幕。你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。 样例：输入：6a－5＋1＝2－2a 输出：a＝0.750 题二．税收与补贴问题 （20分） 问题描述：每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数） 对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币） 问题求解： 你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。 总利润 = 单位商品利润 * 销量 单位商品利润 = 单位商品价格 – 单位商品成本 （– 税金 or + 补贴） 输入：输入的第一行为政府对某种商品的预期价，第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销量售，以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时 6 的销量，以一行-1，-1表示所有已知价位及对应的销量输入完毕，输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。 输出：输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。 如在政府预期价上不能得到最大总利润，则输出“NO SOLUTION”. 样例： 输入 31 28 130 30 120 31 110 -1 –1 15 输出 4 题三 乘积最大 （26分） 问题描述：今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入：程序的输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输出：结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 样例： 输入 4 2 1231 输出 62 题四． 单词接龙 （36分） 问题描述： 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。 输入：输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. 7 输出： 只需输出以此字母开头的最长的“龙”的长度 样例： 输入 5 at touch cheat choose tact a 输出 23 （连成的“龙”为atoucheatactactouchoose） NOIP2001年复赛试题 题一：数的计数 (20分) 问题描述：我们要求找出具有下列性质数的个数(包含输入的自然数n)；先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理 1. 不作任何处理； 2. 茬它的左边加上一个自然数，但该自然数不能超过原数的一半； 3.加上数后，继续按此规则进行处理，直到不能再而 自然数为止。 [样例] 输入：6 满足条件的数为 6 (此部分不必输出) 6 26 126 36 136 输出：6 题二：最大公约数与最小公倍数问题 (20分) 问题描述：输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。 条件：1.. P、Q是正整数；2. 要求P、Q以xO为最大公约数，以yO为最小公倍数。 试求，满足条件的所有可能的两个正整数的个数。 [样例] 输入：x0=3 y0=60 输出：4 说明：(不用输出)此时的 P Q 分别为，满足条件的所有可能的两个正整数的个数共4种。 3 60 15 12 12 15 60 3 8 题三：求先序排列 (30分) 问题描述：给出一棵二叉树的中序与后序排列。求它的先序排列。(树结点用不同的大写字母表示，长度≤8)。 [样例] 输入：BADC BDCA 输出：ABCD 题四：装箱问题 (30分) 问题描述：有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 [样例] 输入： 24 一个整数，表示箱子容量 6 一个整数，表示有n个物品 8 接下来n行，分别表示这n个物品的各自体积。 3 12 7 9 7 输出： 0 一个整数，表示箱子剩余空间。 NOIP2002年复赛试题 题一： 级数求和 [问题描述]：已知：Sn=1+1/2+1/3+?+1/n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。现给出一个整数K（1<=K<=15），要求计算出一个最小的n，使得Sn>K 。 [问题分析]：这道题目非常简单，题目的意思已经把该题的算法描述得再清楚不过了，初始时Sn=0,n=0,然后每次循环n?n+1,Sn?Sn+1/n,，直到Sn大于K，最后输出K。另外实型(Real是最慢的，建议用Extended)的运算速度不是很快，而K为1~15之间的整数，所以最后可以交一张表（常量数组），以达到最好的效果。 题二： 选数 [问题描述]：已知n（1<=n<=20）个整数x1,x2,?,xn（1<=xi<=5000000），以及一个整数k（k 9 接下来的问题就是判断素数，判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a<=sqrt(P))是P的约数，如果不存在，该数就为素数，由于在此题中1<=xi<=5000000,n<=20,所以要判断的数P不会超过100000000，sqrt(p)<=10000，因此，为了加快速度，我们可以用筛选法将2?10000之间的素数保存到一个数组里（共1229个），这样速度估计将提高5~6倍。 特别注意：本题是要求使和为素数的情况有多少种，并不是求有多少种素数，比赛时就有很多同学胡乱判重而丢了12分；还有1不是素数，在判素数时要对1做特殊处理。 题三： 产生数 [问题描述]：给出一个整数n(n<10^30)和k个变换规则（k<=15）。 规则：1个数字可以变换成另一个数字；规则的右部不能为零。 问题：给出一个整数n和k个规则 求出：经过任意次的变换（0次或多次），能产生出多少个不同的整数。 [问题分析]：认真分析题目之后发现，本题搜索显然是不行的，而且对于只需计数而不需求具体方案的题目，一般都不会用搜索解决，其实本题不难看出，可以用乘法原理直接进行计数，用Fi表示数字i包括本身可以变成的数字总个数（这里的变成可以是直接变成也可以是间接变成，比如3->5,5->7,那么3->7），那么对于一个数a（用数组存,长度为n），根据乘法原理它能产生出F[a[1]]*F[a[2]]*F[a[3]]*?F[a[n]]个不同整数，相信这一点大家不难理解。那么现在的关键就是如何求Fi，由于这些变换规则都是反应的数字与数字之间的关系，这很容易让我们想到用图来表示这种关系： 1. 建立一个有向图G，初始化g[i, j] ? False 2. 如果数字i能直接变成数字j，那么g[i, j] ? True 容易知如果数字i能变成数字j，那么i到j必须存在路径，否则i是不可能变成j的，这样一来，Fi的求解就显得非常简单了，求一个顶点v包括本身能到达的顶点数的方法相当多，可以用BFS,DFS,Dijkstra,Floyd，这里介绍一种类似Floyd的有向图的传递闭包算法，该算法实现简单 ，在解决这类问题时比Floyd效率更高，所谓有向图的传递闭包就是指可达性矩阵A=[a[i, j]],其中 a[i, j] = True 从i到j存在通路 a[i, j] = False 从i到j不存在通路 所以有向图传递闭包算法只需将floyd算法中的算术运算符操作‘+’用相应的逻辑运算符‘and’ 和’or’代替就可以了，其算法如下： for k ? 1 to n do for i ? 1 to n do for j ? 1 to n do a[i, j] = a[i, j] or (a[i, k] and a[k, j]) 最后值得注意的是当n很大时输出可能会超过Comp类型的范围，所以要使用高精度乘法，由于高精度算法是信息学竞赛中的基础，这里就不在详述。 题四： 过河卒 [问题描述]：棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。 同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。 棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数 [问题分析]： 这是一道老得不能再老的题目了，很多书上都有类似的题目，NOIp97普及组的最后一题就和本题几乎一模一样。有些同学由于没见过与之类似的题目，在比赛时用了搜索，当n到14，15左右就会超时，其实，本题稍加分析，就能发现：要到达棋盘上的一个点，只能从左边过来或是从上面下来， 10 所以根据加法原理，到达某一点的路径数目，等于到达其相邻上，左两点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起始顶点到重点的路径数目，即使有障碍（我们将马的控制点称为障碍），这一方法也完全适用，只要将到达该点的路径数目置为0即可，用F[i,j]表示到达点(i,j)的路径数目，g[i,j]表示点(i, j)有无障碍，递推方程如下： F[0,0] = 1 F[i,j] = 0 { g[x,y] = 1 } F[i,0] = F[i-1,0] {i > 0, g[x,y] = 0} F[0,j] = F[0,j-1] {j > 0, g[x,y] = 0} F[i,j] = F[i-1,j] + F[i,j-1] {i > 0, j > 0, g[x, y] = 0} 本题与第三题一样，也要考虑精度问题，当n,m都很大时，可能会超过MaxLongInt,所以要使用Comp类型计数(Comp类型已经足够了，即使n=20,m=20，没有任何障碍的情况下的结果也只有14，5位的样子)。 NOIP2003年复赛试题 题一、乒乓球（Table.pas） 【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。 【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：WWWWWWWWWWWWWWWWWWWWWWLW 在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。 你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。 【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。 【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。 【输入样例】 WWWWWWWWWWWWWWWWWWWW WWLWE 【输出样例】 11:0 11:0 1:1 21:0 2:1 11 题二、数字游戏（Game.pas） 【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）： 2 4 3 当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10) -1 ×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。 【输入格式】输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于10，按顺序给出圈中的数字，首尾相接。 【输出格式】输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。 【输入样例】 4 2 4 3 -1 2 【输出样例】 7 81 题三、栈（Stack.pas） 【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。 栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。 【问题描述】 头端 栈A 12 4 输出序列 尾端 头端 1 2 3 操作数序列 宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作， 1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作） 2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作） 使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1 的过程。（原 2 3 3 2 3 始状态如上图所示） 1 2 2 3 2 1 3 1 2 3 1 1 1 你的程序将对给定的n，计算并输出由操作数序列1，2，?，n经过操作可能得到的 输出序列的总数。 【输入格式】输入文件只含一个整数n（1≤n≤18） 【输出格式】输出文件只有一行，即可能输出序列的总数目 【输入样例】3 【输出样例】5 题四、麦森数（Mason.pas） 【问题描述】形如2-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000 【输出格式】第一行：十进制高精度数2-1的位数。第2-11行：十进制高精度数2-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）.不必验证2-1与P是否为素数。 【输入样例】 1279 【输出样例】 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087 13 PPPPPPNOIP2004年复赛试题 1.不高兴的津津 (unhappy.pas/dpr/c/cpp) 【问题描述】津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。 【输入文件】输入文件unhappy.in包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出文件】输出文件unhappy.out包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。 【样例输入】 5 3 6 2 7 2 5 3 5 4 0 4 0 6 【样例输出】 3 2.花生采摘 (peanuts.pas/dpr/c/cpp) 【问题描述】 鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： 1.从路边跳到最靠近路边（即第一行）的某棵花生植株； 2.从一棵植株跳到前后左右与之相邻的另一棵植株； 3.采摘一棵植株下的花生； 4.从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。 例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。 【输入文件】输入文件peanuts.in的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N <= 20），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M 14 行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。 【输出文件】输出文件peanuts.out包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。 【样例输入1】 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 【样例输出1】 37 【样例输入2】 6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 【样例输出2】 28 3.FBI树 (fbi.pas/dpr/c/cpp) 【问题描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： 1.T的根结点为R，其类型与串S的类型相同； 2.若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[2]序列。 【输入文件】输入文件fbi.in第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。 【输出文件】输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 【样例输入】 3 10001011 【样例输出】 IBFBBBFIBFIIIFF 【数据规模】对于40%的数据，N <= 2；对于全部的数据，N <= 10。 15 4.火星人 (martian.pas/dpr/c/cpp) 【问题描述】人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。 火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3??。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。 一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字： 三进制数： 123 132 213 231 312 321 代表的数字： 1 2 3 4 5 6 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。 【输入文件】输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1 <= N <= 10000）。第二行是一个正整数M，表示要加上去的小整数（1 <= M <= 100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。 【输出文件】输出文件martian.out只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。 【样例输入】 5 3 1 2 3 4 5 【样例输出】 1 2 4 5 3 【数据规模】对于30%的数据，N<=15；对于60%的数据，N<=50；对于全部的数据，N<=10000； NOIP2005年复赛试题 1.陶陶摘苹果 (apple.pas/c/cpp) 【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。 【输入文件】输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行 16 只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。 【输出文件】输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。 【样例输入】 100 200 150 140 129 134 167 198 200 111 110 【样例输出】 5 2.校门外的树 (tree.pas/c/cpp) 【问题描述】某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，??，L，都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 【输入文件】输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 【输出文件】输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。 【样例输入】 500 3 150 300 100 200 470 471 【样例输出】 298 【数据规模】对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之间有重合的情况。 3.采药 (medic.pas/c/cpp) 【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 【输入文件】输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 【样例输入】 70 3 71 100 69 1 17 1 2 【样例输出】 3 【数据规模】对于30%的数据，M <= 10；对于全部的数据，M <= 100。 4.循环 (circle.pas/c/cpp) 【问题描述】乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。 众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6??我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象： 循环 循环长度 2：2、4、8、6 4 3：3、9、7、1 4 4：4、6 2 5：5 1 6：6 1 7：7、9、3、1 4 8：8、4、2、6 4 9：9、1 2 这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？ 注意：1． 如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。 2． 如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。 【输入文件】输入文件circle.in只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。 【输出文件】输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。 【样例输入】 32 2 【样例输出】 4 【数据规模】 对于30%的数据，k <= 4；对于全部的数据，k <= 100。 NOIP2006年复赛试题 1 ．明明的随机数 【 问题描述】 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，性是用计算机生成了N 个l 到l000之间的随机整数（N <=100 ） ，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序．然后有空去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 【 输入文件】 输入文件random.in 有2 行，第1 行为1 个正整数，表示所生成的随机数的个数：N 18 第2 行有N 个用空格隔开的正整数，为所产生的随机数。 【 输出文件】 输出文件random.out 也是2 行，第1 行为1 个正整数M ，表示不相同的随机数的个数。第2 行为M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。 【 输入样例】 1O 20 40 32 67 40 20 89 300 400 15 【 输出样例】 8 1 5 20 32 40 67 89 300 400 2 ．开心的金明 ( h appy . pas / c / Cpp ) 【 问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了．可能会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 请你帮助金明设计一个满足要求的购物单。 【 输入文件】 输入文件happy。in 的第1 行，为两个正整数，用一个空格隔开： （总钱数N<30000，希望购买物品的个数m < 25，物品的价格v < = 10000） 【 输出文件】 Happy.out只有一个正整数，为不超过总钱数的物品的价格与其重要度的乘积之和的最大值（<100000000） 【 输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【 输出样例】 3900 3.【 问题描述】 Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam 数字。在Jam 数字中，每个字母互不相同，而且从左到右是严格递增的。每次还指定使用字母的范围，例如，从2 到10，表示只能使用｛b , c , d , e , f , g , h ，i，j｝如果再规定位数为5 ，那么，紧接在Jam 数字“bdfij”之后的数字应该是“bdghi\Jam数字，按顺序输出紧接在后面的5 个Jam数字。如果后面没有那么多Jam 数字，那么有几个就输出几个。 【 输入文件】 所给的数据都是正确的，不必验证。 【 输出文件】 输出文件count.out最多为5 行，为紧接在输入的Jam 数字后面的5 个Jam 数字，如果后面没有那么多Jam 数字，那么有几个就输出几个。每行只输出一个Jam 数字，是由w 个小写字母组成 19 的字符串，不要有多余的空格。 【 输入样例】 2 105 bdfij 【 输出样例】 bdghi bdqhj bdgij bdhij befqh 4、数列 给定一个正整数k (3<=k<=15) , k 的方幂之和构成一个递增的序列，例如，当k = 3 时，把所有k 的方幂及所有有限个互不相等的这个序列是： l , 3 , 4 , 9 , 10 , 12 , 13 ?? （该序列实际上就是：3^0 ，3^1 , 3^0+3^1 , 3^2 , 3^0+3^2 , 3^1+3^2 , 3^0+3^1+3^2 ，? ） 请你求出这个序列的第N 项的值（用10 进制数表示）。 例如，对于k=3 , N = 100 ，正确答案应该是981 。 【 输入文件】 输入文件sequence.in 只有l 行，为2 个正整数，用一个空格隔开：k N ( k 、N 的含义与上述的问题描述一致，且<= k<=15 , 10<=N<=1000）。 【 输出文件】 输出文件sequence.out为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9，整数前不要有空格和其他符号）。 【 输入样例】 3 100 【 输出样例】 981 NOIP2007年复赛试题 1. 奖学金 (scholar.pas/c/cpp) 【问题描述】 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。 任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是: 7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输 20 出数据是: 5 279 7 279 则按输出错误处理，不能得分。 【输入】 输入文件scholar.in包含n+1行: 第1行为一个正整数n，表示该校参加评选的学生人数。 第2到n+1行，每行有3个用空格隔开的数字，每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。 【输出】 输出文件scholar.out共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。 【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar. in scholar. out 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 8 265 2 264 6 264 1 258 5 258 【限制】 50%的数据满足:各学生的总成绩各不相同 100%的数据满足: 6<=n<=300 21 2.纪念品分组 group.pas/c/cpp) 【题目描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。 【输入】输入文件group.in包含n+2行: 第1行包括一个整数w，为每组纪念品价格之和的上眼= 第2行为一个整数n，表示购来的纪念品的总件数G。 第3-n+2行每行包含一个正整数Pi (5 <= Pi <= w3)w表示所对应纪念品的价格。 【输出】输出文件group.out仅→行，包含一个整数， ep最少的分组数目合 【输入输出样例】 group.in group. out 100 9 90 20 20 30 50 60 70 80 90 6 【限制】 50%的数据满足: 1 <=n <= 15 100%的数据满足: 1 <= n <= 30000， 80 <= W <= 200 3. 守望者的逃离 (escape.pas/c/cpp) 【问题描述】 恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，刀上的所有人都会遇难：守望者的跑步速度，为17m/s， 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 【输入】 输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。 【输出】 输出文件escape.out包含两行: 第1行为字符串\或\区分大小写)，即守望者是否能逃离荒岛。 第2行包含一个整数，第一行为\区分大小写)时表示守望着逃离荒岛的最短时间 第一行为\区分大小写) 时表示守望者能走的最远距离。 【输入输出样例1】 escape.in escape.out 39 200 4 No 22 197 【输入输出样例2】 escape.in escape.out 36 255 10 Yes 6 【限制】 30%的数据满足: 1 <= T<= 10， 1 <=S<= 100 50%的数据满足: 1 <= T <= 1000， 1 <= S <= 10000 100%的数据满足: 1 <= T <= 300000， 0 <= M<=1000 1 <=S <= 10^8 4.Hanoi双塔问题 hanoi.pas/c/cpp 【问题描述】给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】 输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】 输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。 【输入输出样例1】 hanoi.in hanoi.out 1 2 【输入输出样例2】 hanoi.in hanoi.out 2 6 【限制】 对于50%的数据， 1<=n<=25 对于100% 数据， 1<=n<=200 NOIP2008年复赛试题 1.ISBN号码（isbn.pas/c/cpp） 【问题描述】每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。 识别码的计算方法如下：首位数字乘以1加上次位数字乘以2??以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，?，9，再求和，即0×1+6×2+??+2×9=158，然后取158 mod 11的结果4作为识别码。 你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。 【输入】输入文件isbn.in只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 【输出】输出文件isbn.out共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。 【输入输出样例1】 【输入输出样例2】 23 isbn.in 0-670-82162-4 isbn.out Right isbn.in 0-670-82162-0 isbn.out 0-670-82162-4 2.排座椅（seat.pas/c/cpp） 【问题描述】上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。 【输入】输入文件seat.in的第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K 接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。 【输出】输出文件seat.out共两行。 第一行包含K个整数，a1a2??aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、?、第aK 行和第aK+1行之间要开辟通道，其中ai< ai+1，每两个整数之间用空格隔开（行尾没有空格）。 第二行包含L个整数，b1b2??bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、?、第bL 列和第bL+1列之间要开辟通道，其中bi< bi+1，每两个整数之间用空格隔开（行尾没有空格）。 【输入输出样例】 seat.in 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 【输入输出样例解释】 4 3 4 2 1 * seat.out 2 2 4 * ※ ※ + + 1 2 3 4 5 上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。 3.传球游戏ball.pas/c/cpp） 【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按 24 接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。 【输入】输入文件ball.in共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。 【输出】输出文件ball.out共一行，有一个整数，表示符合题意的方法数。 【输入输出样例】 ball.in 3 3 ball.out 2 +---+ / /| 高 +---+ | | | + |长 |/ 宽 +---+ 1 ..+---+---+ ./ / /| +---+---+ | | | | + | | |/. +---+---+.. 2 ?.+---+ ?/ /| ..+---+ | ./ /| + +---+ |/. | | +.. | |/? +---+?. 3 【限制】40%的数据满足：3<=n<=30，1<=m<=20; 100%的数据满足：3<=n<=30，1<=m<=30 4.立体图（drawing.pas/c/cpp） 【问题描述】小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。 小渊有一块面积为m*n的矩形区域，上面有m*n个边长为1的格子，每个格子上堆了一些同样大小的吉姆（积木的长宽高都是1），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放： ..+---+ ./ /| +---+ | | | + | |/| +---+ | | | + | |/. +---+.. 每个顶点用1个加号’+’表示，长用3个”-“表示，宽用1个”/”表示，高用两个”|”表示。字符’+’‘-‘’/’‘|’的ASCII码分别为43，45，47，124。字符’.’（ASCII码46）需要作为背景输出，即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则：若两块积木左右相邻，图示为右2；若两块积木上下相邻，图示为左图：若两块积木前后相邻，图示为右3。 立体图中，定义位于第(m,1)的格子（即第m行第1列的格子）上面自底向 上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。 【输入】输入文件drawing.in第一行有用空格隔开的两个整数m和n，表示有m*n个格子（1<=m，n<=50）。 行第j列的格子上摞有多少个积木（1<=每个格子上的积木数<=100）。 接下来的m行，是一个m*n的矩阵，每行有n个用空格隔开的整数，其中第i行第j列上的整数表示第i【输出】输出文件drawing.out中包含题目要求的立体图，是一个K行L列的字符矩阵，其中K和L表示最少需要K行L列才能按规定输出立体图。 【输入输出样例】drawing.in drawing.out 3 4 2 2 1 2 2 2 1 1 3 2 1 2 ......+---+---+...+---+ ..+---+ / /|../ /| ./ /|-+---+ |.+---+ | +---+ |/ /| + | | + | | +---+ |/+---+ |/| | |/ /| +/ /|-+ | +---+---+ |/+---+ |/| + | | | +-| | + |/. | | |/ | |/| +.. +---+---+---+---+ |/... | | | | | +.... | | | | |/..... +---+---+---+---+...... 25