智能算法挑战赛决赛题目——初中组
题目 1. 判断是否存在重复的子序列
从 m 个字符中选取字符，生成 n 个符号的序列，使得其中没有 2 个相邻的子序列相同。如从 1，2，3，生成长度为 5 的序列，序列“12321”是合格的，而“12323”和“12123”是不合格。问：已知 m 和 n 都是小于等于 10 的数字，求 m 个不同字符，组成长度n 的序列中，无 2 个相邻相同的子序列的序列总数？
输入：
一行两个正整数，第一个是 m，表示不同的字符，第二个是 n，表示序列长度，0<m<=n<=10.
输出：
一个数，表示序列种没有 2 个相邻相同子序列的序列总数。
输入举例：
3 5
输出举例：
30
题目 2. 村村通工程
在平原地区，政府想把 n 个村庄（n<100）之间修建直线距离最短的新马路，并保证所有村庄之间都有新马路可以连通。已知每个村庄的经纬度（坐标），求总距离最短的修路方案，并给出最短的总距离。
输入：
第一行为村庄数 n，n<100
以下 n 行，每行两个实数（可能带小数的）数字，分别是经度和纬度坐标
输出：
最短的总距离，单位千米，保留 2 为小数。
输入举例：
3 5 2 4 3 5 2
输出举例：
1.41
题目 3. 病人看病
病人登记看病，按照如下规则安排病人看病的顺序。
（1） 老年人（年龄>=60 岁）比非老年人优先看病。
（2） 老年人按照年龄大小的顺序看病，相同年龄的老年人按照登记的顺序看病。
（3） 非老年人按照登记的顺序看病。
输入：
第一行，输入一个小于 100 的正整数，表示病人的个数。 后面按照病人登记的先后顺序，每行一个病人的信息号，和病人的年龄，中间用空格隔开；病人的信息号（ID）是一个长度小于 10 的字符串，字符串只包含数字或者字母。
输出：
按看病规则顺序排列的病人 ID，每行表示一个人，依次输出。
输入举例：
5
021075 40
004003 15
010158 67
021033 75
102012 30
输出举例：
021033
010158
021075
004003
102012
题目 4. 生命体的族群模拟
科学家用 AI 模拟生命体的族群分类情况，假设有 n 个新生的生命体，每个生命体都有一个生命值，两个生命体相遇时会发生从斗争到认识到合并到同一族群的过程，在不同族群里面的生命体，如果相遇时，会找到本族群最强者进行两两对决，每次斗争都会让参与者的生命值减半，例如原来是生命值 10，进行斗争后变成 5，原来是 5，进行斗争后变成2，如果生命值是 1，斗争后还维持为 1。斗争后两个族群就合并在一起了，如果两个生命体来自于同一个个族群，则它们不会发生斗争问题。请编写程序，求出每一个对决序列，两个相遇的生命体进行对决后，组成的新的族群的最强者的生命值，如果该对决序列的两个生命体属于同一族群则输出-1。
输入：
第一行是一个整数 n，表示有多少个生命体。
第二行到第 n+1 行是每个生命体的生命值。
第 n+2 行是一个整数 m，表示要进行认识的生命体对的数量。
最后面的 m 行，每行有两个数字，表示要进行对决的生命体的序号。
输出：
对每一对要进行接触的生命体，给出对决后，组成的新的族群的最强者的生命值，如果两者在同一个族群，则输出-1.
输入举例：
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
输出举例：
8
5
5
-1
10