第五屆全國(guó)青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽復(fù)賽

1、第五屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第五屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （提（提 高高 組組 競(jìng)賽用時(shí)：競(jìng)賽用時(shí)：3 小時(shí)）小時(shí)）第一題第一題 攔截導(dǎo)彈攔截導(dǎo)彈(28(28 分分) ) 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)） ，計(jì)算這套系統(tǒng)最多能攔截多

2、少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）第二題第二題 回文數(shù)回文數(shù)(25(25 分分) )若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱(chēng)之為回文數(shù)。 例如：給定一個(gè) 10 進(jìn)制數(shù) 56，將 56 加 65（即把 56 從右向左讀） ，得到 121 是一個(gè)回文數(shù)。 又如：對(duì)于 10 進(jìn)制數(shù) 87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627

3、 = 1353 STEP4：1353+3531 = 4884 在這里的一步是指進(jìn)行了一次 N 進(jìn)制的加法，上例最少用了 4 步得到回文數(shù) 4884。 寫(xiě)一個(gè)程序，給定一個(gè) N（2=N=10 或 N=16）進(jìn)制數(shù) M，求最少經(jīng)過(guò)幾步可以得到回文數(shù)。 如果在 30 步以?xún)?nèi)（包含 30 步）不可能得到回文數(shù)，則輸出“Impossible！” 樣例： INPUT OUTPUT N = 9 M= 87 STEP=6第三題第三題 旅行家的預(yù)算旅行家的預(yù)算(27(27 分分) ) 一個(gè)旅行家想駕駛汽車(chē)以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的） 。給定兩個(gè)城市之間的距離 D1、汽車(chē)油箱的容量

4、C（以升為單位） 、每升汽油能行駛的距離 D2、出發(fā)點(diǎn)每升汽油價(jià)格 P 和沿途油站數(shù) N（N 可以為零） ，油站 i 離出發(fā)點(diǎn)的距離 Di、每升汽油價(jià)格Pi（i=1，2，N） 。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無(wú)法到達(dá)目的地，則輸出“No Solution” 。 樣例： INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站號(hào) I離出發(fā)點(diǎn)的距離 Di每升汽油價(jià)格 Pi1102.02.92220.02.2 OUTPUT26.95（該數(shù)據(jù)表示最小費(fèi)用）第四題第四題 郵票面值設(shè)計(jì)郵票面值設(shè)計(jì)(40(40 分分) )給定一個(gè)信封，最多只允許粘貼 N 張郵票，計(jì)算在給定

5、K（N+K40）種郵票的情況下（假定所有的郵票數(shù)量都足夠） ，如何設(shè)計(jì)郵票的面值，能得到最大值 MAX，使在 1MAX 之間的每一個(gè)郵資值都能得到。 例如，N=3，K=2，如果面值分別為 1 分、4 分，則在 1 分6 分之間的每一個(gè)郵資值都能得到（當(dāng)然還有 8 分、9 分和 12 分） ；如果面值分別為 1 分、3 分，則在 1 分7 分之間的每一個(gè)郵資值都能得到?？梢则?yàn)證當(dāng) N=3，K=2 時(shí)，7 分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1 分、3 分。 樣例： INPUT OUTPUT N=3 K=2 1 3MAX=7第六屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)

6、賽復(fù)賽第六屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽（提高組）（提高組） 測(cè)測(cè) 試試 數(shù)數(shù) 據(jù)據(jù)第一題：共 28 分序號(hào)輸入單枚最大可擊落導(dǎo)彈數(shù)需要系統(tǒng)數(shù)分值1300 250 275 252 200 138 2455252181 205 471 782 1033 1058 11111753465 978 486 476 324 575 384278 214 657 218 445 12374104236 865 858 565 545 445 455 656844 735 638 652 659 714 845678第二題：共 25 分序號(hào)NMSTEP分值121001144216AC27

7、673108924942101111Impossible5第三題：共 27 分序號(hào)輸入輸出分值1D1=99.9 C=15.9 D2=29.8 P=99.9 N=0334.9052D1=199.9 C=9.0 D2=10.0 P=99.9 N=1100.0 99.9No solution.53D1=87.75 C=13.03 D2=5.75 P=7.29 N=322.10 7.3824.21 6.8182.08 6.96105.9574D1=475.6 C=11.9 D2=27.4 P=14.98 N=6102.0 9.99220.0 13.29256.3 14.79275.0 10.29277.6 11.29381.8 10.0919