資源簡介

2000年全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題
（初中組 競賽用時：3小時）
題一： 計算器的改良(18分) 問題描述:
NCL是一家專門從事計算器改良與升級的實驗室，最近該實驗室收到了某公司所委托
的一個任務：需要在該公司某型號的計算器上加上解一元一次方程的功能。實驗室將這個任
務交給了一個剛進入的新手ZL先生。為了很好的完成這個任務,ZL先生首先研究了一些
一元一次方程的實例：4+3x=8
6a-5+1=2-2a
-5+12Y=0ZL先生被主管告之，在計算器上鍵入的一個一元一次方程中，只包含整數、小寫字母
及十、一、＝這三個數學符號（當然，符號“一”既可作減號，也可作負號）。方程中并沒
有括號，也沒有除號，方程中的字母表示未知數。問題求解：
編寫程序，解輸入的一元一次方程，將解方程的結果（精確至小數點后三位）輸出至屏幕。你可假設對鍵入的方程的正確性的判斷是由另一個程序員在做，或者說可認為鍵入的一
元一次方程均為合法的，且有唯一實數解。樣例輸入：
6a-5+1=2-2a輸出：
a=0.750
　
題二：稅收與補貼問題(20分) 問題描述：
每樣商品的價格越低，其銷量就會相應增大。現已知某種商品的成本及其在若干價位上
的銷量（產品不會低于成本銷售），并假設相鄰價位間銷量的變化是線性的且在價格高于給
定的最高價位后，銷量以某固定數值遞減。（我們假設價格及銷售量都是整數） 對于某些特殊商品，不可能完全由市場去調節其價格。這時候就需要政府以稅收或補貼
的方式來控制。（所謂稅收或補貼就是對于每個產品收取或給予生產廠家固定金額的貨幣）問題求解： 你是某家咨詢公司的項目經理，現在你已經知道政府對某種商品的預期價格，以及在各
種價位上的銷售情況。要求你確定政府對此商品是應收稅還是補貼的最少金額（也為整數），
才能使商家在這樣一種政府預期的價格上，獲取相對其他價位上的最大總利潤。 總利潤=單位商品利潤*銷量
單位商品利潤=單位商品價格-單位商品成本（-稅金 or +補貼） 輸入：
輸入的第一行為政府對某種商品的預期價，第二行有兩個整數，第一個整數為商品成本，
第二個整數為以成本價銷售時的銷售量，以下若干行每行都有兩個整數，第一個為某價位時
的單價，第二個為此時的銷量，以一行-1，-1表示所有已知價位及對應的銷量輸入完畢，
輸入的最后一行為一個單獨的整數表示在已知的最高單價外每升高一塊錢將減少的銷量。 輸出：
輸出有兩種情況：若在政府預期價上能得到最大總利潤，則輸出一個單獨的整數，數的
正負表示是補貼還是收稅，數的大小表示補貼或收稅的金額最小值。若有多解，取絕對值最
小的輸出。
如在政府預期價上不能得到最大總利潤，則輸出“NO SOLUTION” .樣例：
輸入：
31
28 130
30 120
31 110
-1 -1
15 輸出：
4
　
題三：乘積最大 (26分) 問題描述:今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先
生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活
動，你的一個好朋友XZ也有幸得以參加?；顒又校鞒秩私o所有參加活動的選手出了這樣
一道題目:設有一個長度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
　
題四：單詞接龍 (36分) 問題描述：
單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們己知一組單詞，且
給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍" 中
出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如beast和astonish，如果
接成一條龍則變為beastonish，另外相鄰的兩部分不能存在包含關系，例如at和atide間
不能相連。輸入:
輸入的第一行為一個單獨的整數n(n<=20）表示單詞數，以下n行每行有一個單詞，輸
入的最后一行為一個單個字符，表來“龍”開頭的字母。你可以假定以此字母開頭的“龍"
一定存在。輸出:
只需輸出以此字母開頭的最長的“龍”的長度樣例:輸入
5
at
touch
cheat
choose
tact
a輸出
23 （連成的“龍”為atoucheatactactouchoose）
　2000年復賽普及組測試數據
第一題:計算器的改良
20+3x=-18
-6+12x=0
47-2=6y+3
-25a+18-2=-7a-2
-a+1a-3=a-3
第二題：稅收與補貼問題，輸入見21.in-24.in
第三題：乘積最大
******測試點1******
6 1
101010
******測試點2******
9 4
321044105
******測試點3******
8 3
22222222
******測試點4******
10 5
7777777777
第四題：單詞接龍，見41.in-46.in2000年復賽提高組測試數據
第一題：進制轉換
27993 -8
-37336 -16
-569 -2
-304 -20
683 -2
第二題：乘積最大
******測試點1******
6 1
101010
******測試點2******
9 4
321044105
******測試點3******
8 3
22222222
******測試點4******
10 5
7777777777
第三題：單詞接龍，輸入見31.in-36.in
第四題：方格取數：輸入見41.in-45.in2000年全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題
（高中組 競賽用時：3小時）
題一 進制轉換 (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 -2
28800 -16
-25000 -16輸出
30000=11011010101110000(base -2)
-20000=1111011000100000(base -2)
28800=19180(base -16)
-25000=7FB8(base -16)
　
題二 乘積最大 (22分) 問題描述:今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加?；顒又校鞒秩私o所有參加活動的選手出了這樣一道題目:設有一個長度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　　　　　　　　　13　　6　　　　　　7　　　　　　14　　　　　21　　　4　　　　15　　　　　　14　　　　　　　　　　　　　B某人從圖的左上角的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
　

展開更多......

收起↑