普及組
壹.題目概覽
中文題目名稱 ISBN號碼 排座椅 傳球遊戲 立體圖
英文題目名稱 isbn seat ball drawing
可執行文件名 isbn seat ball drawing
輸入文件名 isbn.in seat.in ball.in drawing.in
輸出文件名 isbn.out seat.out ball.out drawing.out
每個測試點時限 1秒 1秒 1秒 1秒
測試點數目 10 10 10 10
每個測試點分值 10 10 10 10
比較方式 全文比較 全文比較 全文比較 全文比較
題目類型 傳統 傳統 傳統 傳統
二.提交源程序文件名
對於pascal語言 isbn.pas seat.pas ball.pas drawing.pas
對於C語言 isbn.c seat.c ball.c drawing.c
對於C++語言 isbn.cpp seat.cpp ball.cpp drawing.cpp
三.編譯命令（不包含任何優化開關）
對於pascal語言 fpc isbn.pas fpc seat.pas fpc ball.pas fpc drawing.pas
對於C語言 gcc –o isbn
isbn.c gcc –o seat
seat.c gcc –o ball
ball.c gcc –o drawing
drawing.c
對於C++語言 g++ –o isbn
isbn.cpp g++ –o seat
seat.cpp g++ –o ball
ball.cpp g++ –o
drawing
drawing.cpp
四.運行內存限制
運行內存上限 50M 50M 50M 50M
註意事項：
1、文件名（程序名和輸入輸出文件名）必須使用小寫。
2、C/C++中函數main（）的返回值類型必須是int，程序正常結束時的返回值必須是0。
3、全國統壹評測時采用的機器配置為：CPU 1.9GHz， 內存512M， 上述時限以此配置為準。
各省在自測時可根據具體配置調整時限。
1.ISBN號碼
（isbn.pas/c/cpp）
問題描述
每壹本正式出版的圖書都有壹個ISBN號碼與之對應，ISBN碼包括9位數字、1位識別碼和3位分隔符，其規定格式如“x-xxx-xxxxx-x”，其中符號“-”是分隔符（鍵盤上的減號），最後壹位是識別碼，例如0-670-82162-4就是壹個標準的ISBN碼。ISBN碼的首位數字表示書籍的出版語言，例如0代表英語；第壹個分隔符“-”之後的三位數字代表出版社，例如670代表維京出版社；第二個分隔之後的五位數字代表該書在出版社的編號；最後壹位為識別碼。
識別碼的計算方法如下：
首位數字乘以1加上次位數字乘以2……以此類推，用所得的結果mod 11，所得的余數即為識別碼，如果余數為10，則識別碼為大寫字母X。例如ISBN號碼0-670-82162-4中的識別碼4是這樣得到的：對067082162這9個數字，從左至右，分別乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然後取158 mod 11的結果4作為識別碼。
妳的任務是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出妳認為是正確的ISBN號碼。
輸入
輸入文件isbn.in只有壹行，是壹個字符序列，表示壹本書的ISBN號碼（保證輸入符合ISBN號碼的格式要求）。
輸出
輸出文件isbn.out***壹行，假如輸入的ISBN號碼的識別碼正確，那麽輸出“Right”，否則，按照規定的格式，輸出正確的ISBN號碼（包括分隔符“-”）。
輸入輸出樣例1
isbn.in isbn.out
0-670-82162-4 Right
輸入輸出樣例2
isbn.in isbn.out
0-670-82162-0 0-670-82162-4
2.排座椅
（seat.pas/c/cpp）
問題描述
上課的時候總有壹些同學和前後左右的人交頭接耳，這是令小學班主任十分頭疼的壹件事情。不過，班主任小雪發現了壹些有趣的現象，當同學們的座次確定下來之後，只有有限的D對同學上課時會交頭接耳。同學們在教室中坐成了M行N列，坐在第i行第j列
的同學的位置是（i，j），為了方便同學們進出，在教室中設置了K條橫向的通道，L條縱向的通道。於是，聰明的小雪想到了壹個辦法，或許可以減少上課時學生交頭接耳的問題：她打算重新擺放桌椅，改變同學們桌椅間通道的位置，因為如果壹條通道隔開了兩個會交頭接耳的同學，那麽他們就不會交頭接耳了。
請妳幫忙給小雪編寫壹個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學生對數最少。
輸入
輸入文件seat.in的第壹行，有5各用空格隔開的整數，分別是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。
接下來D行，每行有4個用空格隔開的整數，第i行的4個整數Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個同學會交頭接耳（輸入保證他們前後相鄰或者左右相鄰）。
輸入數據保證最優方案的唯壹性。
輸出
輸出文件seat.out***兩行。
第壹行包含K個整數，a1a2……aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、…、第aK行和第aK+1行之間要開辟通道，其中ai< ai+1，每兩個整數之間用空格隔開（行尾沒有空格）。
第二行包含L個整數，b1b2……bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、…、第bL列和第bL+1列之間要開辟通道，其中bi< bi+1，每兩個整數之間用空格隔開（行尾沒有空格）。
輸入輸出樣例
seat.in seat.out
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4 2
2 4
輸入輸出樣例解釋
* *
※
※ + +
1 2 3 4 5
上圖中用符號*、※、+ 標出了3對會交頭接耳的學生的位置，圖中3條粗線的位置表示通道，圖示的通道劃分方案是唯壹的最佳方案。
3.傳球遊戲
（ball.pas/c/cpp）
問題描述
上體育課的時候，小蠻的老師經常帶著同學們壹起做遊戲。這次，老師帶著同學們壹起做傳球遊戲。
遊戲規則是這樣的：n個同學站成壹個圓圈，其中的壹個同學手裏拿著壹個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的壹個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演壹個節目。
聰明的小蠻提出壹個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手裏開始傳的球，傳了m次以後，又回到小蠻手裏。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，並假設小蠻為1號，球傳了3次回到小蠻手裏的方式有1->2->3->1和1->3->2->1，***2種。
輸入
輸入文件ball.in***壹行，有兩個用空格隔開的整數n，m（3<=n<=30，1<=m<=30）。
輸出
輸出文件ball.out***壹行，有壹個整數，表示符合題意的方法數。
輸入輸出樣例
ball.in ball.out
3 3 2
限制
40%的數據滿足：3<=n<=30，1<=m<=20
100%的數據滿足：3<=n<=30，1<=m<=30
4.立體圖
（drawing.pas/c/cpp）
問題描述
小淵是個聰明的孩子，他經常會給周圍的小朋友們講些自己認為有趣的內容。最近，他準備給小朋友們講解立體圖，請妳幫他畫出立體圖。
小淵有壹塊面積為m*n的矩形區域，上面有m*n個邊長為1的格子，每個格子上堆了壹些同樣大小的積木（積木的長寬高都是1），小淵想請妳打印出這些格子的立體圖。我們定義每個積木為如下格式，並且不會做任何翻轉旋轉，只會嚴格以這壹種形式擺放：
+---+
/ /| 高
+---+ |
| | +
| |/ 寬
+---+
長
每個頂點用1個加號’+’表示，長用3個”-“表示，寬用1個”/”表示，高用兩個”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII碼分別為43，45，47，124。字符’.’（ASCII碼46）需要作為背景輸出，即立體圖裏的空白部分需要用’.’代替。立體圖的畫法如下面的規則：
若兩塊積木左右相鄰，圖示為：
..+---+---+
./ / /|
+---+---+ |
| | | +
| | |/.
+---+---+..
若兩塊積木上下相鄰，圖示為：
..+---+
./ /|
+---+ |
| | +
| |/|
+---+ |
| | +
| |/.
+---+..
若兩塊積木前後相鄰，圖示為：
….+---+
…/ /|
..+---+ |
./ /| +
+---+ |/.
| | +..
| |/…
+---+….
立體圖中，定義位於第(m,1)的格子（即第m行第1列的格子）上面自底向上的第壹塊積木（即最下面的壹塊積木）的左下角頂點為整張圖最左下角的點。
輸入
輸入文件drawing.in第壹行有用空格隔開的兩個整數m和n，表示有m*n個格子（1<=m，n<=50）。
接下來的m行，是壹個m*n的矩陣，每行有n個用空格隔開的整數，其中第i行第j列上的整數表示第i行第j列的格子上摞有多少個積木（1<=每個格子上的積木數<=100）。
輸出
輸出文件drawing.out中包含題目要求的立體圖，是壹個K行L列的字符矩陣，其中K和L表示最少需要K行L列才能按規定輸出立體圖。
輸入輸出樣例
drawing.in drawing.out
3 4
2 2 1 2
2 2 1 1
3 2 1 2 ......+---+---+...+---+
..+---+ / /|../ /|
./ /|-+---+ |.+---+ |
+---+ |/ /| +-| | +
| | +---+ |/+---+ |/|
| |/ /| +/ /|-+ |
+---+---+ |/+---+ |/| +
| | | +-| | + |/.
| | |/ | |/| +..
+---+---+---+---+ |/...
| | | | | +....
| | | | |/.....
+---+---+---+---+......
全國信息學奧林匹克聯賽（NOIP2008）復賽
提高組
壹、題目概覽
中文題目名稱 笨小猴 火柴棒等式 傳紙條 雙棧排序
英文題目名稱 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