1999年第五届全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛试题

（上机编程，三小时完成）

第一题　拦截导弹（28分）

　　某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
　　输入导弹依次飞来的高度（雷达给出的高速数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例：
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）

第二题　回文数（25分）

　　若一个数（首位不为零）从左到右读与从右到左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把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
N=9 M=87
OUTPUT
STEP=6

第三题　旅行家的预算（27分）

　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离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

OUTPUT
26.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分。
样例：
INPUT
N=3 K=2
OUTPUT
1 3
MAX=7