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

1、第四屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第四屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時(shí)：競賽用時(shí)：3 小時(shí)）小時(shí)）1火車從始發(fā)站（稱為第 1 站）開出，在始發(fā)站上車的人數(shù)為 a，然后到達(dá)第 2 站，在第2 站有人上、下車，但上、下車的人數(shù)相同，因此在第 2 站開出時(shí)（即在到達(dá)第 3 站之前）車上的人數(shù)保持為 a 人。從第 3 站起（包括第 3 站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點(diǎn)站的前一站（第 n-1 站） ，都滿足此規(guī)律?，F(xiàn)給出的條件是：共有 N 個(gè)車站，始發(fā)站上車的人數(shù)

2、為 a，最后一站下車的人數(shù)是 m（全部下車） 。試問 x 站開出時(shí)車上的人數(shù)是多少？ 輸入：a，n，m 和 x 輸出：從 x 站開出時(shí)車上的人數(shù)。 20%2設(shè)有 n 個(gè)正整數(shù)（n20） ，將它們聯(lián)接成一排，組成一個(gè)最大的多位整數(shù)。例如：n=3 時(shí)，3 個(gè)整數(shù) 13，312，343 聯(lián)接成的最大整數(shù)為：34331213又如：n=4 時(shí)，4 個(gè)整數(shù) 7，13，4，246 聯(lián)接成的最大整數(shù)為：7424613程序輸入：n n 個(gè)數(shù)程序輸出：聯(lián)接成的多位數(shù) 40%3著名科學(xué)家盧斯為了檢查學(xué)生對進(jìn)位制的理解，他給出了如下的一張加法表，表中的字母代表數(shù)字。 例如： 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 根據(jù)這些規(guī)則可推導(dǎo)出：L=0，K=1，V=2，E=3 同時(shí)可以確定該表表示的是 4 進(jìn)制加法程序輸入： n（n9）表示行數(shù)。以下 n 行，每行包括 n 個(gè)字符串，每個(gè)字串間用空格隔開。 （字串僅有一個(gè)為+號，其它都由大寫字母組成）+LKVELLKVEKKVEKLVVEKLKKEEKLKK KV程序輸出： 各個(gè)字母表示什么數(shù)，格式如：L=0，K=1， 加法運(yùn)算是幾進(jìn)制的。 若不可能組成加法表，則應(yīng)輸出“ERROR！”第四屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽第四屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)

4、賽參考答案（高中組）復(fù)賽參考答案（高中組） 題號輸入輸出分值得分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二進(jìn)制5 分3.2N=4+

5、M N PM N MP MN MP MM NP M N PM=1 l=2 P=0三進(jìn)制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五進(jìn)制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七進(jìn)制15 分總計(jì)=20+40+40=100 分NOI 分區(qū)聯(lián)賽分區(qū)聯(lián)賽 - 1998 年第四屆高中組試題年第四屆高中組試題解析解析注意：解析和源程序均為 OIBH 站長劉汝佳所寫，疏漏在所難免，但至少程序均通過了比賽時(shí)使用的測試數(shù)據(jù)，所以還是可以一看。1.火車從始發(fā)站(稱為第 1 站)開出,在始發(fā)站上車的人數(shù)為 a,然后到達(dá)第 2 站,在第 2 站有人上、下車,但上、下車的人數(shù)相同，因此在第 2 站開出時(shí)（即在到達(dá)第 3 站之前）車上的人數(shù)保持為a 人。從第 3 站起（包括第 3 站）上、下車的人數(shù)有一定的規(guī)律：上車的人數(shù)都是前

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

8、數(shù)為 fk-2a+fk-1b (fk=1,1,2,3,5,8,13,21.為 fibonacci 數(shù)列)容易證明，自己試一下吧。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)因?yàn)橹赖?n-1 站開車時(shí)人數(shù)為 m,容易求出 b,再代入(1)求第 x 站開車時(shí)的人數(shù) p。即：m=(fn-3+1)a + (fn-2-1)b (2)p=(fx-2+1)a + (fx-1-1)b (3)從(2)解得 b,代入(3)計(jì)算知p

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

10、到小連接，因?yàn)轭}目的例子都符合，但是不難找到反例：12 121 應(yīng)該組成 12121 而非 12112,那么是不是相互包含的時(shí)候就從小到大呢？也不一定，如：12 123 就是 12312 而非 12112,那么情況就多了。其實(shí)本題就是用貪心法，但是貪心標(biāo)準(zhǔn)不是上述那種，而是：如果 a 后接 b 比 b 后接 a 大，就說ab。直接輸出排序結(jié)果。正確性容易證明,大家自己試試。程序見附件。3.(40%)著名科學(xué)家盧斯為了檢查學(xué)生對進(jìn)位制的理解,他給出了如下的一張加法表,表中的字母代表數(shù)字.(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根據(jù)這些規(guī)則可推導(dǎo)出:L=