資源簡介

1999年全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題
（初中組 競賽用時：3小時）
第一題　Cantor表（30分）
現(xiàn)代數(shù)學(xué)的著名證明之一是Georg Cantor證明了有理數(shù)是可枚舉的。他是用下面這一張
表來證明這一命題的：
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 ...
4/1 4/2 ...
5/1
我們以z字型給上表的每一項編號。第１項是1/1，然后是1/2，2/1，3/1，2/2...
輸入:整數(shù)n(1<=n<=10)
輸出:表中的第N項
樣例:
input: n=7
output: 1/4
　
第二題 回文數(shù)（ 30分）
　　若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回
文數(shù)。例如：給定一個 10進(jìn)制數(shù) 56，將 56加 65（即把56從右向左讀），得到 121是
一個回文數(shù)。又如，對于10進(jìn)制數(shù)87，
STEPl： 87＋78= 165 STEP2： 165＋561= 726
STEP3： 726＋627＝1353 STEP4：1353+3531=4884
　　在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。
　　寫一個程序，給定一個N（2＜n＜＝10，N=16）進(jìn)制數(shù) M．求最少經(jīng)過幾步可以得到
文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Inpossible”
樣例：
INPUT
N＝9 M＝87
Output
STEP=6
　
第三題 旅行家的預(yù)算（40分）
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是
空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）．每升汽油能行
駛的距離D2、出發(fā)點每升汽油價格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點的距
離Di、每升汽油價格 Pi（ i＝l，2，...N）。
計算結(jié)果四舍五入至小數(shù)點后兩位。
如果無法到達(dá)目的地，則輸出“No solution”。
樣例：
INPUT
D1＝275.6 C=11.9 D2＝27.4 P=2.8 N=2
　油站號i 　離出發(fā)點的距離Di　每升汽油價格Pi
　１ 　　102.0 　 29
　２ 　　220.0 　2.2
OUTPUT
26.95（該數(shù)據(jù)表示最小費用）1999年全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題
（高中組 競賽用時：3小時）
第一題 攔截導(dǎo)彈（28分）
　　某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)
有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高
于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以
只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。
　　輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計算
這套系統(tǒng)最多能攔截多少導(dǎo)彈，和如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截
系統(tǒng)。
樣例：
INPUT
389 207 155 300 299 170 158 65
output
6（最多能攔截的導(dǎo)彈數(shù)）
2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）
　
第二題 回文數(shù)（25分）
　　若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回
文數(shù)。例如：給定一個 10進(jìn)制數(shù) 56，將 56加 65（即把56從右向左讀），得到 121是
一個回文數(shù)。又如，對于10進(jìn)制數(shù)87，
STEPl： 87＋78= 165 STEP2： 165＋561= 726
STEP3： 726＋627＝1353 STEP4：1353+3531=4884
　　在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。
　　寫一個程序，給定一個N（2＜n＜＝10，N=16）進(jìn)制數(shù) M．求最少經(jīng)過幾步可以得到
文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Inpossible”
樣例：
INPUT
N＝9 M＝87
Output
STEP=6
　
第三題 旅行家的預(yù)算（27分）
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是
空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）．每升汽油能行
駛的距離D2、出發(fā)點每升汽油價格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點的距
離Di、每升汽油價格 Pi（ i＝l，2，...N）。
計算結(jié)果四舍五入至小數(shù)點后兩位。
如果無法到達(dá)目的地，則輸出“No solution”。
樣例：
INPUT
D1＝275.6 C=11.9 D2＝27.4 P=2.8 N=2
　油站號i 　離出發(fā)點的距離Di　每升汽油價格Pi
　１ 　　102.0 　 29
　２ 　　220.0 　2.2
OUTPUT
26.95（該數(shù)據(jù)表示最小費用）
　
第四題 郵票面值設(shè)計（40分）
給定一個信封，最多只允許粘貼N張郵票，計算在給定K（N+k<=40) 種郵票的情況
下（假定所有的郵票數(shù)量都足夠），如何設(shè)計郵票的面值，能得到最大max ，使得1－
max之間的每一個郵資值都能得到。
例如，N=3，K＝2，如果面值分別為1分、4分，則在l分-6分之間的每一個郵資值
都能得到（當(dāng)然還有8分、9分和12分）：如果面值分別為1分、3分，則在1分-7分之間的
每一個郵資值都能得到。可以驗證當(dāng)N=3，K＝2時，7分就是可以得到連續(xù)的郵資最大值
，所以MAX=7，面值分別為l分、3分。
樣例：
INPUT
N=3 k=2
Output
1 3
max=71999年全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽普及組復(fù)賽題測試數(shù)據(jù)及參考答案
第一題 30分
序號 N 輸出 分值
1 15 1/5 5
2 85 7/7 5
3 1999 18/46 10
4 10278 19/125 10
第二題 30分
序號 N M Step 分值
1 2 10011 4 5
2 16 AC27 6 9
3 10 89 24 10
4 2 101111 Impossible! 6
第三題 40分
序號 輸入 輸出 分值
1 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 334.90 10
2 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 No Solution. 5
100.0 99.9
3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 105.95 12
22.10 7.38
24.21 6.81
82.08 6.96
4 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 192.15 13
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.091999年全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽提高組復(fù)賽題測試數(shù)據(jù)及參考答案
第一題 28分
序號 輸入
1 300,250,275,252,200,138,245
2 181,205,471,782,1033,1058,1111
3 465,978,486,476,324,575,384,278,214,657,218,445,123
4 236,865,858,565,545,445,455,656,844,735,638,652,569,714,845
序號 單枚最大可擊落導(dǎo)彈數(shù) 需要系統(tǒng)數(shù) 分值
1 5 2 5
2 1 7 5
3 7 4 10
4 6 7 8
第二題 25分
序號 N M Step 分值
1 2 10011 4 4
2 16 AC27 6 7
3 10 89 24 9
4 2 101111 Impossible! 5
第三題 27分
序號 輸入 輸出 分值
1 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 334.90 5
2 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 No Solution. 5
100.0 99.9
3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 105.95 7
22.10 7.38
24.21 6.81
82.08 6.96
4 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 192.15 10
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.09
第四題 40分
序號 N K STEP 分值
1 7 3 1，8，13， MAX=69 10
2 7 4 1，5，24，37， MAX=165 10
3 10 3 1，10，28， MAX=146 10
4 5 5 1，4，9，31，51 MAX=126 10

展開更多......

收起↑