NOI’2001第七届全国青少年信息学（计算机）奥林匹克分区

联赛复赛试题普及组

题一 数的计算(20分)

问题描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:

1.          不作任何处理;

2.          在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3.          加上数后,继续按此规则进行处理,直到不能再加自然数为止.

样例:  输入:  6

           满足条件的数为  6 (此部分不必输出)

                          16

                          26

                         126

                          36

                         136

输出:  6

题二 最大公约数和最小公倍数问题(20分)

问题描述

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:  1.P,A是正整数

2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

样例

输入:x0=3   yo=60

输出:4

说明(不用输出)此时的  P  Q  分别为:

    3   60

15      12

12      15

60       3

所以:满足条件的所有可能的两个正整数的个数共4种.

题三　求先序排列（30分）

问题描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

样例

输入：BADC  BDCA

输出：ABCD

题四　装箱问题（30分）

问题描述

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30＝，每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

样例

输入：

24             一个整数，表示箱子容量

6       一个整数，表示有n个物品

8　   接下来n行，分别表示这n 个物品的各自体积

3

12

7

9

7

输出：

0　　一个整数，表示箱子剩余空间。