第五届全国青少年信息学奥林匹克分区联赛(普及组)
暨99北京市青少年计算机程序设计竞赛初中组复赛试题

第一题：Cantor表

把分子和分母均小于108的分数按下面的办法排成一个数表。

1/2→1/2 1/3→1/4 1/5 ……
↙ ↗ ↙ ↗
2/1 2/2 2/3 2/4 2/5 ……
↓↗ ↙ ↗
3/1 3/2 3/3 3/4 3/5 ……
↙ ↗
4/1 4/2 4/3 4/4 4/5 ……
↓↗
5/1 5/2 ……
……

我们以Z方形方法给上表的每项编号。第一项是1/1，然后是1/2、2/1、3/1、2/2、1/3、1/4、2/3……。编程输入项号N（1<=N<=10），输出表中第N项。

例：输入：N=7 输出：1/4

　

第二题：回文数

若一个数（首位不为0）从左到右读与从右到左读都是一样，这个数就叫做回文数，例如12512就是一个回文数。

给定一个10进制正整数，把它的各位数字上数字倒过来排列组成一个新数，然后与原数相加，如果是回文数则停止，如果不是，则重复这个操作，直到和为回文数为止。例如：10进制87则有：

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

（1）编写一个程序，输入10进制数M（1<=M<=1000）,输出最少经过几步可以得到回文数。如果在30步以内（含30步）不可能得到回文数，则输出“Impossible!”。数出格式为：

输入： M=87 输出： Step=4

（2）把（1）中“输入10进制数”改为“输入N进制数（1<N<=10, N=16）”又如何编程？输出格式为：

输入：N=9 M=87 输出：Step=6

　

第三题：旅行家的预算

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D、汽车邮箱的容量C（以升为单位）。每生汽油能行使距离D0、出发点的每升汽油价格P和沿途油站数（N可以是0）、油站I离出发点的距离Di、油站I每升汽油价格Pi（I=1,2,3……N）。编程找出一种加油方案，使费用最少，输出这个最少的费用值，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”。例如：

输入：

D=275.60 C=11.90 D0=27.40 P=2.80 N=2

油站号i 离出发点距离Di 每升汽油价格Pi
1 102.00 2.90
2 220.00 2.20

输出：

Cost=26.95 (该数据表示最小费用)