几道有趣的算法题

。

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

如果N超过10，使用英文字母来表示那些大于9的数码。例如对16进制数来说，用A表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。

例如：10进制87则有：

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

编写一个程序，输入N(2<=N<=16)进制数M（1<=M<=30000(10进制)）,输出最少经过几步可以得到回文数。如果在30步以内（含30步）不可能得到回文数，则输出0。输入的数保证不为回文数。

【输入】

第一行一个整数L，代表输入数据的组数。

接下来L行，每行两个整数N,M

【输出】

输出L行，对于每个数据组，按题目要求输出结果，并占一行。

【样例输入】

2

10 87

2 110

【样例输出】

4

1

B题 恺撒的规划
【问题描述】

　　亚特兰蒂斯是一块富饶美丽的土地。恺撒大帝率领他的大军，经过了一整年的浴血奋战，终于将它纳入了罗马帝国的版图。然而，长期的战火彻底抹去了这里的繁华，昔日的富庶之地如今一片荒芜。恺撒大帝作为一位有着雄才大略的君主，决心在战争的废墟上建起一座更为宏伟的城市。所以，在建城之前，他需要对整个城市进行规划。

　　亚特兰蒂斯是一块矩形平原，恺撒准备在上面修建一些建筑。为了规划方便，他将矩形划分成N*M格。棘手的是，部分古老的神庙残存下来，散布在某些格子内。亚特兰蒂斯的原住民原本就十分信奉神灵，而这些经过战火洗礼的神庙更是被他们视为圣物，是万万不能拆除的，否则将激起民愤，甚至引发暴动。恺撒深知这一点，因此，他的新建筑在选址时要避开这些神庙。

假设新的建筑物有P种规格，每种建筑物都是正方形的，占地为Ti Ti格 (1<=i<=P)。恺撒想知道对于每种规格的建筑，有多少种不同的合适选址方案（一种合适的选址方案指的是在该建筑所占的正方形区域内不存在神庙）。作为他的内务部长，这个光荣而艰巨的任务自然交给你来完成。

【输入】

　　输入文件第一行包含三个数，分别代表N,M,P (1<=N,M<=100,1<=P<=100)。随后的n行，每行有m个0或1（1表示该格为废墟，0表示该格有神庙）。接下来的P行每行有一个整数 (1< <=max(M,N))，代表的第i种建筑物的边长。

【输出】

输出文件有P行，每行一个整数，第行的数代表边长为 的建筑物选址方案数。

【样例输入】

4 4 2
1011
1111
1110
1110
2
3

【样例输出】

5
1

C题　车 站

【问题描述】

　　辖区内新开了一条高速公路，公路上有两个车站，坐标分别为A（xa，ya）、B（xb，yb），每天都有车辆从A站开往B站。公路附近有两个村庄（公路可能从村庄中穿过），村庄分布在如图所示的带状区域内，坐标为C（xc，yc），D（xd，yd），C、D两村每天都分别有m人要前往B站。

因为高速公路不可随意出入，所以需要在两车站之间的公路上合理地设置一些汽车停靠点，村民可步行至停靠点后进入高速公路，并免费乘车前往B站。每个村民每步行一千米（一个单位看作一千米）所得到的政府补贴为t元，政府维护一个停靠点所需花费为p元/年。应如何设置这些停靠点，才能使政府的支出最小？
　　给出一个年份year，请你设计一个方案，使得镇政府从该年起的n年内总支出最小，注意考虑闰年情况。
　　注意，村民只能进入停靠点而不能直接进入车站，但允许在车站处设置停靠点。

【输入】
　　　　 第一行四个数： xa ya xb yb
　　　　 第二行四个数： xc yc xd yd
　　　　 第三行四个数： m n t p （0<=3000，0<=10）

第四行一个数： year （2000<year<3000）
以上数字，m，year，n为正整数，p，t为正实数，其余均为实数。

【输出】

　　 第一行 最小费用c（单位：元）
　　　　 第二行 设置的停靠点数N（N为正整数）
　　　　 以下N行，每行两个实数，代表停靠点的坐标
　　　　 如有多解，任意输出一解即可。
　　　　 所有实数保留四位小数。

【样例输入】

-5 0 5 0

-1 -1 1 1

1 1 1 500

2001

【样例输出】

1532.3759

1

0.0000 0.0000