第五届全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛试题 （上机编程三小时完成）

第一题 拦截导弹（28分） 　　

     某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统

 有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高 于前一发的高度。

    某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以 只有一套系统，因此有可能不能

拦截所有的导弹。 　　

  输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算 这套系统最多能拦截

多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截 系统。 

样例： 

INPUT 

389 207 155 300 299 170 158 65 

OUTPUT 

6（最多能拦截的导弹数） 

2（要拦截所有导弹最少要配备的系统数）

第二题 回文数（25分）
　　若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回
文数。例如：给定一个 10进制数 56，将 56加 65（即把56从右向左读），得到 121是
一个回文数。又如，对于10进制数87，
                  STEPl： 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步）不可能得到回文数，则输出“Inpossible”样例： 

INPUT 

N＝9 M＝87 

Output 

STEP=6

第三题 旅行家的预算（27分）
    一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是
空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行
驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距
离Di、每升汽油价格  Pi（ i＝l，2，...N）。
      计算结果四舍五入至小数点后两位。
      如果无法到达目的地，则输出“No solution”。

样例：

INPUT D1＝275.6 C=11.9 D2＝27.4 P=2.8 N=2 　

油站号i 　离出发点的距离Di　每升汽油价格Pi 　

 １ 　　     102.0 　            29 　

 ２ 　     　220.0 　           2.2

OUTPUT 

26.95（该数据表示最小费用）

第四题 邮票面值设计（40分） 给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k<=40) 

种邮票的情况 下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max ，

使得1－ max之间的每一个邮资值都能得到。 例如，N=3，K＝2，如果面值分别为1分、4分，

则在l分-6分之间的每一个邮资值 都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，

则在1分-7分之间的 每一个邮资值都能得到。可以验证当N=3，K＝2时，7分就是可以得到连续的邮资

最大值 ，所以MAX=7，面值分别为l分、3分。

样例： 

INPUT 

N=3 k=2 

OUTPUT 

1 3 

MAX=7