1、第五屆全國青少年信息學（計算機）奧林匹克分區聯賽普及組復賽試題2007-4-3 9:07:34      閱讀27次第一題：Cantor表現代數學的著名證明之一是Georg Cantor證明了有理數是可枚舉的。他是用下面一張表來證明這一名題的：1/21/2 1/31/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、1/3、1/4、2/3。編程輸入項號N（1<=N<=1000000），輸出表中第N

2、項。例：輸入：N=7輸出：1/4 第二題回文數若一個數（首位不為零）從左到右讀與從右到左讀都是一樣，我們就將其稱之為回文數。例如：給定一個10進制數56，將56加65（即把56從右向左讀），得到121是一個會文數。又如，對于10進制數87：STEP1:87+78=165 STEP2:165+561=726STEP3:726+627=1353 STEP4:1353+3531=4884在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數4884。寫一個程序，給定一個N（2<=N<=10,N=16）進制數M，求最少經過幾步可以得到回文數。如果在30步以內（包含30步）不可能

3、得到回文數，則輸出"Impossible!"樣例：INPUTN=9 M=87OUTPUTSTEP=6 第三題旅行家的預算一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱是空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發點每升汽油價格P和沿途油站數N（N可以為零），油站i離出發點的距離Di、每升汽油價格Pi（i=1,2,.N）。計算結果四舍五入至小數點后兩位。如果無法到達目的地，則輸出"No Solution"。樣例：INPUTD1=275.6 C=11.9 D2=27.4 P=2.8

4、 N=2油站號I離出發點的距離Di每升汽油價格Pi1102.02.92220.02.2OUTPUT26.95（該數據表示最小費用） -1999年第五屆全國青少年信息學（計算機）奧林匹克分區聯賽提高組復賽試題（上機編程，三小時完成）第一題攔截導彈（28分）某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高度（雷達給出的高速數據是不大于30000的正整數），計算這

5、套系統最多能攔截多少導彈，和如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。樣例：INPUT389 207 155 300 299 170 158 65OUTPUT6（最多能攔截的導彈數）2（要攔截所有導彈最少要配備的系統數） 第二題回文數（25分）若一個數（首位不為零）從左到右讀與從右到左讀都是一樣，我們就將其稱之為回文數。例如：給定一個10進制數56，將56加65（即把56從右向左讀），得到121是一個會文數。又如，對于10進制數87：STEP1:87+78=165 STEP2:165+561=726STEP3:726+627=1353 STEP4:1353+3531=4884在這里的

6、一步是指進行了一次N進制的加法，上例最少用了4步得到回文數4884。寫一個程序，給定一個N（2<=N<=10,N=16）進制數M，求最少經過幾步可以得到回文數。如果在30步以內（包含30步）不可能得到回文數，則輸出"Impossible!"樣例：INPUTN=9 M=87OUTPUTSTEP=6 第三題旅行家的預算（27分）一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱是空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發點每升汽油價格P和沿途油站數N（N可以為零），油站i離出發點的距離Di、

7、每升汽油價格Pi（i=1,2,.N）。計算結果四舍五入至小數點后兩位。如果無法到達目的地，則輸出"No Solution"。樣例：INPUTD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站號I離出發點的距離Di每升汽油價格Pi1102.02.92220.02.2OUTPUT26.95（該數據表示最小費用） 第四題郵票面值設計（40分）給定一個信封，最多只允許粘貼N張郵票，計算在給定K（N|K<=40）種郵票的情況下（假定所有的郵票數量都足夠），如何設計郵票的面值，能得到最大值MAX，使在1MAX之間的每一個郵資值都能得到。例如，N=3，K=2，如果面值分別為1分、4分，則在1分6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）：