第一题 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≤10000000） 输出：表中的第N项
样例： INPUT OUTPUT
N=7 1/4
答案:
第一题 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
[分析]
题目很简单，规律也不难找到。这类题目其实是数学游戏,在编码之前应该先算一算。
用模拟填表的方法也可以，但数学方法更有意思，求解能力也更强。
不难看出，第K个斜行（"/"方向）上每个分数的分子分母之和为K+1,而表的填充顺序正是
依次填写每个斜行，因此先算出第N项所在的斜行K。
显然K是满足
N<=1+2+3+...+K (1)
的最小数。
显然当K为奇数时,分母为N-(1+2+3+..+K-1),K为偶数时分子为N-(1+2+3+..+K-1)。
找K显然可以递推，但是没有意思，我们应该锻炼自己的数学能力，解出不等式(1)。
不等式同解变形为:
(K+1)*K>=N*2
K*K+K-N*2>=0
解不等式，取正数区间，得 K>=(-1+sqrt(1+8*N))/2。
例如N=7时
K>=(-1+sqrt(1+7*8))/2=3.275
故K=4,分子分母之和为K+1=5,因为K是偶数，分子为N-(1+2+3)=1,故分母为5-1=4
注意：题目没有要求时，分区联赛不需要做出错处理。
第二题 回文数（30分）
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把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 OUTPUT
N = 9 M= 87 STEP=6
答案:
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回
文数。例如：给定一个 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步）不可能得到回文数，则输出“Impossible”
样例：
INPUT
N＝9 M＝87
Output
STEP=6
[分析]
本题也很简单，只是考查了一些基本编程能力，没有什么难度可言。只要细心，本题的分是可以
轻松拿到手的。
这里数采用字符串表示（其他方法当然也可以），因为处理方便。
N进制的加法是本题的重头戏，处理如下：
1)字符->数字，可以用数组来简化程序,即digit和chars数组
2)做加法，保留各位数字和进位，就想做高精度加法一样。g是进位
第三题 旅行家的预算（40分）
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离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
油站号I 离出发点的距离Di 每升汽油价格Pi
1 102.0 2.9
2 220.0 2.2
OUTPUT 26.95（该数据表示最小费用）
答案:
第三题 旅行家的预算（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
1 102.0 2.9
2 220.0 2.2
OUTPUT
26.95（该数据表示最小费用）
[分析]
看到题目后，很容易想到递推，但是又不知道具体怎样做。我们可以先分析一下题目，用手工算
几个数据，看能不能受到启发（注意：这是一个很重要的思路!!）
例如可以先分析样例数据（这是理解题意思必须的，因为样例不会错）
算了一下吗？好了，我问你，如果你是司机，你会怎么办呢？
尽量买便宜的，贵的就买“刚刚可以到下一站”？对不对呢？
举出反例很容易，但是我们不能轻易放弃这个思路，可以接着想下去。
不能保证全局最优，我们就试着改进我们的方法。
事实上，要用的油是确定的（D1/D2），价钱最便宜的油的站Q的油显然应该多买，至少：
到达Q这个油站时汽车剩油不为0的方案一定不是最优的。
这是因为，如果剩下P升油，显然不如当初少买P升，改在Q这里买P升划算！（Q最便宜嘛！）
哈哈，有一点思路了吧！就是把较优解改进为最优解啦！
算法如下：
每次都假装装满油，用的时候先用便宜的，因为把贵的留在后面“反悔”(被替换成更便宜的油)不是更爽吗？！
这样计算费用时只考虑真正使用的，假装装满时就不要再算一次了。你看看程序中是不是只有两处修改了cost？
我很懒，因此就默认油站是按离起点由近及远给出的。
输入后面是先把油费由贵到便宜排序,第i贵的站是place，以便选择。
下面的程序中主要部分是那个循环，它做了以下事情：
1)假装装满油：gas:=c-nowp; nowp是现在有的油，gas是车上第i站的油的体积。
2)替换：现有的油如果有比当前站（第i站）贵的，改为i号油：gas:=gas+gas[j]; gas[j]:=0;
3)行驶：依次选择最便宜的油行驶路程distance,就是个循环for j:=n downto 0
经过这样分析,程序是不难写出了，程序长一点，是为了写得更易懂。
基础较好的同学也可以用优先队列（例如用堆来实现）来进行替换和使用油，这里只用了最简单的方法模拟，
效率并不高。
