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

第一题：Cantor表

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面一张表来证明这一名题的：

1/2→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、1/3、1/4、2/3……。编程输入项号N（1<=N<=1000000），输出表中第N项。
例：输入：N=7
输出：1/4

第二题　回文数

　　若一个数（首位不为零）从左到右读与从右到左读都是一样，我们就将其称之为回文数。例如：给定一个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

第三题　旅行家的预算

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