第7届信息学分区联赛普及组复赛试题

第七届分区联赛普及组复赛 全称：N012001第七届全国青少年信息学 (计算机)奥林匹克分区联赛复赛试题 普及组 题一 数的计数 (20分) [问题描述] 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理 l·不作任何处理: z·茬它的左边加上一个自然数，但该自然数不能超过原数的一半; 3·加上数后，继续按此规则进行处理，直到不能再而 自然数为止。 [样例] 输入：6 满足条件的数为 6 (此部分不必输出) 6 26 126 36 136 输出：6 题二 最大公约数与最小公倍数问题 (20分) [问题描述] 输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。 条件:1.P、Q是正整数 二要求P、Q以xO为最大公约数，以yO为最小公倍数。 试求，满足条件的所有可能的两个正整数的个数。 [样例] 输入：x0=3 y0=60 输出：4 说明：(不用输出)此时的 P Q 分别为， 3 60 15 12 12 15 60 3 所以，满足条件的所有可能的两个正整数的个数共4种。 题三 求先序排列 (30分) [问题描述] 给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。 [样例] 输入：BADC BDCA 输出：ABCD 题四 装箱问题 (30分) [问题描述] 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 [样例] 输入： 24 --个整数，表示箱子容量 6 一个整数，表示有n个物品 8 接下来n行，分别表示这n个物品的各自体积。 3 12 7 9 7 输出： 0 一个整数，表示箱子剩余空间。 主管：中国科协、教育部 主办：中国计算机学会 承办：江苏省科协青少年科技中心 试题审定:全国青少年信息学奥林匹克科学委员会