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

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

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

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

4、的條數(shù)。 第三屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽第三屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽參考答案（初中組）復(fù)賽參考答案（初中組） 賽區(qū) 學(xué)校題一輸入輸出實際輸出得分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總計=6+6+6+6+6=30 分題二輸入輸出實際輸出得分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總計=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=