資源簡介

全國信息學奧林匹克競賽（NOIP2008）復賽 普及組
全國信息學奧林匹克競賽（NOIP2008）復賽
普及組
題目概覽
中文題目名稱 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
注意事項：
文件名（程序名和輸入輸出文件名）必須使用小寫。
C/C++中函數main()的返回值類型必須是int，程序正常結束時的返回值必須是0。
全國統一評測時采用的機器配置為：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接下來的D行，每行有4個用空格隔開的整數。第i行的4個整數Xi，Yi，Pi，Qi，表示坐在位置(Xi，Yi)與(Pi，Qi)的兩個同學會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。
輸入數據保證最優方案的唯一性。
【輸出】
輸出文件seat.out共兩行。
第一行包含K個整數，a1，a2……aK，表示第a1行和a1+1行之間、第a2行和a2+1行之間、…、第aK行和第aK+1行之間要開辟通道，其中ai< ai+1，每兩個整數之間用空格隔開（行尾沒有空格）。
第二行包含L個整數，b1，b2……bL，表示第b1列和b1+1列之間、第b2列和b2+1列之間、…、第bL列和第bL+1列之間要開辟通道，其中bi< bi+1，每兩個整數之間用空格隔開（列尾沒有空格）。
【輸入輸出樣例】
seat.in seat.out
4 5 1 2 34 2 4 32 3 3 32 5 2 4 22 4
【輸入輸出樣例解釋】
上圖中用符號*、※、+標出了3對會交頭接耳的學生的位置，圖中3條粗線的位置表示通道，圖示的通道劃分方案是唯一的最佳方案。
3. 傳球游戲
(ball.pas/c/cpp)
【問題描述】
上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。
游戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師在此吹哨子時，傳球停止，此時，拿著球沒有傳出去的那個同學就是敗者，要給大家表演一個節目。
聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有三個同學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第一行有用空格隔開的2個整數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 42 2 1 22 2 1 13 2 1 2
第4頁 共6頁

展開更多......

收起↑