1、第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時）1火車從始發站（稱為第 1 站）開出，在始發站上車的人數為 a，然后到達第 2 站，在第2 站有人上、下車，但上、下車的人數相同，因此在第 2 站開出時（即在到達第 3 站之前）車上的人數保持為 a 人。從第 3 站起（包括第 3 站）上、下車的人數有一定規律：上車的人數都是前兩站上車人數之和，而下車人數等于上一站上車人數，一直到終點站的前一站（第 n-1 站） ，都滿足此規律。現給出的條件是：共有 N 個車站，始發站上車的人數

2、為 a，最后一站下車的人數是 m（全部下車） 。試問 x 站開出時車上的人數是多少？ 輸入：a，n，m 和 x 輸出：從 x 站開出時車上的人數。 20%2設有 n 個正整數（n20） ，將它們聯接成一排，組成一個最大的多位整數。例如：n=3 時，3 個整數 13，312，343 聯接成的最大整數為：34331213又如：n=4 時，4 個整數 7，13，4，246 聯接成的最大整數為：7424613程序輸入：n n 個數程序輸出：聯接成的多位數 40%3著名科學家盧斯為了檢查學生對進位制的理解，他給出了如下的一張加法表，表中的字母代表數字。 例如： 40%其含義為：L+L=L，L+K=K，L

3、+V=V，L+E=EK+L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根據這些規則可推導出：L=0，K=1，V=2，E=3 同時可以確定該表表示的是 4 進制加法程序輸入： n（n9）表示行數。以下 n 行，每行包括 n 個字符串，每個字串間用空格隔開。 （字串僅有一個為+號，其它都由大寫字母組成）+LKVELLKVEKKVEKLVVEKLKKEEKLKK KV程序輸出： 各個字母表示什么數，格式如：L=0，K=1， 加法運算是幾進制的。 若不可能組成加法表，則應輸出“ERROR！”第四屆全國青少年信息學（計算機）奧林匹克分區聯賽第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復

4、賽參考答案（高中組）復賽參考答案（高中組） 題號輸入輸出分值得分1.15 7 32 4135 分1.20 10 40 685 分1.310 15 2378 813810 分2.13121 21 33 2 1 1 2 1 5 分2.2413 24 75 427 5 4 2 2 4 1 310 分2.341341 133 1321 373 7 1 3 4 1 1 3 3 1 3 2 110 分2.46321 32 407 135 13 2174 0 7 3 2 3 2 1 2 1 7 1 3 5 1 3 15 分3.1N=3+ M LM ML ML M LM=1 L=0二進制5 分3.2N=4+

5、M N PM N MP MN MP MM NP M N PM=1 l=2 P=0三進制10 分3.3N=6+ M L K N HM L H M MK NL H N L MM MKK M L K N HN MK MM N MH MLH N MK H ML MMM=1 l=2 k=0 n=4 h=3五進制10 分3.4N=8+ M N L P Q R S M S LL P R M LQ NN LL LR LQ LM N LS LPL P LQ M S L N R P R LM S N P LL LQQ M N L P Q R S R LQ LS N LL R LP LMS N LP R LQ S

6、LM LL M=2 N=6 L=1 P=3 Q=0R=5 S=4七進制15 分總計=20+40+40=100 分NOI 分區聯賽分區聯賽 - 1998 年第四屆高中組試題年第四屆高中組試題解析解析注意：解析和源程序均為 OIBH 站長劉汝佳所寫，疏漏在所難免，但至少程序均通過了比賽時使用的測試數據，所以還是可以一看。1.火車從始發站(稱為第 1 站)開出,在始發站上車的人數為 a,然后到達第 2 站,在第 2 站有人上、下車,但上、下車的人數相同，因此在第 2 站開出時（即在到達第 3 站之前）車上的人數保持為a 人。從第 3 站起（包括第 3 站）上、下車的人數有一定的規律：上車的人數都是前

7、兩站上車人數之和，而下車人數等于上一站上車人數，一直到終點站的前一站（第 n-1 站），都滿足此規律。現給出的條件是：共有 N 個車站，始發站上車的人數為 a,最后一站下車的人數是 m（全部下車）。試問從 x 站開出時車上的人數是多少？輸入：a,n,m 和 x輸出：x 站開出時車上的人數(20%)分析典型的數學題。為了找規律，我們建立一個表。站號 1 2 3 4 5 6開車時人數 num a a 2a 2a+b 3a+2b 4a+4b上車人數 in a b a+b a+2b 2a+3b 3a+5b下車人數 out 0 b b a+b a+2b 2a+3b規律出來了，設第 k(k=3)站時上車人

8、數為 fk-2a+fk-1b (fk=1,1,2,3,5,8,13,21.為 fibonacci 數列)容易證明，自己試一下吧。numk=a+in2-out2+in3-out3.+ink-outk而 in2=out3,in3=out4.故 numk=a-out2+ink=a-b+fk-2a+fk-1b= (fk-2+1)a + (fk-1-1)b (1)因為知道第 n-1 站開車時人數為 m,容易求出 b,再代入(1)求第 x 站開車時的人數 p。即：m=(fn-3+1)a + (fn-2-1)b (2)p=(fx-2+1)a + (fx-1-1)b (3)從(2)解得 b,代入(3)計算知p

9、=(fx-2+1)*a+(fx-1-1)*(m-(fn-3+1)*a) div (fn-2-1);程序就只有 10 行了。注意 f24用 integer 裝不下了，故只遞推到 f23。當然，你用枚舉也可以，不過不如這種方法吸引人。2.設有 n 個正整數,將他們連接成一排,組成一個最大的多位整數.例如:n=3 時,3 個整數 13,312,343,連成的最大整數為:34331213又如:n=4 時,4 個整數 7,13,4,246 連接成的最大整數為 7424613程序輸入:N N 個數程序輸出:連接成的多位數(40%)分析這是一道比較成功的題目。極易想到的算法是貪心法 - 按整數對應的字符串大

10、到小連接，因為題目的例子都符合，但是不難找到反例：12 121 應該組成 12121 而非 12112,那么是不是相互包含的時候就從小到大呢？也不一定，如：12 123 就是 12312 而非 12112,那么情況就多了。其實本題就是用貪心法，但是貪心標準不是上述那種，而是：如果 a 后接 b 比 b 后接 a 大，就說ab。直接輸出排序結果。正確性容易證明,大家自己試試。程序見附件。3.(40%)著名科學家盧斯為了檢查學生對進位制的理解,他給出了如下的一張加法表,表中的字母代表數字.(40%)例如:+LKVELLKVEKKVEKLVVEKLKKEEKLKKKV其含義為:L+L=L,L+K=K,L+V=V,L+E=E,K+L=K,K+K=V,K+V=E,K+E=KL,.E+E=KV根據這些規則可推導出:L=