算法训练 Tricky and Clever Password   时间限制：2.0s   内存限制：256.0MB     问题描述　　在年轻的时候，我们故事中的英雄——国王 Copa——他的私人数据并不是完全安全地隐蔽。对他来说是，这不可接受的。因此，他发明了一种密码，好记又难以破解。后来，他才知道这种密码是一个长度为奇数的回文串。

　　Copa 害怕忘记密码，所以他决定把密码写在一张纸上。他发现这样保存密码不安全，于是他决定按下述方法加密密码：他选定一个整数 X ，保证 X 不小于 0 ，且 2X 严格小于串长度。然后他把密码分成 3 段，最前面的 X 个字符为一段，最后面的 X 个字符为一段，剩余的字符为一段。不妨把这三段依次称之为 prefix, suffix, middle 。显然， middle 的长度为一个大于 0 的奇数，且 prefix 、 suffix 的长度相等。他加密后的密码即为 A + prefix + B + middle + C + suffix ，其中 A 、 B 、 C 是三个由 Copa 选定的字符串，且都有可能为空， + 表示字符串相连。

　　许多年过去了。Copa 昨天找到了当年写下加密后字符串的那张纸。但是，Copa 把原密码、A、B、C 都忘了。现在，他请你找一个尽量长的密码，使得这个密码有可能被当年的 Copa 发明、加密并写下。输入格式　　输入包含一个只含有小写拉丁字母的字符串，长度在 1 到 10^5 之内。输出格式　　第一行包含一个整数 k ，表示你找到的原密码分成的 3 个部分中有多少个非空字符串。显然 k in {1, 3} 。接下来 k 行，每行 2 个用空格分开的整数 x_i l_i ，表示这一部分的起始位置和长度。要求输出的 x_i 递增。

　　起始位置 x_i 应该在 1 到加密后的字符串长度之间。 l_i 必须是正整数，因为你只要输出非空部分的信息。 middle 的长度必须为奇数。

　　如果有多组答案，任意一组即可。提示：你要最大化的是输出的 l_i 的总和，而不是 k 。样例输入abacaba样例输出1
1 7样例输入axbya样例输出3
1 1
2 1
5 1样例输入xabyczba样例输出3
2 2
4 1
7 2数据规模和约定　　对于 10% 的数据： n <= 10

　　对于 30% 的数据： n <= 100

　　对于 100% 的数据： n <= 100000

　　存在 20% 的数据，输出文件第一行为 1 。

  算法训练 Beaver's Calculator  
时间限制：3.0s   内存限制：256.0MB
   
问题描述
　　从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为"Beaver's Calculator 1.0"。它非常特别，并且被计划使用在各种各样的科学问题中。
　　为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了 ki个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。
　　每个教授的每个问题都用一个数 ai, j  来描述，i（1≤i≤n）是科学家的编号，j（1≤j≤ ki ）是问题的编号， ai, j  表示解决这个问题所需资源单位的数量。
　　这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。
　　计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。
　　给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。
　　所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。
输入格式
　　第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，ki, ai, 1, xi, yi, mi (0 ≤ ai, 1 < mi ≤ 109, 1 ≤ xi, yi ≤ 109) ，分别表示第i个科学家的问题个数，第1个问题所需资源单位数，以及3个用来计算 ai, j 的参量。ai, j = (ai, j - 1 * xi + yi)mod mi。
输出格式
　　第一行输出一个整数，表示最优顺序下最少的“坏对”个数。
　　如果问题的总个数不超过200000,接下来输出 行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。
样例输入
2
2 1 1 1 10
2 3 1 1 10
样例输出
0
1 1
2 1
3 2
4 2
数据规模和约定
　　20%的数据 n = 2, 1 ≤ ki ≤ 2000；
　　另外30%的数据 n = 2, 1 ≤ ki ≤ 200000；
　　剩下50%的数据 1 ≤ n ≤ 5000, 1 ≤ ki ≤ 5000。

 算法训练 Cowboys  
时间限制：2.0s   内存限制：256.0MB
   
问题描述
　　一个间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜……对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所指的方向。“A”表示顺时针方向，“B”表示逆时针方向。如此，一个仅含“A”“B”的字符串便用来表示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环“ABBBABBBA”在一秒后会变成“BABBBABBA”；而牛仔环“BABBA”会变成“ABABB”。 这幅图说明了“BABBA”怎么变成“ABABB” 一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。
输入格式
　　输入数据包括一个字符串s，它只含有“A”和“B”。
输出格式
　　输出你求出来的一秒前的可能排列数。
数据规模和约定
　　s的长度为3到100（包含3和100）
样例输入
BABBBABBA
样例输出
2
样例输入
ABABB
样例输出
2
样例输入
ABABAB
样例输出
4
样例说明
　　测试样例一中，可能的初始排列为："ABBBABBAB"和 "ABBBABBBA"。
　　测试样例二中，可能的初始排列为："AABBB"和"BABBA"。

  算法训练 数字三角形  
时间限制：1.0s   内存限制：256.0MB
   
问题描述
　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
　　径，使该路径所经过的数字的总和最大。
　　●每一步可沿左斜线向下或右斜线向下走；
　　●1＜三角形行数≤100；
　　●三角形中的数字为整数0，1，…99；


　　.
　　（图３.１－１）
输入格式
　　文件中首先读到的是三角形的行数。

　　接下来描述整个三角形
输出格式
　　最大总和（整数）
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

  算法训练 未名湖边的烦恼   时间限制：1.0s   内存限制：256.0MB     问题描述　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）输入格式　　两个整数，表示m和n输出格式　　一个整数，表示队伍的排法的方案数。样例输入3 2样例输出5数据规模和约定　　m,n∈［0,18］
　　问题分析

算法训练 最大的算式   时间限制：1.0s   内存限制：256.0MB     问题描述　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
　　N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：
　　1*2*(3+4+5)=24
　　1*(2+3)*(4+5)=45
　　(1*2+3)*(4+5)=45
　　……输入格式　　输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。输出格式　　输出文件仅一行包含一个整数，表示要求的最大的结果样例输入5 2
1 2 3 4 5样例输出120样例说明　　(1+2+3)*4*5=120

  算法训练 图形显示   时间限制：1.0s   内存限制：512.0MB     问题描述　　编写一个程序，首先输入一个整数，例如5，然后在屏幕上显示如下的图形（5表示行数）：
　　* * * * *
　　* * * *
　　* * *
　　* *
　　*

  算法训练 排序   时间限制：1.0s   内存限制：512.0MB     问题描述　　编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。
　　输入格式：输入只有一行，即三个整数，中间用空格隔开。
　　输出格式：输出只有一行，即排序后的结果。
　　输入输出样例样例输入9 2 30样例输出30 9 2

  算法训练 2的次幂表示   时间限制：1.0s   内存限制：512.0MB     问题描述　　任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。
　　将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0
　　现在约定幂次用括号来表示，即a^b表示为a（b）
　　此时，137可表示为：2（7）+2（3）+2（0）
　　进一步：7=2^2+2+2^0 （2^1用2表示）
　　3=2+2^0
　　所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：1315=2^10+2^8+2^5+2+1
　　所以1315最后可表示为：
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）输入格式　　正整数（1<=n<=20000）输出格式　　符合约定的n的0，2表示（在表示中不能有空格）样例输入137样例输出2(2(2)+2+2(0))+2(2+2(0))+2(0)样例输入1315样例输出2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)提示　　用递归实现会比较简单，可以一边递归一边输出

  算法训练 前缀表达式   时间限制：1.0s   内存限制：512.0MB     问题描述　　编写一个程序，以字符串方式输入一个前缀表达 式，然后计算它的值。输入格式为：“运算符 对象1 对象2”，其中，运算符为“+”（加法）、“-”（减法）、“*”（乘法）或“/”（除法），运算对象为不超过10的整数，它们之间用一个空格隔开。要 求：对于加、减、乘、除这四种运算，分别设计相应的函数来实现。
　　输入格式：输入只有一行，即一个前缀表达式字符串。
　　输出格式：输出相应的计算结果（如果是除法，直接采用c语言的“/”运算符，结果为整数）。
　　输入输出样例样例输入+ 5 2样例输出7