第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)初中聯(lián)賽復(fù)賽

1、第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （初中組（初中組 競(jìng)賽用時(shí)：競(jìng)賽用時(shí)：3 小時(shí)）小時(shí)）1設(shè)有一個(gè) n*m 方格的棋盤（1m,n100） 。 （30%） 求出該棋盤中包含多少個(gè)正方形、多少個(gè)長(zhǎng)方形（不包括正方形） 。 例如：當(dāng) n=2，m=3 時(shí)正方形的個(gè)數(shù)有 8 個(gè)；即邊長(zhǎng)為 1 的正方形有 6 個(gè)； 邊長(zhǎng)為 2 的正方形有 2 個(gè)。長(zhǎng)方形的個(gè)數(shù)有 10 個(gè)； 即 2*1 的長(zhǎng)方形有 4 個(gè)； 1*2 的長(zhǎng)方形有 3 個(gè)； 3*1 的長(zhǎng)方形有 2 個(gè)； 3*2 的長(zhǎng)方形有 1 個(gè)。程序要求：輸入：n 和 m 輸出

2、：正方形的個(gè)數(shù)與長(zhǎng)方形的個(gè)數(shù)如上例：輸入：2 3 輸出：8，102將 1，2，,9 共 9 個(gè)數(shù)排成下列形態(tài)的三角形。 （30%） a b c d e f g h i 其中：ai 分別表示 1，2，,9 中的一個(gè)數(shù)字，并要求同時(shí)滿足下列條件： （1）afi; （2）bd, gh, ce （3）a+b+d+f=f+g+h+i=i+e+c+a=P 程序要求： 根據(jù)輸入的邊長(zhǎng)之和 P 輸出所有滿足上述條件的三角形的個(gè)數(shù)以及其中的一種方案。 3設(shè)有一個(gè) NM（l N50， l M 50）的街道（如下圖）：（40%） 規(guī)定行人從 A(1,1)出發(fā)，在街道上只能向東或北方向行走。 如下為 N3，M=3 的

3、街道圖，從 A 出發(fā)到達(dá) B 共有 6 條可供行走的路徑： A6 A7 B（N，M） A3 A4 A5 A A1 A2 若在 NM 的街道中，設(shè)置一個(gè)矩形障礙區(qū)域（包括圍住該區(qū)域的街道）不讓行人通行，如圖中用“”表示的部分。此矩形障礙區(qū)域用 2 對(duì)頂點(diǎn)坐標(biāo)給出,前圖中的 2 對(duì)頂點(diǎn)坐標(biāo)為:(2，2),(8，4),此時(shí)從 A 出發(fā)到達(dá) B 的路徑僅有兩條。 程序要求： 任務(wù)一：給出 N，M 后，求出所有從 A 出發(fā)到達(dá) B 的路徑的條數(shù)。 任務(wù)二：給出 N，M，同時(shí)再給出此街道中的矩形障礙區(qū)域的 2 對(duì)頂點(diǎn)坐標(biāo)(X1,y1), （X2，Y2） ，然后求出此種情況下所有從 A 出發(fā)到達(dá) B 的路徑

4、的條數(shù)。 第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽參考答案（初中組）復(fù)賽參考答案（初中組） 賽區(qū) 學(xué)校題一輸入輸出實(shí)際輸出得分11N=1，M=11，012N=2，M=25，413N=10，M=10385，2640南*東北54321西1 2 3 4 5 6 7 8 9A（1，1）1.A-A1-A2-A5-B2. A-A1-A4-A5-B3. A-A1-A4-A7-B 4. A-A3-A4-A5-B 5. A-A3-A4-A7-B 6. A-A3-A6-A7-B B（9，5）14N=20，M=204970，9268015N=50，M=50

5、42925，1582700總計(jì)=6+6+6+6+6=30 分題二輸入輸出實(shí)際輸出得分21P=23滿足條件的方案數(shù)：2（如下） 7 7 3 1 2 3 5 6 6 48 2 4 9 8 1 5 922P=18無解23P=19滿足條件的方案數(shù)：4（如下） 1 1 5 3 6 2 9 8 8 9 4 2 6 7 4 3 5 7 2 2 5 4 6 1 9 6 8 9 3 1 8 7 3 4 5 724P=20滿足條件的方案數(shù)：6（如下） 1 2 6 3 6 1 8 7 7 9 5 2 4 9 5 3 4 8 3 2 4 1 7 4 8 9 3 9 5 2 6 7 8 6 1 5 4 4 3 1 2 3 8 9 9 7 5 2 7 6 5 1 8 6總計(jì)=6+4+8+12=30 分題三任 務(wù) 一31N=2，M=2232N=10，M=104862033N=50，M=5058，980，856，902，730，428，600 任 務(wù) 二34N=30，M=40（5，5） ， （15，15）118，200946，737，728，40035N=50，M=