全國2008信息學(xué)奧林匹克復(fù)賽普及組

1、全國信息學(xué)奧林匹克聯(lián)賽（NOIP2008）復(fù)賽普及組一.題目概覽中文題目名稱 ISBN號碼 排座椅 傳球游戲 立體圖英文題目名稱 isbn seat ball drawing可執(zhí)行文件名 isbn seat ball drawing輸入文件名 HYPERLINK http:/isbn.in isbn.in HYPERLINK http:/seat.in seat.in HYPERLINK http:/ball.in ball.in HYPERLINK http:/drawing.in drawing.in輸出文件名 isbn.out seat.out ball.out drawing.out每

2、個測試點時限 1秒 1秒 1秒 1秒測試點數(shù)目 10 10 10 10每個測試點分值 10 10 10 10比較方式 全文比較 全文比較 全文比較 全文比較題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng)二.提交源程序文件名對于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三.編譯命令（不包含任何優(yōu)化開關(guān)）對于pascal語言 fpc isbn.pas fpc seat.pas fpc ball.pas

3、 fpc drawing.pas對于C語言 gcc o isbnisbn.c gcc o seatseat.c gcc o ballball.c gcc o drawingdrawing.c對于C+語言 g+ o isbnisbn.cpp g+ o seatseat.cpp g+ o ballball.cpp g+ o drawingdrawing.cpp四.運行內(nèi)存限制運行內(nèi)存上限 50M 50M 50M 50M注意事項：1、文件名（程序名和輸入輸出文件名）必須使用小寫。2、C/C+中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為

4、：CPU 1.9GHz， 內(nèi)存512M， 上述時限以此配置為準。各省在自測時可根據(jù)具體配置調(diào)整時限。1.ISBN號碼（isbn.pas/c/cpp）【問題描述】每一本正式出版的圖書都有一個ISBN號碼與之對應(yīng)，ISBN碼包括9位數(shù)字、1位識別碼和3位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”，其中符號“-”是分隔符（鍵盤上的減號），最后一位是識別碼，例如0-670-82162-4就是一個標準的ISBN碼。ISBN碼的首位數(shù)字表示書籍的出版語言，例如0代表英語；第一個分隔符“-”之后的三位數(shù)字代表出版社，例如670代表維京出版社；第二個分隔之后的五位數(shù)字代表該書在出版社的編號；最后一位為

5、識別碼。識別碼的計算方法如下：首位數(shù)字乘以1加上次位數(shù)字乘以2以此類推，用所得的結(jié)果mod 11，所得的余數(shù)即為識別碼，如果余數(shù)為10，則識別碼為大寫字母X。例如ISBN號碼0-670-82162-4中的識別碼4是這樣得到的：對067082162這9個數(shù)字，從左至右，分別乘以1，2，9，再求和，即01+62+29=158，然后取158 mod 11的結(jié)果4作為識別碼。你的任務(wù)是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出你認為是正確的ISBN號碼?！据斎搿枯斎胛募?HYPERLINK http:/isbn.in isbn.in只有一行，是一

6、個字符序列，表示一本書的ISBN號碼（保證輸入符合ISBN號碼的格式要求）。【輸出】輸出文件isbn.out共一行，假如輸入的ISBN號碼的識別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的ISBN號碼（包括分隔符“-”）。【輸入輸出樣例1】 HYPERLINK http:/isbn.in isbn.in isbn.out0-670-82162-4 Right【輸入輸出樣例2】 HYPERLINK http:/isbn.in isbn.in isbn.out0-670-82162-0 0-670-82162-42.排座椅（seat.pas/c/cpp）【問題描述】 上課的時候

7、總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當同學(xué)們的座次確定下來之后，只有有限的D對同學(xué)上課時會交頭接耳。同學(xué)們在教室中坐成了M行N列，坐在第i行第j列的同學(xué)的位置是（i，j），為了方便同學(xué)們進出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個辦法，或許可以減少上課時學(xué)生交頭接耳的問題：她打算重新擺放桌椅，改變同學(xué)們桌椅間通道的位置，因為如果一條通道隔開了兩個會交頭接耳的同學(xué)，那么他們就不會交頭接耳了。請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學(xué)生對數(shù)最少?！据斎?/p>

8、】輸入文件 HYPERLINK http:/seat.in seat.in的第一行，有5各用空格隔開的整數(shù)，分別是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。接下來D行，每行有4個用空格隔開的整數(shù)，第i行的4個整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個同學(xué)會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。輸入數(shù)據(jù)保證最優(yōu)方案的唯一性?！据敵觥枯敵鑫募eat.out共兩行。第一行包含K個整數(shù)，a1a2aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、第aK行和第aK+1行之間要開辟通道，其中ai ai+1，每兩個整

9、數(shù)之間用空格隔開（行尾沒有空格）。第二行包含L個整數(shù)，b1b2bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、第bL列和第bL+1列之間要開辟通道，其中bi2-3-1和1-3-2-1，共2種?！据斎搿枯斎胛募?HYPERLINK http:/ball.in ball.in共一行，有兩個用空格隔開的整數(shù)n，m（3=n=30，1=m=30）?！据敵觥枯敵鑫募all.out共一行，有一個整數(shù)，表示符合題意的方法數(shù)。【輸入輸出樣例】 HYPERLINK http:/ball.in ball.in ball.out3 3 2【限制】40%的數(shù)據(jù)滿足：3=n=30，1=m=20100%的

10、數(shù)據(jù)滿足：3=n=30，1=m=304.立體圖（drawing.pas/c/cpp）【問題描述】小淵是個聰明的孩子，他經(jīng)常會給周圍的小朋友們講些自己認為有趣的內(nèi)容。最近，他準備給小朋友們講解立體圖，請你幫他畫出立體圖。小淵有一塊面積為m*n的矩形區(qū)域，上面有m*n個邊長為1的格子，每個格子上堆了一些同樣大小的吉姆（積木的長寬高都是1），小淵想請你打印出這些格子的立體圖。我們定義每個積木為如下格式，并且不會做任何翻轉(zhuǎn)旋轉(zhuǎn)，只會嚴格以這一種形式擺放：+-+/ /| 高+-+ | | +| |/ 寬+-+長每個頂點用1個加號+表示，長用3個”-“表示，寬用1個”/”表示，高用兩個”|”表示。字符+

11、-/ |的ASCII碼分別為43，45，47，124。字符.（ASCII碼46）需要作為背景輸出，即立體圖里的空白部分需要用.代替。立體圖的畫法如下面的規(guī)則：若兩塊積木左右相鄰，圖示為：.+-+-+./ / /|+-+-+ | | | +| | |/.+-+-+.若兩塊積木上下相鄰，圖示為：.+-+./ /|+-+ | | +| |/|+-+ | | +| |/.+-+.若兩塊積木前后相鄰，圖示為：.+-+/ /|.+-+ |./ /| +-+ |/.| | +.| |/+-+.立體圖中，定義位于第(m,1)的格子（即第m行第1列的格子）上面自底向上的第一塊積木（即最下面的一塊積木）的左下角頂

12、點為整張圖最左下角的點?！据斎搿枯斎胛募?HYPERLINK http:/drawing.in drawing.in第一行有用空格隔開的兩個整數(shù)m和n，表示有m*n個格子（1=m，n=50）。接下來的m行，是一個m*n的矩陣，每行有n個用空格隔開的整數(shù)，其中第i行第j列上的整數(shù)表示第i行第j列的格子上摞有多少個積木（1=每個格子上的積木數(shù)=100）。【輸出】輸出文件drawing.out中包含題目要求的立體圖，是一個K行L列的字符矩陣，其中K和L表示最少需要K行L列才能按規(guī)定輸出立體圖?！据斎胼敵鰳永?HYPERLINK http:/drawing.in drawing.in drawing.out3 42 2 1 22 2 1 13 2