1、1第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （提 高 组 竞赛用时：3 小时）第一题 拦截导弹(28 分)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUT OUTPUT389 207 1
2、55 300 299 170 158 65 6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）第二题 回文数(25 分)若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个 10 进制数 56，将 56 加 65（即把 56 从右向左读） ，得到 121 是一个回文数。又如：对于 10 进制数 87：STEP1：87+78 = 165 STEP2：165+561 = 726STEP3：726+627 = 1353 STEP4：1353+3531 = 4884在这里的一步是指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。写
3、一个程序，给定一个 N（2=N=10 或 N=16）进制数 M，求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出“Impossible！”样例：INPUT OUTPUTN = 9 M= 87 STEP=6第三题 旅行家的预算(27 分)一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的） 。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位） 、每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N（N 可以为零） ，油站 i 离出发点的距离 Di、每升汽油价格Pi（i=1，2，N） 。计算结果四舍五
4、入至小数点后两位。如果无法到达目的地，则输出“No 2Solution”。样例：INPUTD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号 I 离出发点的距离 Di 每升汽油价格 Pi1 102.0 2.92 220.0 2.2OUTPUT26.95（该数据表示最小费用）第四题 邮票面值设计(40 分)给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N+K40）种邮票的情况下（假定所有的邮票数量都足够） ，如何设计邮票的面值，能得到最大值 MAX，使在 1MAX 之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为 1 分、4 分，则在 1 分6 分之间的每一个邮资值都能得到（当然还有 8 分、9 分和 12 分） ；如果面值分别为 1 分、3 分，则在 1 分7 分之间的每一个邮资值都能得到。可以验证当 N=3，K=2 时，7 分就是可以得到的连续的邮资最大值，所以 MAX=7，面值分别为 1 分、3 分。样例：INPUT OUTPUTN=3 K=2 1 3MAX=7
