1995-2008 历届NOIP试题及详解(8)

NOIP 1999 普及组 复赛试题

第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（普及组 竞赛用时：3小时）

第一题 Cantor表（30分）

现代数学的著名证明之一是George Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 1/1 1/2 1/3 1/4 1/5 ?

1/1 1/2 1/3 1/4 1/5 ?

2/1 2/2 2/3 2/4 ?

2/1 2/2 2/3 2/4 ? 3/1 3/2 3/3 ?

3/1 3/2 3/3 ? 4/1 4/2 ?

4/1 4/2 ? 5/1 ?

5/1 ? ?

?

我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，?

输入：整数N（1≤N≤10000000） 输出：表中的第N项 样例： INPUT OUTPUT N=7 1/4 第二题 回文数（30分）

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87：

STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（2<=N<=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6 第三题 旅行家的预算（40分）

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，?，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 样例： INPUT

D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号I 1 2 离出发点的距离Di 102.0 220.0 每升汽油价格Pi 2.9 2.2 OUTPUT 26.95（该数据表示最小费用）

第36页 | 共209页

NOIP 1999 普及组 测试数据

第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛

（普及组） 测 试 数 据

第一题：共30分

序号 1 2 3 4

第二题：共30分

序号 1 2 3 4

第三题：共40分 序号 1 2 输入 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 100.0 99.9 3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 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 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 192.15 13 105.95 12 输出 334.90 No solution. 分值 10 5 N 2 16 10 2 M 10011 AC27 89 101111 STEP 4 6 24 Impossible 分值 5 9 10 6 N 15 85 1999 10278 输出 1/5 7/7 18/46 19/125 分值 5 5 10 10 第37页 | 共209页

NOIP 1999 提高组 复赛试题

第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（提 高 组 竞赛用时：3小时）

第一题 拦截导弹(28分)

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例：

INPUT OUTPUT

389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）

2（要拦截所有导弹最少要配备的系统数）

第二题 回文数(25分)

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：

STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M，求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

样例：

INPUT OUTPUT N = 9 M= 87 STEP=6

第三题 旅行家的预算(27分)

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距

第38页 | 共209页

NOIP 1999 提高组 复赛试题

离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，??N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 样例： INPUT

D1=275.6 C=11.9 D2=27.4 P=2.8 N=2

油站号I 1 2 离出发点的距离Di 102.0 220.0 每升汽油价格Pi 2.9 2.2

OUTPUT

26.95（该数据表示最小费用）

第四题 邮票面值设计(40分)

给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。

例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。

样例：

INPUT OUTPUT N=3 K=2 1 3 MAX=7

第39页 | 共209页

NOIP 1999 提高组 测试数据

第六届全国青少年信息学（计算机）奥林匹克分区联赛复赛

（提高组） 测 试 数 据

第一题：共28分 序号 1 2 3 4 输入 300 250 275 252 200 138 245 181 205 471 782 1033 1058 1111 465 978 486 476 324 575 384 278 214 657 218 445 123 236 865 858 565 545 445 455 656 844 735 638 652 659 714 845 单枚最大可击落导弹数 5 1 7 6 需要系统数 2 7 4 7 分值 5 5 10 8

第二题：共25分 序号 1 2 3 4

第三题：共27分 序号 1 2 3 输入 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 100.0 99.9 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 22.10 7.38 24.21 6.81 82.08 6.96 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 输出 334.90 No solution. 105.95 分值 5 5 7 N 2 16 10 2 M 10011 AC27 89 101111 STEP 4 6 24 Impossible 分值 4 7 9 5 4 192.15 10

第四题：共40分 序号 1 2 3 4 N 7 7 10 5 K 3 4 3 5 STEP 1 8 13 MAX=69 1 5 24 37 MAX=165 1 10 28 MAX=146 1 4 9 31 51 MAX=126 分值 10 10 10 10 第40页 | 共209页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库1995-2008 历届NOIP试题及详解(8)在线全文阅读。