2001年信息学奥赛NOIP普及组复赛C++真题

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 　　一个整数，表示箱子剩余空间。