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
一个整数，表示箱子剩余空间。
2001年信奥赛普及组复赛真题，2001年信息学奥赛NOIP普及组复赛C++真题