提高組
壹、題目概覽
中文題目名稱 笨小猴 火柴棒等式 傳紙條 雙棧排序
英文題目名稱 word matches message twostack
可執行文件名 word matches message twostack
輸入文件名 word,in matches.in message.in twostack.in
輸出文件名 word.out matches.out message.out twostack.out
每個測試點時限 1秒 1秒 1秒 1秒
測試點數目 10 10 10 10
每個測試點分值 10 10 10 10
比較方式 全文比較 全文比較 全文比較 全文比較
題目類型 傳統 傳統 傳統 傳統
二、提交源程序文件名
對於Pascal語言 word.pas matches.pas message.pas twostack.pas
對於C語言 word.c matches.c message.c twostack.c
對於C++語言 word.cpp matches.cpp message.cpp twostack.cpp
三、編譯命令（不包含任何優化開關）
對於Pascal語言 fpc word.pas fpc matches.pas fpc message.pas fpc twostack.pas
對於C語言 gcc –o word word.c gcc –o matches matches.c gcc –o message message.c gcc –o twostack twostack.c
對於C++語言 g++ -o word word.cpp g++-o matches matches.cpp g++ -o message message.cpp g++ -o twostack twostack.cpp
四、運行內存限制
運行內存上限 50M 50M 50M 50M
註意事項：
1. 文件名（程序名和輸入輸出文件名）必須使用大寫。
2. C/C++中函數main()的返回值類型必須是int，程序正常結束時的返回值必須是0。
3. 全國統壹評測時采用的機器配置為：CPU 1.9GHz，內存512M，上述時限以此配置為準。各省在自測時可根據具體配置調整時限。
1. 笨小猴
(wird.pas/c/cpp)
問題描述
笨小猴的詞匯量很小，所以每次做英語選擇題的時候都很頭疼。但是他找到了壹種方法，經試驗證明，用這種方法去選擇選項的時候選對的幾率非常大！
這種方法的具體描述如下：假設maxn是單詞中出現次數最多的字母的出現次數，minn是單詞中出現次數最少的字母的出現次數，如果maxn-minn是壹個質數，那麽笨小猴就認為這是個Lucky Word，這樣的單詞很可能就是正確的答案。
輸入
輸入文件word.in只有壹行，是壹個單詞，其中只可能出現小寫字母，並且長度小於100。
輸出
輸出文件word.out***兩行，第壹行是壹個字符串，假設輸入的的單詞是Lucky Word，那麽輸出“Lucky Word”，否則輸出“No Answer”；
第二行是壹個整數，如果輸入單詞是Lucky Word，輸出maxn-minn的值，否則輸出0。
輸入輸出樣例1
word.in word.out
error Lucky Word
2
輸入輸出樣例1解釋
單詞error中出現最多的字母r出現了3次，出現次數最少的字母出現了1次，3-1=2，2是質數。
輸入輸出樣例2
word.in word.out
Olympic No Answer
0
輸入輸出樣例2解釋
單詞olympic中出現最多的字母i出現了2次，出現次數最少的字母出現了1次，2-1=1，1不是質數。
2. 火柴棒等式
(matches.pas/c/cpp)
問題描述
給妳n根火柴棍，妳可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數（若該數非零，則最高位不能是0）。用火柴棍拼數字0-9的拼法如圖所示：
註意：
1. 加號與等號各自需要兩根火柴棍
2. 如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）
3. n根火柴棍必須全部用上
輸入
輸入文件matches.in***壹行，又壹個整數n（n<=24）。
輸出
輸出文件matches.out***壹行，表示能拼成的不同等式的數目。
輸入輸出樣例1
matches.in matches.out
14 2
輸入輸出樣例1解釋
2個等式為0+1=1和1+0=1。
輸入輸出樣例2
matches.in matches.out
18 9
輸入輸出樣例2解釋
9個等式為：
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
3. 傳紙條
(wassage.pas/c/cpp)
問題描述
小淵和小軒是好朋友也是同班同學，他們在壹起總有談不完的話題。壹次素質拓展活動中，班上同學安排做成壹個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經由許多同學傳到對方手裏，小淵坐在矩陣的左上角，坐標(1,1)，小軒坐在矩陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。
在活動進行中，小淵希望給小軒傳遞壹張紙條，同時希望小軒給他回復。班裏每個同學都可以幫他們傳遞，但只會幫他們壹次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那麽在小軒遞給小淵的時候就不會再幫忙。反之亦然。
還有壹件事情需要註意，全班每個同學願意幫忙的好感度有高有低（註意：小淵和小軒的好心程度沒有定義，輸入時用0表示），可以用壹個0-100的自然數來表示，數越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度只和最大。現在，請妳幫助小淵和小軒找到這樣的兩條路徑。
輸入
輸入文件message.in的第壹行有2個用空格隔開的整數m和n，表示班裏有m行n列（1<=m,n<=50）。
接下來的m行是壹個m*n的矩陣，矩陣中第i行j列的整數表示坐在第i行j列的學生的好心程度。每行的n個整數之間用空格隔開。
輸出
輸出文件message.out***壹行，包含壹個整數，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。
輸入輸出樣例
message.in message.out
3 3
0 3 9
2 8 5
5 7 0 34
限制
30%的數據滿足：1<=m,n<=10
100%的數據滿足：1<=m,n<=50
4. 雙棧排序
(twostack.pas/c/cpp)
問題描述
Tom最近在研究壹個有趣的排序問題。如圖所示，通過2個棧S1和S2，Tom希望借助以下4種操作實現將輸入序列升序排序。
操作a
如果輸入序列不為空，將第壹個元素壓入棧S1
操作b
如果棧S1不為空，將S1棧頂元素彈出至輸出序列
操作c
如果輸入序列不為空，將第壹個元素壓入棧S2
操作d
如果棧S2不為空，將S2棧頂元素彈出至輸出序列
如果壹個1~n的排列P可以通過壹系列操作使得輸出序列為1，2，…，(n-1)，n，Tom就稱P是壹個“可雙棧排序排列”。例如(1,3,2,4)就是壹個“可雙棧排序序列”，而(2,3,4,1)不是。下圖描述了壹個將(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>
當然，這樣的操作序列有可能有幾個，對於上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外壹個可行的操作序列。Tom希望知道其中字典序最小的操作序列是什麽。
輸入
輸入文件twostack.in的第壹行是壹個整數n。
第二行有n個用空格隔開的正整數，構成壹個1~n的排列。
輸出
輸出文件twostack.out***壹行，如果輸入的排列不是“可雙棧排序排列”，輸出數字0；否則輸出字典序最小的操作序列，每兩個操作之間用空格隔開，行尾沒有空格。
輸入輸出樣例1
twostack.in twostack.out
4
1 3 2 4 a b a a b b a b
輸入輸出樣例2
twostack.in twostack.out
4
2 3 4 1 0
輸入輸出樣例3
twostack.in twostack.out
3
2 3 1 a c a b b d
限制
30%的數據滿足： n<=10
50%的數據滿足： n<=50
100%的數據滿足： n<=1000