資源簡介

第六屆分區聯賽提高組復賽
第六屆全國青少年信息學（計算機）奧林匹克分區聯賽提高組復賽試題
2000年12月2日
提高組復賽試題（三小時完成）
題一 進制轉換 (18分)
問題描述:
我們可以用這樣的方式來表示一個十進制數：將每個阿拉伯數字乘以一個以該數字所
處位置的（值減1）為指數，以10為底數的冪之和的形式。例如，123可表示為1*10^2+2*10^1
+3*10^0這樣的形式。
與之相似的，對二進制數來說，也可表示成每個二進制數碼乘以一個以該數字所處位
置的（值-1）為指數，以2為底數的冪之和的形式。一般說來，任何一個正整數R或一
個負整數-R都可以被選來作為一個數制系統的基數。如果是以R或-R為基數，則需要
用到的數碼為0，1,....R-1。例如，當R=7時，所需用到的數碼是0，1，2,
3，4，5和6，這與其是R或-R無關。如果作為基數的數絕對值超過10，則為了表
示這些數碼，通常使用英文字母來表示那些大于9的數碼。例如對16進制數來說，用A
表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。
在負進制數中是用-R作為基數，例如-15（＋進制）相當于110001（-2進制），
并且它可以被表示為2的冪級數的和數：
110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+
0*(-2)^1+1*(-2)^0
問題求解:
設計一個程序，讀入一個十進制數的基數和一個負進制數的基數，并將此十進制數轉換為此負
進制下的數：-R∈{-2，-3，-4,....-20}
輸入:
輸入的每行有兩個輸入數據。
第一個是十進制數N（-32768<=N<=32767）; 第二個是負進制數的基數-R。
輸出:
結果顯示在屏幕上，相對于輸入，應輸出此負進制數及其基數，若此基數超過10，
則參照16進制的方式處理。
樣例:
輸入
30000 -2
-20000 -7
28800 -16
-25000 -16
輸出
30000=1101101010111000(base -2)
-20000=1111011000100000(base -2)
28800=19180(base -16)
-25000=7FB8(base -16)
題二 乘積最大 (22分)
問題描述:
今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先
生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活
動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣
一道題目:
設有一個長度N的數字串，要求選手使用K個乘號將它分成K+1個部分，找出一種
分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：
有一個數字串: 312，當N=3，K=1時會有以下兩種分法：
1）3*12=36
2）31*2=62
這時，符合題目要求的結果是： 31*2=62
現在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。
輸入：
程序的輸入共有兩行:
第一行共有2個自然數N,K (6<=N<=40，1<=K<=6)
第二行是一個K度為N的數字串。
輸出:
結果顯示在屏幕上，相對于輸入，應輸出所求得的最大乘積（一個自然數）。
樣例:
輸入
4 2
1231
輸出
62
題三 單詞接龍 (27分)
問題描述：
單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們己知一組單詞，且
給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍" 中
出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如beast和astonish，如果
接成一條龍則變為beastonish，另外相鄰的兩部分不能存在包含關系，例如at和atide間
不能相連。
輸入:
輸入的第一行為一個單獨的整數n(n<=20）表示單詞數，以下n行每行有一個單詞，輸
入的最后一行為一個單個字符，表來“龍”開頭的字母。你可以假定以此字母開頭的“龍"
一定存在。
輸出:
只需輸出以此字母開頭的最長的“龍”的長度
樣例:
輸入
5
at
touch
cheat
choose
tact
a
輸出
23 （連成的“龍”為atoucheatactactouchoose）
題四 方格取數 (33分)
問題描述:
設有N*N的方格圖(N<=8)，我們將其中的某些方格中填入正整數，而其他的方格中則放
人數字0。如下圖所示（見樣例）：
某人從圖的左上角的A點出發，可以向下行走，也可以向右走，直到到達右下角的B
點。在走過的路上，他可以取走方格中的數（取走后的方格中將變為數字0）。
此人從A點到B點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
輸入:
輸入的第一行為一個整數N（表示N*N的方格圖），接下來的每行有三個整數，前兩個
表示位置，第三個數為該位置上所放的數。一行單獨的0表示輸入結束。
輸出:
只需輸出一個整數，表示2條路徑上取得的最大的和。
樣例:
輸入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
輸出
67

展開更多......

收起↑