历届noip提高组复赛试题

1/56NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210分钟）1编码问题：设有一个数组A:ARRAY[0..N-1]OFINTEGER；数组中存放的元素为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中的原数据。2灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。例如：N=8（格子数）R=2（红灯数）B=3（蓝灯数）放置的方法有：R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB2/56B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的总数为12种。数据输入的方式为：NP1（颜色，为一个字母）N1（灯的数量）P2N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。3设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：ABC计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。如：3+45=3554+3=23可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=BC+B也就是：8=23+2，15=34+3，……14=26+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。①输入数据不存在出错的情况，同时也不会超过整数的范围。3/56②计算时可允许出现以下情况：A=B（即可理解为运算符的个数为零）A=BB+B（即全部由B产生）第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）1．比赛安排（20分）设有有2n（n=6）个球队进行单循环比赛，计划在2n–1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n–1天内每个队都与不同的对手比赛。例如n=2时的比赛安排：队1234比赛1==23==4一天1==32==4二天1==42==3三天2．数制转换（20分）设有一个字符串A$的结构为：A$=’mnp’其中m为数字串（长度=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。例如：A$=’48108’其意义为：将10进制数48，转换成8进制数输出。输出结果为：4810=6084．挖地雷（30分）在一个地图上有N个地窖（N=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。例如：[题目要求]当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。输入格式：N：（表示地窖的个数）Ｗ1，W2，W3，……WN（表示每个地窖中埋藏的地雷数量）V1V2V3V4V54/56A12…………….A1NA23…………..A2N……..AN-1N输出格式：K1--K2--……….KV（挖地雷的顺序）MAX（挖地雷的数量）例如：⑩--------⑧④-----⑦-------⑥其输入格式为：输出：51–3-4-510，8，4，7，6max=2711100001114．砝码称重（30分）设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），要求：输入方式：a1a2a3a4a5a6（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）输出方式：Total=N（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0（注：下划线表示空格）输出：TOTAL=3表示可以称出1g，2g，3g三种不同的重量。第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）1．在N*N的棋盘上（1≤N≤10），填入1，2，…，N*N共N*N个数，使得任意两个相邻的数之和为素数。（30%）例如：当N=2时，有：1243当N=4时，一种可以填写的方案如下：地窖之间连接路径（其中Ａij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij==0）其相邻数的和为素数的有：1+2，1+4，4+3，2+35/5612111216158513491467103在这里我们约定：左上角的格子里必须填数字1。程序要求：输入：N；输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”。2．代数表达式的定义如下：例如，下面的式子是合法的代数表达式：a；a+b*(a+c);a*a/(b+c)下面的式子是不合法的代数表达式：ab;a+a*/(b+c);程序要求：输入：输入一个字符串，以“；”结束，“；”本身不是代数表达式中字符，仅作为结束）；输出：若表达式正确，则输出“OK”；若表达式不正确，则输出“ERROR”，及错误类型。错误类型约定：1．式了中出现不允许的字符；2．括号不配对；3．其它错误。例如：输入：a+(b);输出：OKacb字母6/56例如：输入：a+(b+c*a;输出：ERROR23．骑士游历：设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上左下角有一个中国象棋马。（n,m）(1,1)马走的规则为：（1）马走日字；（2）马只能向右走即如下图如示：任务1：当n,m输入之后，找出一条从左下角到右上角的路径。例如，输入：n=4，m=4输出：路径的格式：(1,1)→(2,3)→(4,4)。若不存在路径，则输出‘NO’任务2：当n，m给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：（n=10,m=10），（1，5）（起点），（3，5）（终点）输出：2（即由（1，5）到（3，5）共有2条路径）输入格式：n,m,x1,y1,x2,y2(分别表示n,m,起点坐标，终点坐标)输出格式：路径数目（若不存在从起点到终点的路径，输出0）马(4,4)(1,1)10987654321123456789107/56第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）1．火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？输入：a，n，m和x输出：从x站开出时车上的人数。{20%}2．设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613程序输入：nn个数程序输出：联接成的多位数{40%}3．著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。例如：{40%}其含义为：L+L=L，L+K=K，L+V=V，L+E=EK+L=K，K+K=V，K+V=E，K+E=KL……E+E=KV根据这些规则可推导出：L=0，K=1，V=2，E=3同时可以确定该表表示的是4进制加法程序输入：n（n≤9）表示行数。以下n行，每行包括n个字符串，每个字串间用空格隔开。（字串仅有一个为‘+’号，其它都由大写字母组成）程序输出：+LKVELLKVEKKVEKLVVEKLKKEEKLKKKV8/56①各个字母表示什么数，格式如：L=0，K=1，……②加法运算是几进制的。③若不可能组成加法表，则应输出“ERROR！”第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（提高组竞赛用时：3小时）第一题拦截导弹(28分)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）第二题回文数(25分)若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。又如：对于10进制数87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627=1353STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一个N（2=N=10或N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”样例：INPUTOUTPUT9/56N=9M=87STEP=6第三题旅行家的预算(27分)一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“NoSolution”。样例：INPUTD1=275.6C=11.9D2=27.4P=2.8N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2OUTPUT26.95（该数据表示最小费用）第四题邮票面值设计(40分)给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。样例：INPUTOUTPUTN=3K=213MAX=710/562000年题一进制转换（18分）问题描述我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数