算法訓練 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