1999年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（初中组 竞赛用时：3小时）
第一题 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<=10)
输出:表中的第N项
样例:
input: n=7
output: 1/4
第二题 回文数（ 30分）
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回
文数。例如：给定一个 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
第三题 旅行家的预算（40分）
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是
空的）。给定两个城市之间的距离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（该数据表示最小费用）1999年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组 竞赛用时：3小时）
第一题 拦截导弹（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=71999年全国青少年信息学（计算机）奥林匹克分区联赛普及组复赛题测试数据及参考答案
第一题 30分
序号 N 输出 分值
1 15 1/5 5
2 85 7/7 5
3 1999 18/46 10
4 10278 19/125 10
第二题 30分
序号 N M Step 分值
1 2 10011 4 5
2 16 AC27 6 9
3 10 89 24 10
4 2 101111 Impossible! 6
第三题 40分
序号 输入 输出 分值
1 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 334.90 10
2 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 No Solution. 5
100.0 99.9
3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 105.95 12
22.10 7.38
24.21 6.81
82.08 6.96
4 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 192.15 13
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.091999年全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛题测试数据及参考答案
第一题 28分
序号 输入
1 300,250,275,252,200,138,245
2 181,205,471,782,1033,1058,1111
3 465,978,486,476,324,575,384,278,214,657,218,445,123
4 236,865,858,565,545,445,455,656,844,735,638,652,569,714,845
序号 单枚最大可击落导弹数 需要系统数 分值
1 5 2 5
2 1 7 5
3 7 4 10
4 6 7 8
第二题 25分
序号 N M Step 分值
1 2 10011 4 4
2 16 AC27 6 7
3 10 89 24 9
4 2 101111 Impossible! 5
第三题 27分
序号 输入 输出 分值
1 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 334.90 5
2 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 No Solution. 5
100.0 99.9
3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 105.95 7
22.10 7.38
24.21 6.81
82.08 6.96
4 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 192.15 10
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.09
第四题 40分
序号 N K STEP 分值
1 7 3 1，8，13， MAX=69 10
2 7 4 1，5，24，37， MAX=165 10
3 10 3 1，10，28， MAX=146 10
4 5 5 1，4，9，31，51 MAX=126 10
